help-glpk
[Top][All Lists]

## 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)?

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
891 rows, 916 columns, 2619 non-zeros
120 integer variables, 118 of which are binary
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...
+   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

```