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
address@hidden:~/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