I think I understood what you meant now. The answer also is quite helpful understanding the "integer tolerance". (I think it would be great if the reference manual could contain a small explanation of this (i.e. that it just means that anything that only differs so much from a integer value is considered acceptable).
Thanks for the great help Thomas On 12/03/2010 04:28 PM, Andrew Makhorin wrote:
My current problem is rather small (I attached it). But the solution found is wrong (which is only stated in the KKT.PE information below the problem solution).In your case glpsol reports: Integer feasibility conditions: KKT.PE: max.abs.err = 1.00e+00 on row 123 max.rel.err = 5.00e-01 on row 123 SOLUTION IS WRONG KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality I solved your instance with glpsol 4.44 (please see the solver output below). Though now the solution found is correct, look at row 123, which is the following constraint: R6_upper: + R6 + 999999 R6_w0<= 999999 R6_w0 is a binary variable, and the default integer tolerance is 1e-5. Thus, if R6_w0 takes on the value, say, 1e-6, it is considered as integer feasible; however, due to big constraint coefficient this gives an absolute error for R6_w0 about 0.999 as in your case. The "big M" you are using is too big, so the solver cannot provide a more accurate solution. GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s) specified in the command line: --glp Problem --wlp /dev/stdout -o /dev/stdout Reading problem data from `Problem'... Unable to open `Problem' - No such file or directory GLPK LP/MIP file processing error m...@none:~/Desktop/glpk-4.44/examples$ ./glpsol --glp Problem --wlp /dev/stdout -o /dev/stdout GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s) specified in the command line: --glp Problem --wlp /dev/stdout -o /dev/stdout Reading problem data from `Problem'... 159 rows, 92 columns, 319 non-zeros 39 integer variables, all of which are binary 744 lines were read Writing problem data to `/dev/stdout'... \* Problem: Unknown *\ Maximize obj: + R12 + 0 x_92 Subject To M_E: + R2 + R3 - R4 = 0 M_F: + R1 - R2 = 0 M_G: + R4 - R5 - R6 = 0 M_H: + R6 - R7 - R8 = 0 M_I: + R5 + R7 - R10 - R13 = 0 M_J: + R8 - R9 = 0 M_K: + R9 + R10 - R11 = 0 M_L: + R11 - R12 = 0 R1_weights: + R1_w0 + x_66 + R1_w~ = 1 R2_weights: + R2_w0 + x_67 + R2_w~ = 1 R3_weights: + R3_w0 + x_68 + R3_w~ = 1 R4_weights: + R4_w0 + x_69 + R4_w~ = 1 R5_weights: + R5_w0 + x_70 + R5_w~ = 1 R6_weights: + R6_w0 + x_71 + R6_w~ = 1 R7_weights: + R7_w0 + x_72 + R7_w~ = 1 R8_weights: + R8_w0 + x_73 + R8_w~ = 1 R9_weights: + R9_w0 + x_74 + R9_w~ = 1 R10_weights: + R10_w0 + x_75 + R10_w~ = 1 R11_weights: + R11_w0 + x_76 + R11_w~ = 1 R13_weights: + R13_w0 + x_77 + R13_w~ = 1 R12_weights: + R12_w0 + x_78 + R12_w~ = 1 R1_flux: + R1 - R1_v0 - x_27 - R1_v~ = 0 R2_flux: + R2 - R2_v0 - x_28 - R2_v~ = 0 R3_flux: + R3 - R3_v0 - x_29 - R3_v~ = 0 R4_flux: + R4 - R4_v0 - x_30 - R4_v~ = 0 R5_flux: + R5 - R5_v0 - x_31 - R5_v~ = 0 R6_flux: + R6 - R6_v0 - x_32 - R6_v~ = 0 R7_flux: + R7 - R7_v0 - x_33 - R7_v~ = 0 R8_flux: + R8 - R8_v0 - x_34 - R8_v~ = 0 R9_flux: + R9 - R9_v0 - x_35 - R9_v~ = 0 R10_flux: + R10 - R10_v0 - x_36 - R10_v~ = 0 R11_flux: + R11 - R11_v0 - x_37 - R11_v~ = 0 R13_flux: + R13 - R13_v0 - x_38 - R13_v~ = 0 R12_flux: + R12 - R12_v0 - x_39 - R12_v~ = 0 R1_upper: + R1 + 10 R1_w0<= 10 R2_upper: + R2 + 999999 R2_w0<= 999999 R3_upper: + R3 + 5 R3_w0<= 5 R4_upper: + R4 + 999999 R4_w0<= 999999 R5_upper: + R5 + 999999 R5_w0<= 999999 R6_upper: + R6 + 999999 R6_w0<= 999999 R7_upper: + R7 + 999999 R7_w0<= 999999 R8_upper: + R8 + 999999 R8_w0<= 999999 R9_upper: + R9 + 999999 R9_w0<= 999999 R10_upper: + R10 + 999999 R10_w0<= 999999 R11_upper: + R11 + 999999 R11_w0<= 999999 R13_upper: + R13 + 999999 R13_w0<= 999999 R12_upper: + R12 + 999999 R12_w0<= 999999 R1_lower: + R1>= 0 R2_lower: + R2>= 0 R3_lower: + R3>= 0 R4_lower: + R4>= 0 R5_lower: + R5>= 0 R6_lower: + R6>= 0 R7_lower: + R7>= 0 R8_lower: + R8>= 0 R9_lower: + R9>= 0 R10_lower: + R10>= 0 R11_lower: + R11>= 0 R13_lower: + R13>= 0 R12_lower: + R12>= 0 R1_posepsilon: + R1_v0 + 0.5 R1_w0>= 0 R2_posepsilon: + R2_v0 + 0.5 R2_w0>= 0 R3_posepsilon: + R3_v0 + 0.5 R3_w0>= 0 R4_posepsilon: + R4_v0 + 0.5 R4_w0>= 0 R5_posepsilon: + R5_v0 + 0.5 R5_w0>= 0 R6_posepsilon: + R6_v0 + 0.5 R6_w0>= 0 R7_posepsilon: + R7_v0 + 0.5 R7_w0>= 0 R8_posepsilon: + R8_v0 + 0.5 R8_w0>= 0 R9_posepsilon: + R9_v0 + 0.5 R9_w0>= 0 R10_posepsilon: + R10_v0 + 0.5 R10_w0>= 0 R11_posepsilon: + R11_v0 + 0.5 R11_w0>= 0 R13_posepsilon: + R13_v0 + 0.5 R13_w0>= 0 R12_posepsilon: + R12_v0 + 0.5 R12_w0>= 0 R1_negepsilon: + R1_v0 - 0.5 R1_w0<= 0 R2_negepsilon: + R2_v0 - 0.5 R2_w0<= 0 R3_negepsilon: + R3_v0 - 0.5 R3_w0<= 0 R4_negepsilon: + R4_v0 - 0.5 R4_w0<= 0 R5_negepsilon: + R5_v0 - 0.5 R5_w0<= 0 R6_negepsilon: + R6_v0 - 0.5 R6_w0<= 0 R7_negepsilon: + R7_v0 - 0.5 R7_w0<= 0 R8_negepsilon: + R8_v0 - 0.5 R8_w0<= 0 R9_negepsilon: + R9_v0 - 0.5 R9_w0<= 0 R10_negepsilon: + R10_v0 - 0.5 R10_w0<= 0 R11_negepsilon: + R11_v0 - 0.5 R11_w0<= 0 R13_negepsilon: + R13_v0 - 0.5 R13_w0<= 0 R12_negepsilon: + R12_v0 - 0.5 R12_w0<= 0 R1_lower2: - R1_v~<= 0 R2_lower2: - R2_v~<= 0 R3_lower2: - R3_v~<= 0 R4_lower2: - R4_v~<= 0 R5_lower2: - R5_v~<= 0 R6_lower2: - R6_v~<= 0 R7_lower2: - R7_v~<= 0 R8_lower2: - R8_v~<= 0 R9_lower2: - R9_v~<= 0 R10_lower2: - R10_v~<= 0 R11_lower2: - R11_v~<= 0 R13_lower2: - R13_v~<= 0 R12_lower2: - R12_v~<= 0 R1_lowepsilon: + R1_v~ + R1_w~<= 0 R2_lowepsilon: + R2_v~ + R2_w~<= 0 R3_lowepsilon: + R3_v~ + R3_w~<= 0 R4_lowepsilon: + R4_v~ + R4_w~<= 0 R5_lowepsilon: + R5_v~ + R5_w~<= 0 R6_lowepsilon: + R6_v~ + R6_w~<= 0 R7_lowepsilon: + R7_v~ + R7_w~<= 0 R8_lowepsilon: + R8_v~ + R8_w~<= 0 R9_lowepsilon: + R9_v~ + R9_w~<= 0 R10_lowepsilon: + R10_v~ + R10_w~<= 0 R11_lowepsilon: + R11_v~ + R11_w~<= 0 R13_lowepsilon: + R13_v~ + R13_w~<= 0 R12_lowepsilon: + R12_v~ + R12_w~<= 0 R1_upper2: - x_27 + 10 x_66>= 0 R2_upper2: - x_28 + 999999 x_67>= 0 R3_upper2: - x_29 + 5 x_68>= 0 R4_upper2: - x_30 + 999999 x_69>= 0 R5_upper2: - x_31 + 999999 x_70>= 0 R6_upper2: - x_32 + 999999 x_71>= 0 R7_upper2: - x_33 + 999999 x_72>= 0 R8_upper2: - x_34 + 999999 x_73>= 0 R9_upper2: - x_35 + 999999 x_74>= 0 R10_upper2: - x_36 + 999999 x_75>= 0 R11_upper2: - x_37 + 999999 x_76>= 0 R13_upper2: - x_38 + 999999 x_77>= 0 R12_upper2: - x_39 + 999999 x_78>= 0 R1_upperepsilon: - x_27 + x_66<= 0 R2_upperepsilon: - x_28 + x_67<= 0 R3_upperepsilon: - x_29 + x_68<= 0 R4_upperepsilon: - x_30 + x_69<= 0 R5_upperepsilon: - x_31 + x_70<= 0 R6_upperepsilon: - x_32 + x_71<= 0 R7_upperepsilon: - x_33 + x_72<= 0 R8_upperepsilon: - x_34 + x_73<= 0 R9_upperepsilon: - x_35 + x_74<= 0 R10_upperepsilon: - x_36 + x_75<= 0 R11_upperepsilon: - x_37 + x_76<= 0 R13_upperepsilon: - x_38 + x_77<= 0 R12_upperepsilon: - x_39 + x_78<= 0 Weight_Contraint0: - R1_w0 - R2_w0 - R3_w0 - R4_w0 - R5_w0 + R6_w0 + R7_w0 + R8_w0 + R9_w0 - R10_w0 - R11_w0 + R13_w0<= 4 Weight_Contraint1: - R1_w0 - R2_w0 - R3_w0 - R4_w0 + R5_w0 - R6_w0 + R7_w0 - R8_w0 - R9_w0 + R10_w0 - R11_w0 + R13_w0<= 3 Bounds R1 free R2 free R3 free R4 free R5 free R6 free R7 free R8 free R9 free R10 free R11 free R13 free R12 free R1_v0 free R2_v0 free R3_v0 free R4_v0 free R5_v0 free R6_v0 free R7_v0 free R8_v0 free R9_v0 free R10_v0 free R11_v0 free R13_v0 free R12_v0 free x_27 free x_28 free x_29 free x_30 free x_31 free x_32 free x_33 free x_34 free x_35 free x_36 free x_37 free x_38 free x_39 free R1_v~ free R2_v~ free R3_v~ free R4_v~ free R5_v~ free R6_v~ free R7_v~ free R8_v~ free R9_v~ free R10_v~ free R11_v~ free R13_v~ free R12_v~ free 0<= R1_w0<= 1 0<= R2_w0<= 1 0<= R3_w0<= 1 0<= R4_w0<= 1 0<= R5_w0<= 1 0<= R6_w0<= 1 0<= R7_w0<= 1 0<= R8_w0<= 1 0<= R9_w0<= 1 0<= R10_w0<= 1 0<= R11_w0<= 1 0<= R13_w0<= 1 0<= R12_w0<= 1 0<= x_66<= 1 0<= x_67<= 1 0<= x_68<= 1 0<= x_69<= 1 0<= x_70<= 1 0<= x_71<= 1 0<= x_72<= 1 0<= x_73<= 1 0<= x_74<= 1 0<= x_75<= 1 0<= x_76<= 1 0<= x_77<= 1 0<= x_78<= 1 0<= R1_w~<= 1 0<= R2_w~<= 1 0<= R3_w~<= 1 0<= R4_w~<= 1 0<= R5_w~<= 1 0<= R6_w~<= 1 0<= R7_w~<= 1 0<= R8_w~<= 1 0<= R9_w~<= 1 0<= R10_w~<= 1 0<= R11_w~<= 1 0<= R13_w~<= 1 0<= R12_w~<= 1 x_92 = 0 Generals R1_w0 R2_w0 R3_w0 R4_w0 R5_w0 R6_w0 R7_w0 R8_w0 R9_w0 R10_w0 R11_w0 R13_w0 R12_w0 x_66 x_67 x_68 x_69 x_70 x_71 x_72 x_73 x_74 x_75 x_76 x_77 x_78 R1_w~ R2_w~ R3_w~ R4_w~ R5_w~ R6_w~ R7_w~ R8_w~ R9_w~ R10_w~ R11_w~ R13_w~ R12_w~ End 285 lines were written GLPK Integer Optimizer, v4.44 159 rows, 92 columns, 319 non-zeros 39 integer variables, all of which are binary Preprocessing... 2 hidden covering inequaliti(es) were detected 22 constraint coefficient(s) were reduced 101 rows, 65 columns, 241 non-zeros 26 integer variables, all of which are binary Scaling... A: min|aij| = 5.000e-01 max|aij| = 4.550e+01 ratio = 9.100e+01 GM: min|aij| = 3.850e-01 max|aij| = 2.597e+00 ratio = 6.745e+00 EQ: min|aij| = 1.482e-01 max|aij| = 1.000e+00 ratio = 6.745e+00 2N: min|aij| = 1.250e-01 max|aij| = 1.250e+00 ratio = 1.000e+01 Constructing initial basis... Size of triangular part = 101 Solving LP relaxation... GLPK Simplex Optimizer, v4.44 101 rows, 65 columns, 241 non-zeros 0: obj = 0.000000000e+00 infeas = 1.950e+01 (0) * 25: obj = 2.000000000e+00 infeas = 0.000e+00 (0) * 31: obj = 1.500000000e+01 infeas = 0.000e+00 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 31: mip = not found yet<= +inf (1; 0) + 35:>>>>> 1.500000000e+01<= 1.500000000e+01 0.0% (2; 0) + 35: mip = 1.500000000e+01<= tree is empty 0.0% (0; 3) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.2 Mb (178843 bytes) Writing MIP solution to `/dev/stdout'... Problem: Rows: 159 Columns: 92 (39 integer, 39 binary) Non-zeros: 319 Status: INTEGER OPTIMAL Objective: 15 (MAXimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 0 2 0 3 0 4 0 5 M_E 0 0 = 6 M_F 0 0 = 7 M_G 0 0 = 8 M_H 0 0 = 9 M_I 0 0 = 10 M_J 0 0 = 11 M_K 0 0 = 12 M_L 0 0 = 13 0 14 R1_weights 1 1 = 15 R2_weights 1 1 = 16 R3_weights 1 1 = 17 R4_weights 1 1 = 18 R5_weights 1 1 = 19 R6_weights 1 1 = 20 R7_weights 1 1 = 21 R8_weights 1 1 = 22 R9_weights 1 1 = 23 R10_weights 1 1 = 24 R11_weights 1 1 = 25 R13_weights 1 1 = 26 R12_weights 1 1 = 27 R1_flux 0 0 = 28 R2_flux 0 0 = 29 R3_flux 0 0 = 30 R4_flux 0 0 = 31 R5_flux 0 0 = 32 R6_flux 0 0 = 33 R7_flux 0 0 = 34 R8_flux 0 0 = 35 R9_flux 0 0 = 36 R10_flux 0 0 = 37 R11_flux 0 0 = 38 R13_flux 0 0 = 39 R12_flux 0 0 = 40 R1_upper 10 10 41 R2_upper 10 999999 42 R3_upper 5 5 43 R4_upper 15 999999 44 R5_upper 1 999999 45 R6_upper 14 999999 46 R7_upper 1 999999 47 R8_upper 13 999999 48 R9_upper 13 999999 49 R10_upper 2 999999 50 R11_upper 15 999999 51 R13_upper 999999 999999 52 R12_upper 15 999999 53 R1_lower 10 0 54 R2_lower 10 0 55 R3_lower 5 0 56 R4_lower 15 0 57 R5_lower 1 0 58 R6_lower 14 0 59 R7_lower 1 0 60 R8_lower 13 0 61 R9_lower 13 0 62 R10_lower 2 0 63 R11_lower 15 0 64 R13_lower 0 0 65 R12_lower 15 0 66 R1_posepsilon 0 0 67 R2_posepsilon 0 0 68 R3_posepsilon 0 0 69 R4_posepsilon 0 0 70 R5_posepsilon 0 0 71 R6_posepsilon 0 0 72 R7_posepsilon 0 0 73 R8_posepsilon 0 0 74 R9_posepsilon 0 0 75 R10_posepsilon 0 0 76 R11_posepsilon 0 0 77 R13_posepsilon 0.5 0 78 R12_posepsilon 0 0 79 R1_negepsilon 0 0 80 R2_negepsilon 0 0 81 R3_negepsilon 0 0 82 R4_negepsilon 0 0 83 R5_negepsilon 0 0 84 R6_negepsilon 0 0 85 R7_negepsilon 0 0 86 R8_negepsilon 0 0 87 R9_negepsilon 0 0 88 R10_negepsilon 0 0 89 R11_negepsilon 0 0 90 R13_negepsilon -0.5 0 91 R12_negepsilon 0 0 92 R1_lower2 0 0 93 R2_lower2 0 0 94 R3_lower2 0 0 95 R4_lower2 0 0 96 R5_lower2 0 0 97 R6_lower2 0 0 98 R7_lower2 0 0 99 R8_lower2 0 0 100 R9_lower2 0 0 101 R10_lower2 0 0 102 R11_lower2 0 0 103 R13_lower2 0 0 104 R12_lower2 0 0 105 R1_lowepsilon 0 0 106 R2_lowepsilon 0 0 107 R3_lowepsilon 0 0 108 R4_lowepsilon 0 0 109 R5_lowepsilon 0 0 110 R6_lowepsilon 0 0 111 R7_lowepsilon 0 0 112 R8_lowepsilon 0 0 113 R9_lowepsilon 0 0 114 R10_lowepsilon 0 0 115 R11_lowepsilon 0 0 116 R13_lowepsilon 0 0 117 R12_lowepsilon 0 0 118 R1_upper2 0 0 119 R2_upper2 999989 0 120 R3_upper2 0 0 121 R4_upper2 999984 0 122 R5_upper2 999998 0 123 R6_upper2 999985 0 124 R7_upper2 999998 0 125 R8_upper2 999986 0 126 R9_upper2 999986 0 127 R10_upper2 999997 0 128 R11_upper2 999984 0 129 R13_upper2 0 0 130 R12_upper2 999984 0 131 R1_upperepsilon -9 0 132 R2_upperepsilon -9 0 133 R3_upperepsilon -4 0 134 R4_upperepsilon -14 0 135 R5_upperepsilon 0 0 136 R6_upperepsilon -13 0 137 R7_upperepsilon 0 0 138 R8_upperepsilon -12 0 139 R9_upperepsilon -12 0 140 R10_upperepsilon -1 0 141 R11_upperepsilon -14 0 142 R13_upperepsilon 0 0 143 R12_upperepsilon -14 0 144 0 145 0 146 0 147 0 148 0 149 0 150 0 151 0 152 0 153 0 154 0 155 0 156 0 157 0 158 Weight_Contraint0 1 4 159 Weight_Contraint1 1 3 No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 R1 10 2 R2 10 3 R3 5 4 R4 15 5 R5 1 6 R6 14 7 R7 1 8 R8 13 9 R9 13 10 R10 2 11 R11 15 12 R13 0 13 R12 15 14 R1_v0 0 15 R2_v0 0 16 R3_v0 0 17 R4_v0 0 18 R5_v0 0 19 R6_v0 0 20 R7_v0 0 21 R8_v0 0 22 R9_v0 0 23 R10_v0 0 24 R11_v0 0 25 R13_v0 0 26 R12_v0 0 27 R1_v+ 10 28 R2_v+ 10 29 R3_v+ 5 30 R4_v+ 15 31 R5_v+ 1 32 R6_v+ 14 33 R7_v+ 1 34 R8_v+ 13 35 R9_v+ 13 36 R10_v+ 2 37 R11_v+ 15 38 R13_v+ 0 39 R12_v+ 15 40 R1_v- 0 41 R2_v- 0 42 R3_v- 0 43 R4_v- 0 44 R5_v- 0 45 R6_v- 0 46 R7_v- 0 47 R8_v- 0 48 R9_v- 0 49 R10_v- 0 50 R11_v- 0 51 R13_v- 0 52 R12_v- 0 53 R1_w0 * 0 0 1 54 R2_w0 * 0 0 1 55 R3_w0 * 0 0 1 56 R4_w0 * 0 0 1 57 R5_w0 * 0 0 1 58 R6_w0 * 0 0 1 59 R7_w0 * 0 0 1 60 R8_w0 * 0 0 1 61 R9_w0 * 0 0 1 62 R10_w0 * 0 0 1 63 R11_w0 * 0 0 1 64 R13_w0 * 1 0 1 65 R12_w0 * 0 0 1 66 R1_w+ * 1 0 1 67 R2_w+ * 1 0 1 68 R3_w+ * 1 0 1 69 R4_w+ * 1 0 1 70 R5_w+ * 1 0 1 71 R6_w+ * 1 0 1 72 R7_w+ * 1 0 1 73 R8_w+ * 1 0 1 74 R9_w+ * 1 0 1 75 R10_w+ * 1 0 1 76 R11_w+ * 1 0 1 77 R13_w+ * 0 0 1 78 R12_w+ * 1 0 1 79 R1_w- * 0 0 1 80 R2_w- * 0 0 1 81 R3_w- * 0 0 1 82 R4_w- * 0 0 1 83 R5_w- * 0 0 1 84 R6_w- * 0 0 1 85 R7_w- * 0 0 1 86 R8_w- * 0 0 1 87 R9_w- * 0 0 1 88 R10_w- * 0 0 1 89 R11_w- * 0 0 1 90 R13_w- * 0 0 1 91 R12_w- * 0 0 1 92 0 0 = Integer feasibility conditions: KKT.PE: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality End of output
-- Dipl.-Inf. Thomas Pfau [email protected] Institute for Complex Systems and Mathematical Biology University of Aberdeen Meston Building, Room 303 Phone : ++44 1224 27-2907 Aberdeen AB24 3UE United Kingdom The University of Aberdeen is a charity registered in Scotland, No SC013683. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
