|
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 } |