[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Re: MIP Solutions
|
From: |
Andrew Makhorin |
|
Subject: |
Re: [Help-glpk] Re: MIP Solutions |
|
Date: |
Fri, 03 Dec 2010 19:28:53 +0300 |
> 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