A slow MIP case. Need help on performance improvement

[wenjie]

Hi guys,

I am formulating a problem with Mixed integer programming and using Gurobi Optimizer to solve it. The number of variables in my problem is not that many (around 40,000 continuous variables and 500,000 binary variables) but it runs very slow. I wait for more than 1 hour and Gurobi is still on the search for the optimal result. I have used a smaller case to prove the optimality of my problem. Now I was to wonder if there is any method to speed up the searching.

The objective of my optimization problem is not natively linear. Generally speaking, it is like Min a1x1 + a2x2 + ...., where xi is a continuous variable equals min {b1y1 + b2y2 +...., c1z1 + c2z2 + ......, d1w1 + d2w2}, where yi, zi, wi are binary variables. I used the Big-M method to transfer the objective into the linear form with a lot of slack constraints. Therefore, as we could expect, there is a lot of dependency in this problem.

I am pasting the mlp.lp file of my smaller case test. In the code, I choose the following parameters to control the gurobi.

MIPGap = 1e-3

MIPFocus = 3

Method = 3

ImproveStartTime = 600

=================mlp.lp start============================

Gurobi 6.0.3 (linux64) logging started

Optimize a model with 2049 rows, 2580 columns and 7500 nonzeros

Coefficient statistics:

  Matrix range    [4e-03, 1e+03]

  Objective range [1e-02, 2e+01]

  Bounds range    [1e+00, 1e+00]

  RHS range       [8e-03, 3e+02]

Found heuristic solution: objective 6588.57

Presolve removed 240 rows and 240 columns

Presolve time: 0.03s

Presolved: 1809 rows, 2340 columns, 6840 nonzeros

Variable types: 180 continuous, 2160 integer (2160 binary)

Optimize a model with 1809 rows, 2340 columns and 6840 nonzeros

Solved with dual simplex

Solved in 1537 iterations and 0.09 seconds

Optimal objective  1.527599072e+00

Root relaxation: objective 1.527599e+00, 1537 iterations, 0.06 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work

 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0    1.52760    0  820 6588.56554    1.52760   100%     -    0s

H    0     0                    3623.1937965    1.52760   100%     -    0s

     0     0    2.01065    0 1267 3623.19380    2.01065   100%     -    0s

     0     0    2.21425    0 1144 3623.19380    2.21425   100%     -    1s

H    0     0                     314.0010533    2.21425  99.3%     -    1s

H    0     0                     296.5673143    2.21425  99.3%     -    1s

     0     0    2.50597    0  966  296.56731    2.50597  99.2%     -    1s

H    0     0                     209.9892590    2.50597  98.8%     -    1s

     0     0    2.74531    0  870  209.98926    2.74531  98.7%     -    2s

H    0     0                     170.3005163    2.74531  98.4%     -    2s

H    0     0                       3.4641783    2.74531  20.8%     -    2s

     0     0    2.86420    0  747    3.46418    2.86420  17.3%     -    3s

H    0     0                       3.3736497    2.86420  15.1%     -    3s

     0     0    2.94298    0  679    3.37365    2.94298  12.8%     -    3s

H    0     0                       3.3316109    2.94298  11.7%     -    3s

     0     0    2.98701    0  620    3.33161    2.98701  10.3%     -    4s

     0     0    2.98701    0  614    3.33161    2.98701  10.3%     -    4s

H    0     0                       3.3132839    2.98701  9.85%     -    4s

H    0     0                       3.2579026    2.98701  8.31%     -    5s

.........

.........

42120 36999    3.20580   32  385    3.22355    3.16761  1.74%  25.2   95s

 44532 39132    3.21406   38  334    3.22355    3.16837  1.71%  25.4  100s

 47222 41484    3.20022   37  333    3.22355    3.16942  1.68%  25.6  105s

 49687 43570    3.17237   26  451    3.22355    3.16992  1.66%  25.9  110s

 52378 46089    3.22109   69  237    3.22355    3.17096  1.63%  26.1  115s

 54759 48216    3.18033   32  366    3.22355    3.17148  1.62%  26.2  120s

 57136 50319    3.20962   54  239    3.22355    3.17212  1.60%  26.4  125s

H58512 50970                       3.2232280    3.17230  1.58%  26.4  128s

H58948 51344                       3.2232279    3.17239  1.58%  26.4  129s

 59341 51671    3.21164   33  385    3.22323    3.17251  1.57%  26.4  130s

H59606 51919                       3.2232272    3.17252  1.57%  26.4  130s

 61667 53753    3.21584   38  327    3.22323    3.17309  1.56%  26.5  135s

 63843 55637    3.21701   66  249    3.22323    3.17358  1.54%  26.5  140s

........

.......

 154251 132104    3.20739   34  384    3.22273    3.18251  1.25%  29.6  350s

 156091 133642    3.20047   35  357    3.22273    3.18265  1.24%  29.6  355s

 158388 135605    3.19372   39  349    3.22273    3.18277  1.24%  29.6  360s

 160159 137103    3.21096   47  301    3.22273    3.18288  1.24%  29.7  365s

 162260 138884    3.21670   36  339    3.22273    3.18303  1.23%  29.7  370s

 164030 140382    3.20577   28  407    3.22273    3.18316  1.23%  29.8  375s

 166152 142177    3.21956   63  258    3.22273    3.18330  1.22%  29.8  380s

.......

========================mlp.lp end=============================

as you can see, the bound updates very slow. I was to wonder if there is any method to improve the speed or is there any suggestion on changing the formulation.

(BTW, all coefficients are double type.)

Thank you very much.

[Tobias Achterberg]

The kind of objective function that you are modeling is one of the biggest
challenges in MIP solving: minimize a minimum of several terms. A min-max is
much easier, because this can be formulated using a single auxiliary variable
that is constrained to be larger or equal to each of the term. But, as you have
done it, for min-min you need to introduce big-M or indicator formulations that
the auxiliary variable is larger or equal to at least one of the terms. This
makes the LP relaxation of the problem very weak, and, consequently, the MIP
very hard to solve.

Secondly, 500,000 binary variables is by no means small. Gurobi can solve larger
problems if they are "easy" from a combinatorial point of view, but you are
combining a pretty large problem with a very difficult combinatorial structure.
I don't think that todays solver technology is able to deal with this.

Actually, we are very interested in challenging problems like yours. So, if you
are allowed to share your model it would be great if you could upload some of
your models, in particular the smaller ones that are still challenging to solve.
If they are small enough, just send them to me by email (achterberg at gurobi
dot com); if they are too large for email, I can enable the upload functionality
for your account at gurobi.com.


Regards,

Tobias