Re: [Help-glpk] Help regarding MILP problem

[Andrew Makhorin]

> I have a 0-1 MIP formulation of a file scheduling problem. The variables
> are all 0-1. When I run it using standard approach (as a MIP problem)
> using glpsol on the command line, it runs for a long time.

Try specifying the option --intopt that enables the mip presolver.
This signficantly reduces the running time for your instance:

lpx_read_cpxlp: reading problem data from `problem_data.lpt'...
lpx_read_cpxlp: 1132 rows, 496 columns, 3432 non-zeros
lpx_read_cpxlp: 496 integer columns, 495 of which are binary
lpx_read_cpxlp: 2196 lines were read
ipp_basic_tech:  451 row(s) and 180 column(s) removed
ipp_reduce_bnds: 2 pass(es) made, 4 bound(s) reduced
ipp_basic_tech:  12 row(s) and 4 column(s) removed
ipp_reduce_coef: 2 pass(es) made, 28 coefficient(s) reduced
lpx_intopt: presolved MIP has 669 rows, 312 columns, 2099 non-zeros
lpx_intopt: 312 integer columns, 311 of which are binary
lpx_adv_basis: size of triangular part = 669
Solving LP relaxation...
      0:   objval =   3.000000000e+00   infeas =   1.000000000e+00 (0)
    168:   objval =   9.000000000e+00   infeas =   3.589083054e-19 (0)
*   168:   objval =   9.000000000e+00   infeas =   4.163336342e-17 (0)
*   200:   objval =   6.333333333e+00   infeas =   2.704506029e-15 (0)
*   320:   objval =   3.014284257e+00   infeas =   1.110223025e-15 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Objective function is integral
+   320: mip =     not found yet >=              -inf        (1; 0)
. . . . .
+ 34137: mip =   5.000000000e+00 >=   4.000000000e+00  20.0% (10; 5223)
+ 34627: mip =   5.000000000e+00 >=     tree is empty   0.0% (0; 5361)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   46.0 secs
Memory used: 1.7M (1807748 bytes)