-------- Forwarded Message --------
From: "Ágoston Kolos" <[email protected]>
To: [email protected]
Subject: I have a problem with glpk
Date: Wed, 17 Apr 2013 12:56:45 +0200
Dear Develpers,
I have use GLPK since several year, and I am very satisfied with it. I
would like to thank your work!
Recently I discovered a problem. A use standalone version 4.34 on a
Windows XP
> glpsol -v
GLPSOL: GLPK LP/MIP Solver 4.34
Copyright (C) 2008 Andrew Makhorin, Department for Applied Informatics,
Moscow Aviation Institute, Moscow, Russia. All rights reserved.
This program has ABSOLUTELY NO WARRANTY.
This program is free software; you may re-distribute it under the terms
of the GNU General Public License version 3 or later.
I tried to solve a mixed integer LP (attached as lp0.txt). The problem
said that is has not integer solution:
> glpsol --cpxlp lp0.txt
glp_read_lp: reading problem data from `lp0.txt'...
glp_read_lp: 132 rows, 150 columns, 332 non-zeros
glp_read_lp: 33 integer columns, all of which are binary
glp_read_lp: 231 lines were read
ipp_basic_tech: 4 row(s) and 5 column(s) removed
ipp_reduce_bnds: 29 pass(es) made, 85 bound(s) reduced
ipp_basic_tech: 1 row(s) and 1 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 1 coefficient(s) reduced
glp_intopt: presolved MIP has 127 rows, 144 columns, 323 non-zeros
glp_intopt: 30 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+008 ratio = 1.000e+008
GM: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
EQ: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
2N: min|aij| = 7.451e-001 max|aij| = 1.170e+000 ratio = 1.571e+000
Crashing...
Size of triangular part = 127
Solving LP relaxation...
0: obj = -7.341498715e+003 infeas = 6.319e+007 (0)
* 41: obj = 3.797002300e+004 infeas = 0.000e+000 (0)
* 78: obj = 2.983881319e+004 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 78: mip = not found yet >= -inf (1; 0)
+ 78: mip = not found yet >= tree is empty (0; 1)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used: 0.0 secs
Memory used: 0.2 Mb (254740 bytes)
I modified the problem: I attached a new constraint F4=1 (lp1.txt) and
the program solve the MLP:
> glpsol --cpxlp lp1.txt
glp_read_lp: reading problem data from `lp1.txt'...
glp_read_lp: 133 rows, 150 columns, 333 non-zeros
glp_read_lp: 33 integer columns, all of which are binary
glp_read_lp: 231 lines were read
ipp_basic_tech: 6 row(s) and 6 column(s) removed
ipp_reduce_bnds: 30 pass(es) made, 84 bound(s) reduced
ipp_basic_tech: 1 row(s) and 1 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 1 coefficient(s) reduced
glp_intopt: presolved MIP has 126 rows, 143 columns, 321 non-zeros
glp_intopt: 29 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+008 ratio = 1.000e+008
GM: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
EQ: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
2N: min|aij| = 7.451e-001 max|aij| = 1.170e+000 ratio = 1.571e+000
Crashing...
Size of triangular part = 126
Solving LP relaxation...
0: obj = 2.658501285e+003 infeas = 6.319e+007 (0)
* 41: obj = 4.758082980e+004 infeas = 0.000e+000 (0)
* 78: obj = 3.944961999e+004 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 78: mip = not found yet >= -inf (1; 0)
+ 78: >>>>> 3.944961999e+004 >= 3.944961999e+004 0.0% (1; 0)
+ 78: mip = 3.944961999e+004 >= tree is empty 0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2 Mb (246161 bytes)
However the optimal solution to the second problem is a feasible
solution for the firt problem, so I am confused. Is there something I
left out of consideration?
Thank your answer!
Best wishes:
Kolos
minimize
0.000136986301369863X1+0.001Y1+0.001Z1+10000B1+10000F1+
0.000136986301369863X2+0.001Y2+0.001Z2+10000B2+10000F2+
0.000136986301369863X3+0.001Y3+0.001Z3+10000B3+10000F3+
0.000136986301369863X4+0.001Y4+0.001Z4+10000B4+10000F4+
0.000136986301369863X5+0.001Y5+0.001Z5+10000B5+10000F5+
0.000136986301369863X6+0.001Y6+0.001Z6+10000B6+10000F6+
0.000136986301369863X7+0.001Y7+0.001Z7+10000B7+10000F7+
0.000136986301369863X8+0.001Y8+0.001Z8+10000B8+10000F8+
0.000136986301369863X9+0.001Y9+0.001Z9+10000B9+10000F9+
0.000136986301369863X10+0.001Y10+0.001Z10+10000B10+10000F10+
0.000136986301369863X11+0.001Y11+0.001Z11+10000B11+10000F11+
0.000136986301369863X12+0.001Y12+0.001Z12+10000B12+10000F12+
0.000136986301369863X13+0.001Y13+0.001Z13+10000B13+10000F13+
0.000136986301369863X14+0.001Y14+0.001Z14+10000B14+10000F14+
0.000136986301369863X15+0.001Y15+0.001Z15+10000B15+10000F15+
0.000136986301369863X16+0.001Y16+0.001Z16+10000B16+10000F16+
0.000136986301369863X17+0.001Y17+0.001Z17+10000B17+10000F17+
0.000136986301369863X18+0.001Y18+0.001Z18+10000B18+10000F18+
0.000136986301369863X19+0.001Y19+0.001Z19+10000B19+10000F19+
0.000136986301369863X20+0.001Y20+0.001Z20+10000B20+10000F20+
0.000136986301369863X21+0.001Y21+0.001Z21+10000B21+10000F21+
0.000136986301369863X22+0.001Y22+0.001Z22+10000B22+10000F22+
0.000136986301369863X23+0.001Y23+0.001Z23+10000B23+10000F23+
0.000136986301369863X24+0.001Y24+0.001Z24+10000B24+10000F24+
0.000136986301369863X25+0.001Y25+0.001Z25+10000B25+10000F25+
0.000136986301369863X26+0.001Y26+0.001Z26+10000B26+10000F26+
0.000136986301369863X27+0.001Y27+0.001Z27+10000B27+10000F27+
0.000136986301369863X28+0.001Y28+0.001Z28+10000B28+10000F28+
0.000136986301369863X29+0.001Y29+0.001Z29+10000B29+10000F29+
0.000136986301369863X30+0.001Y30+0.001Z30+10000B30+10000F30
subject to
X1=613627
X2-X1-Y2+Z2=-2534429
X3-X2-Y3+Z3=3891932
X4-X3-Y4+Z4=438299
X5-X4-Y5+Z5=1269578
X6-X5-Y6+Z6=1957909
X7-X6-Y7+Z7=-983405
X8-X7-Y8+Z8=2478916
X9-X8-Y9+Z9=-138982
X10-X9-Y10+Z10=1498782
X11-X10-Y11+Z11=-290044
X12-X11-Y12+Z12=-1325945
X13-X12-Y13+Z13=832869
X14-X13-Y14+Z14=-184669
X15-X14-Y15+Z15=-48293
X16-X15-Y16+Z16=299077
X17-X16-Y17+Z17=678315
X18-X17-Y18+Z18=-501070
X19-X18-Y19+Z19=-258297
X20-X19-Y20+Z20=1400600
X21-X20-Y21+Z21=930747
X22-X21-Y22+Z22=1624118
X23-X22-Y23+Z23=626818
X24-X23-Y24+Z24=911342
X25-X24-Y25+Z25=-3418085
X26-X25-Y26+Z26=-380826
X27-X26-Y27+Z27=-160769
X28-X27-Y28+Z28=-640593
X29-X28-Y29+Z29=6694850
X30-X29-Y30+Z30=308580
X1+Y2-Z2>=2534429
X6+Y7-Z7>=983405
X8+Y9-Z9>=138982
X10+Y11-Z11>=290044
X11+Y12-Z12>=1325945
X13+Y14-Z14>=184669
X14+Y15-Z15>=48293
X17+Y18-Z18>=501070
X18+Y19-Z19>=258297
X24+Y25-Z25>=3418085
X25+Y26-Z26>=380826
X26+Y27-Z27>=160769
X27+Y28-Z28>=640593
Z2-X1<=0
Z3-X2<=0
Z4-X3<=0
Z5-X4<=0
Z6-X5<=0
Z7-X6<=0
Z8-X7<=0
Z9-X8<=0
Z10-X9<=0
Z11-X10<=0
Z12-X11<=0
Z13-X12<=0
Z14-X13<=0
Z15-X14<=0
Z16-X15<=0
Z17-X16<=0
Z18-X17<=0
Z19-X18<=0
Z20-X19<=0
Z21-X20<=0
Z22-X21<=0
Z23-X22<=0
Z24-X23<=0
Z25-X24<=0
Z26-X25<=0
Z27-X26<=0
Z28-X27<=0
Z29-X28<=0
Z30-X29<=0
B1=0
Y2-100000000B2<=0
Y3-100000000B3<=0
Y4-100000000B4<=0
Y5-100000000B5<=0
Y6-100000000B6<=0
Y7-100000000B7<=0
Y8-100000000B8<=0
Y9-100000000B9<=0
Y10-100000000B10<=0
Y11-100000000B11<=0
Y12-100000000B12<=0
Y13-100000000B13<=0
Y14-100000000B14<=0
Y15-100000000B15<=0
Y16-100000000B16<=0
Y17-100000000B17<=0
Y18-100000000B18<=0
Y19-100000000B19<=0
Y20-100000000B20<=0
Y21-100000000B21<=0
Y22-100000000B22<=0
Y23-100000000B23<=0
Y24-100000000B24<=0
Y25-100000000B25<=0
Y26-100000000B26<=0
Y27-100000000B27<=0
Y28-100000000B28<=0
Y29-100000000B29<=0
Y30-100000000B30<=0
F1=0
Z2-100000000F2<=0
Z3-100000000F3<=0
Z4-100000000F4<=0
Z5-100000000F5<=0
Z6-100000000F6<=0
Z7-100000000F7<=0
Z8-100000000F8<=0
Z9-100000000F9<=0
Z10-100000000F10<=0
Z11-100000000F11<=0
Z12-100000000F12<=0
Z13-100000000F13<=0
Z14-100000000F14<=0
Z15-100000000F15<=0
Z16-100000000F16<=0
Z17-100000000F17<=0
Z18-100000000F18<=0
Z19-100000000F19<=0
Z20-100000000F20<=0
Z21-100000000F21<=0
Z22-100000000F22<=0
Z23-100000000F23<=0
Z24-100000000F24<=0
Z25-100000000F25<=0
Z26-100000000F26<=0
Z27-100000000F27<=0
Z28-100000000F28<=0
Z29-100000000F29<=0
Z30-100000000F30<=0
binary
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
B11
B12
B13
B14
B15
B16
B17
B18
B19
B20
B21
B22
B23
B24
B25
B26
B27
B28
B29
F1
F2
F3
F4
end
minimize
0.000136986301369863X1+0.001Y1+0.001Z1+10000B1+10000F1+
0.000136986301369863X2+0.001Y2+0.001Z2+10000B2+10000F2+
0.000136986301369863X3+0.001Y3+0.001Z3+10000B3+10000F3+
0.000136986301369863X4+0.001Y4+0.001Z4+10000B4+10000F4+
0.000136986301369863X5+0.001Y5+0.001Z5+10000B5+10000F5+
0.000136986301369863X6+0.001Y6+0.001Z6+10000B6+10000F6+
0.000136986301369863X7+0.001Y7+0.001Z7+10000B7+10000F7+
0.000136986301369863X8+0.001Y8+0.001Z8+10000B8+10000F8+
0.000136986301369863X9+0.001Y9+0.001Z9+10000B9+10000F9+
0.000136986301369863X10+0.001Y10+0.001Z10+10000B10+10000F10+
0.000136986301369863X11+0.001Y11+0.001Z11+10000B11+10000F11+
0.000136986301369863X12+0.001Y12+0.001Z12+10000B12+10000F12+
0.000136986301369863X13+0.001Y13+0.001Z13+10000B13+10000F13+
0.000136986301369863X14+0.001Y14+0.001Z14+10000B14+10000F14+
0.000136986301369863X15+0.001Y15+0.001Z15+10000B15+10000F15+
0.000136986301369863X16+0.001Y16+0.001Z16+10000B16+10000F16+
0.000136986301369863X17+0.001Y17+0.001Z17+10000B17+10000F17+
0.000136986301369863X18+0.001Y18+0.001Z18+10000B18+10000F18+
0.000136986301369863X19+0.001Y19+0.001Z19+10000B19+10000F19+
0.000136986301369863X20+0.001Y20+0.001Z20+10000B20+10000F20+
0.000136986301369863X21+0.001Y21+0.001Z21+10000B21+10000F21+
0.000136986301369863X22+0.001Y22+0.001Z22+10000B22+10000F22+
0.000136986301369863X23+0.001Y23+0.001Z23+10000B23+10000F23+
0.000136986301369863X24+0.001Y24+0.001Z24+10000B24+10000F24+
0.000136986301369863X25+0.001Y25+0.001Z25+10000B25+10000F25+
0.000136986301369863X26+0.001Y26+0.001Z26+10000B26+10000F26+
0.000136986301369863X27+0.001Y27+0.001Z27+10000B27+10000F27+
0.000136986301369863X28+0.001Y28+0.001Z28+10000B28+10000F28+
0.000136986301369863X29+0.001Y29+0.001Z29+10000B29+10000F29+
0.000136986301369863X30+0.001Y30+0.001Z30+10000B30+10000F30
subject to
X1=613627
X2-X1-Y2+Z2=-2534429
X3-X2-Y3+Z3=3891932
X4-X3-Y4+Z4=438299
X5-X4-Y5+Z5=1269578
X6-X5-Y6+Z6=1957909
X7-X6-Y7+Z7=-983405
X8-X7-Y8+Z8=2478916
X9-X8-Y9+Z9=-138982
X10-X9-Y10+Z10=1498782
X11-X10-Y11+Z11=-290044
X12-X11-Y12+Z12=-1325945
X13-X12-Y13+Z13=832869
X14-X13-Y14+Z14=-184669
X15-X14-Y15+Z15=-48293
X16-X15-Y16+Z16=299077
X17-X16-Y17+Z17=678315
X18-X17-Y18+Z18=-501070
X19-X18-Y19+Z19=-258297
X20-X19-Y20+Z20=1400600
X21-X20-Y21+Z21=930747
X22-X21-Y22+Z22=1624118
X23-X22-Y23+Z23=626818
X24-X23-Y24+Z24=911342
X25-X24-Y25+Z25=-3418085
X26-X25-Y26+Z26=-380826
X27-X26-Y27+Z27=-160769
X28-X27-Y28+Z28=-640593
X29-X28-Y29+Z29=6694850
X30-X29-Y30+Z30=308580
X1+Y2-Z2>=2534429
X6+Y7-Z7>=983405
X8+Y9-Z9>=138982
X10+Y11-Z11>=290044
X11+Y12-Z12>=1325945
X13+Y14-Z14>=184669
X14+Y15-Z15>=48293
X17+Y18-Z18>=501070
X18+Y19-Z19>=258297
X24+Y25-Z25>=3418085
X25+Y26-Z26>=380826
X26+Y27-Z27>=160769
X27+Y28-Z28>=640593
Z2-X1<=0
Z3-X2<=0
Z4-X3<=0
Z5-X4<=0
Z6-X5<=0
Z7-X6<=0
Z8-X7<=0
Z9-X8<=0
Z10-X9<=0
Z11-X10<=0
Z12-X11<=0
Z13-X12<=0
Z14-X13<=0
Z15-X14<=0
Z16-X15<=0
Z17-X16<=0
Z18-X17<=0
Z19-X18<=0
Z20-X19<=0
Z21-X20<=0
Z22-X21<=0
Z23-X22<=0
Z24-X23<=0
Z25-X24<=0
Z26-X25<=0
Z27-X26<=0
Z28-X27<=0
Z29-X28<=0
Z30-X29<=0
B1=0
Y2-100000000B2<=0
Y3-100000000B3<=0
Y4-100000000B4<=0
Y5-100000000B5<=0
Y6-100000000B6<=0
Y7-100000000B7<=0
Y8-100000000B8<=0
Y9-100000000B9<=0
Y10-100000000B10<=0
Y11-100000000B11<=0
Y12-100000000B12<=0
Y13-100000000B13<=0
Y14-100000000B14<=0
Y15-100000000B15<=0
Y16-100000000B16<=0
Y17-100000000B17<=0
Y18-100000000B18<=0
Y19-100000000B19<=0
Y20-100000000B20<=0
Y21-100000000B21<=0
Y22-100000000B22<=0
Y23-100000000B23<=0
Y24-100000000B24<=0
Y25-100000000B25<=0
Y26-100000000B26<=0
Y27-100000000B27<=0
Y28-100000000B28<=0
Y29-100000000B29<=0
Y30-100000000B30<=0
F1=0
Z2-100000000F2<=0
Z3-100000000F3<=0
Z4-100000000F4<=0
Z5-100000000F5<=0
Z6-100000000F6<=0
Z7-100000000F7<=0
Z8-100000000F8<=0
Z9-100000000F9<=0
Z10-100000000F10<=0
Z11-100000000F11<=0
Z12-100000000F12<=0
Z13-100000000F13<=0
Z14-100000000F14<=0
Z15-100000000F15<=0
Z16-100000000F16<=0
Z17-100000000F17<=0
Z18-100000000F18<=0
Z19-100000000F19<=0
Z20-100000000F20<=0
Z21-100000000F21<=0
Z22-100000000F22<=0
Z23-100000000F23<=0
Z24-100000000F24<=0
Z25-100000000F25<=0
Z26-100000000F26<=0
Z27-100000000F27<=0
Z28-100000000F28<=0
Z29-100000000F29<=0
Z30-100000000F30<=0
F4=1
binary
B1
B2
B3
B4
B5
B6
B7
B8
B9
B10
B11
B12
B13
B14
B15
B16
B17
B18
B19
B20
B21
B22
B23
B24
B25
B26
B27
B28
B29
F1
F2
F3
F4
end
_______________________________________________
Bug-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/bug-glpk
