1 /*Find the minimum value which satisfies the linear inequality:

2 a*x + b*y >= 1 {a,b,x,y Integers} {a,b > 0} {a,b entered on command line}

3

4 Nigel_Galloway@operamail.com

5 February 2008

6 */

7 using System;

8 using System.Runtime.InteropServices;

9

10 unsafe class GLPK{

11 double *lp;

12 public int a;

13 public int b;

14

15 const string glpkLibrary = "libglpk.so";

16 readonly int GLP_FR = 1;

17 readonly int GLP_IV = 2;

18 readonly int GLP_DB = 4;

19 struct ConstraintMatrix{

20 public fixed int ia[3];

21 public fixed int ja[3];

22 public fixed double ar[3];

23 }

24 [DllImport(glpkLibrary, SetLastError=true)]

25 static extern double* glp_create_prob();

26 [DllImport(glpkLibrary, SetLastError=true)]

27 static extern void glp_add_rows(double* lp, int rows);

28 [DllImport(glpkLibrary, SetLastError=true)]

29 static extern void glp_add_cols(double* lp, int cols);

30 [DllImport(glpkLibrary, SetLastError=true)]

31 static extern void glp_set_col_bnds(double* lp, int col, int bound_type, double lower_bound, double upper_bound);

32 [DllImport(glpkLibrary, SetLastError=true)]

33 static extern void glp_set_col_kind(double* lp, int col, int kind);

34 [DllImport(glpkLibrary, SetLastError=true)]

35 static extern void glp_load_matrix(double* lp, int elements, int* ia, int* ja, double* ar);

36 public GLPK(int a, int b){

37 this.a = a;

38 this.b = b;

39 lp = glp_create_prob();

40 //Col 1 is x, Col 2 is y

41 glp_add_rows(lp, 1);

42 glp_add_cols(lp, 2);

43 glp_set_col_bnds(lp, 1, GLP_FR, 0.0, 0.0);

44 glp_set_col_bnds(lp, 2, GLP_FR, 0.0, 0.0);

45 glp_set_col_kind(lp, 1, GLP_IV);

46 glp_set_col_kind(lp, 2, GLP_IV);

47 //Row 1 is a*x + b*y

48 ConstraintMatrix CM = new ConstraintMatrix();

49 CM.ia[1]=1; CM.ja[1]=1; CM.ar[1]=a;

50 CM.ia[2]=1; CM.ja[2]=2; CM.ar[2]=b;

51 glp_load_matrix(lp, 2, CM.ia, CM.ja, CM.ar);

52 Console.WriteLine("Hello Nigel");

53 }

54

55 [DllImport(glpkLibrary, SetLastError=true)]

56 static extern void glp_set_row_bnds(double* lp, int row, int bound_type, double lower_bound, double upper_bound);

57 [DllImport(glpkLibrary, SetLastError=true)]

58 static extern void glp_simplex(double* lp, void* options);

59 [DllImport(glpkLibrary, SetLastError=true)]

60 static extern void glp_intopt(double* lp, void* options);

61 [DllImport(glpkLibrary, SetLastError=true)]

62 static extern double glp_mip_col_val(double* lp, int col);

63 public int betterGuess(int upper_bound){

64 //Find a new guess less than the old guess: 1 <= (a*x + b*y) <= (old guess - 1)

65 glp_set_row_bnds(lp, 1, GLP_DB, 1.0, ((double)upper_bound)-0.5);

66 glp_simplex(lp, null);

67 glp_intopt(lp, null);

68 int x = (int)glp_mip_col_val(lp, 1);

69 int y = (int)glp_mip_col_val(lp, 2);

70 int nextGuess = a*x + b*y;

71 Console.WriteLine("x = {0}, y = {1}, a*x + b*y = {2}",x,y,nextGuess);

72 return nextGuess;

73 }

74

75 [DllImport(glpkLibrary, SetLastError=true)]

76 static extern void glp_delete_prob(double* lp);

77 ~GLPK(){

78 glp_delete_prob(lp);

79 Console.WriteLine("Goodbye Nigel");

80 }

81

82 }

83

84 class test{

85 static bool isMinimum(int a, int b, int guess){

86 Console.WriteLine("Trying {0}",guess);

87 if (a%guess > 0) return false;

88 if (b%guess > 0) return false;

89 Console.WriteLine("Solution is {0}",guess);

90 return true;

91 }

92

93 public static void Main(string[] args){

94 Console.WriteLine("a = {0}, b = {1}",args[0], args[1]);

95 GLPK lp = new GLPK(Int32.Parse(args[0]),Int32.Parse(args[1]));

96 int guess = (lp.a > lp.b) ? lp.b : lp.a;

97 while (!isMinimum(lp.a,lp.b,guess)) guess = lp.betterGuess(guess);

98 }

99 }