[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] MILP wrong solution
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] MILP wrong solution |
Date: |
Sat, 11 Jul 2009 22:58:47 +0300 |
> I have a problem solving the MILP problem written in attached file.
> I
> know that formulation is right, because it was solved with XPRESS
> commercial solver without any error or warning. But if I try to solve
> it with glpk it does not work. I also tried to change backtrack
> routines or some other MILP options, but it still does not wok. Is
> there any suggestion you coud give me? Or is it an hard problem for
> glpk (even if I don not think so)?
In your model:
a) some variables have huge bounds:
0 <= Pe_1_1_1 <= 1e+030
0 <= Pe_1_1_2 <= 1e+030
0 <= Pe_1_1_3 <= 1e+030
If you mean that these variables have no upper bound, do not
specify the bound at all.
b) there are used huge constraint coefficients (perhaps "big M"):
Pp_1_1: - 1e+030 DeltaPp_1_1 + Pp_1_1 <= 0
Pp_1_2: - 1e+030 DeltaPp_1_2 + Pp_1_2 <= 0
Pp_1_3: - 1e+030 DeltaPp_1_3 + Pp_1_3 <= 0
that makes the model badly formulated and causes numerical problems.
I removed the huge bounds and replaced the "big M" by 1e6. This
allowed me to run your model successfully (however, the solution
may be distorsed):
GLPSOL: GLPK LP/MIP Solver 4.39
Reading problem data from `Economical-1.lp'...
891 rows, 916 columns, 2619 non-zeros
120 integer variables, 118 of which are binary
2533 lines were read
ipp_basic_tech: 77 row(s) and 102 column(s) removed
ipp_reduce_bnds: 9 pass(es) made, 693 bound(s) reduced
ipp_basic_tech: 26 row(s) and 25 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 1 coefficient(s) reduced
glp_intopt: presolved MIP has 788 rows, 789 columns, 2311 non-zeros
glp_intopt: 114 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.200e-04 max|aij| = 1.000e+06 ratio = 8.333e+09
GM: min|aij| = 6.162e-01 max|aij| = 1.623e+00 ratio = 2.633e+00
EQ: min|aij| = 4.105e-01 max|aij| = 1.000e+00 ratio = 2.436e+00
2N: min|aij| = 2.102e-01 max|aij| = 1.440e+00 ratio = 6.851e+00
Constructing initial basis...
Size of triangular part = 788
Solving LP relaxation...
0: obj = 3.096653019e+02 infeas = 2.892e+02 (0)
* 37: obj = 1.776115222e+03 infeas = 7.312e-16 (0)
* 132: obj = 3.103305069e+02 infeas = 1.760e-28 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 132: mip = not found yet >= -inf (1; 0)
+ 139: >>>>> 3.104131270e+02 >= 3.104131270e+02 0.0% (5; 0)
+ 139: mip = 3.104131270e+02 >= tree is empty 0.0% (0; 9)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.1 secs
Memory used: 1.3 Mb (1410167 bytes)
Andrew Makhorin