Re: [Help-glpk] Write MIP model, read MIP model and then it's easy again!

[Andrew Makhorin]

Hi Pavel,

Looks like the pseudo-cost branching --pcost helps:

GLPSOL: GLPK LP/MIP Solver, v4.43
Parameter(s) specified in the command line:
 --glp hard.glpk --pcost -o hard.sol --log hard.log
Reading problem data from `hard.glpk'...
2275 rows, 1565 columns, 5550 non-zeros
1565 integer variables, all of which are binary
7838 lines were read
GLPK Integer Optimizer, v4.43
2275 rows, 1565 columns, 5550 non-zeros
1565 integer variables, all of which are binary
Preprocessing...
660 hidden packing inequaliti(es) were detected
1002 hidden covering inequaliti(es) were detected
2262 rows, 1563 columns, 5526 non-zeros
1563 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 2262
Solving LP relaxation...
GLPK Simplex Optimizer, v4.43
2262 rows, 1563 columns, 5526 non-zeros
      0: obj =   0.000000000e+00  infeas =  5.000e+02 (0)
    500: obj =   0.000000000e+00  infeas =  1.475e+02 (0)
*   853: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*   870: obj =   5.000000000e+02  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   870: mip =     not found yet <=              +inf        (1; 0)
Pseudocosts initialized for 368 of 439 variables
+   872: mip =     not found yet <=   5.000000000e+02        (2; 0)
+  1055: mip =     not found yet <=   5.000000000e+02        (56; 0)
+  1199: >>>>>   2.500000000e+02 <=   5.000000000e+02 100.0% (152; 0)
+  1299: mip =   2.500000000e+02 <=     tree is empty   0.0% (0; 303)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   21.1 secs
Memory used: 3.7 Mb (3923070 bytes)
Writing MIP solution to `hard.sol'...

GLPSOL: GLPK LP/MIP Solver, v4.43
Parameter(s) specified in the command line:
 --glp impossible.glpk --pcost -o imposs.sol --log imposs.log
Reading problem data from `impossible.glpk'...
1889 rows, 1548 columns, 4782 non-zeros
1548 integer variables, all of which are binary
6816 lines were read
GLPK Integer Optimizer, v4.43
1889 rows, 1548 columns, 4782 non-zeros
1548 integer variables, all of which are binary
Preprocessing...
46 hidden packing inequaliti(es) were detected
1006 hidden covering inequaliti(es) were detected
1619 rows, 1546 columns, 4244 non-zeros
1546 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 1619
Solving LP relaxation...
GLPK Simplex Optimizer, v4.43
1619 rows, 1546 columns, 4244 non-zeros
      0: obj =  -7.031250000e+01  infeas =  4.080e+02 (0)
    500: obj =   4.804687500e+02  infeas =  1.300e+01 (0)
*   935: obj =   4.804687500e+02  infeas =  0.000e+00 (0)
*  1000: obj =   1.160156250e+03  infeas =  0.000e+00 (0)
*  1194: obj =   1.233017113e+03  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+  1194: mip =     not found yet <=              +inf        (1; 0)
Pseudocosts initialized for 286 of 650 variables
Pseudocosts initialized for 563 of 650 variables
+  1200: mip =     not found yet <=   1.231649926e+03        (2; 0)
+  1628: mip =     not found yet <=   1.222079613e+03        (8; 0)
+  1738: >>>>>   1.000000000e+03 <=   1.222079613e+03  22.2% (13; 0)
+  2354: >>>>>   1.070312500e+03 <=   1.196493676e+03  11.8% (21; 12)
+  6408: mip =   1.070312500e+03 <=   1.070907738e+03 < 0.1% (43; 155)
+ 11085: mip =   1.070312500e+03 <=   1.070907738e+03 < 0.1% (2; 377)
+ 11802: mip =   1.070312500e+03 <=     tree is empty   0.0% (0; 519)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   46.1 secs
Memory used: 3.1 Mb (3224776 bytes)
Writing MIP solution to `imposs.sol'...

I also noticed tiny objective coefficients in 'impossible' model:

a 0 19 7.44320660294296e-015
a 0 22 3.22335907962733e-018
a 0 23 -3.22658566529263e-021
a 0 37 3.22335907982908e-018
a 0 48 3.22335907972821e-018
a 0 68 3.22335907962733e-018
a 0 71 3.22335907967777e-018

This may cause numerical difficulties, so I recommend you to replace
such coefficients by exact zeros.

>> If you add rows to exclude solutions, which for some reasons are not
>> suitable for you, it would be more efficient to add such rows to the
>> formulation as early as possible (ideally to the initial formulation)
>> rather than at the end when the search is finished. I mean "lazy"
>> constraint generation.
>>
> I'm trying exactly this, i.e., to generate constraints as eagerly as
> possible. The thing is that my MIPs are really approximations of the
> real domain-specific constraints. The approximations are iteratively
> refined by adding new rows as soon as possible.

> However, I'm slightly surprised now as you told me the other day that
> GLPK does *not* keep the b&c tree after returning from the glp_intopt,
> didn't you? I thought it starts from scratch every time, so it
> shouldn't matter how I obtained the model. What am I missing?

Probably I misunderstood you.

The lazy constraint generation technique assumes generating rows
during the search by means of the user-defined callback routine called
from glp_intopt, *not* when the search has been finished. If glp_intopt
has returned, the search is finished and the search tree is empty, so
if you add rows at that point, there is no way other than solving the
instance from scratch.

You may look at an example attached to following message:
http://lists.gnu.org/archive/html/help-glpk/2010-01/msg00117.html
which demonstrates this technique.

> Either way, attached are two models in the GLPK format. hard.glpk is
> the one I was talking about - it's solved easily after writing in a
> file and reading back (btw, if I write it in CPLEX format then it's
> solved 2x faster on my machine!). impossible.glpk can't be solved
> within 5 mins on my machine. If you could solve it with some
> combination of input arguments, will you tell me? I tried the
> feasibility pump but it's never applied after a certain point,
> probably because simplex gets stuck (not sure).

Please post me the terminal output.


Best regards,

Andrew Makhorin