Best way to solve many similar feasibility problems consecutively in MILP?

[FANG Colin]

I have a feasible base Integer LP model  with roughly 2000 variables & 3000 constraints.

Given a small set of variables with some particular intervals, (e.g. a in 1:6, b in 2:7, c in -3:5), I would like to query how many combinations are feasible with the base model.

At the moment, I have to try each combination, with

- add constraints to base model (either by constraint like a = 2, or by fixing the lower/upper bound of the variable )

- solve it, see if it is feasible.

- Reset the modified model to the original state.

In this particular case, I have to run solver 6 * 6 * 9 times.

It takes on average about 0.02 sec on each solve. So if there are 10000 feasible combinations, it takes at least 10000 * 0.02 = 3 mins.

Is there any way I can speed it up? What's the best way to tackle such problems?

I noticed that for each solve, Gurobi has to do a presolve which takes at least 80% of the total solving time.

Is there any way I can reuse the presolved model, (i.e. modify the bounds / add constraints upon the presolved model)?

The following is a typical presolve.

Optimize a model with 2077 rows, 2016 columns and 5581 nonzeros

Coefficient statistics:

  Matrix range    [1e+00, 2e+04]

  Objective range [0e+00, 0e+00]

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

  RHS range       [5e-01, 2e+04]

Presolve removed 1772 rows and 1797 columns

Presolve time: 0.01s

Presolved: 305 rows, 219 columns, 879 nonzeros

[FANG Colin]

I found a similar post 

https://groups.google.com/forum/#!searchin/gurobi/dualreductions/gurobi/N_BhoKKmiSc/dekZ8GdZBwAJ

Is there anything in addition I can apply in my case?

[Tobias Achterberg]

As suggested in the thread you refer to, the probably fastest way to achieve
what you want is to use a lazy constraint callback:

Set the "LazyConstraints" parameter to 1 (which implicitly disables dual
presolve reductions) and add a lazy constraint callback. In there, whenever a
new feasible solution candidate arrives, you reject it by adding a lazy
constraint that cuts off exactly this solution. Internally you increment a
counter. Finally, when Gurobi finishes and tells you that the model is
infeasible (you have rejected all solutions), then your counter will be the
number of different feasible solutions that exist.

Of course, this only makes sense for integer variables, because if there are
continuous variables involved than there are often an infinite amount of
different feasible solutions.

Rejecting a solution with general integer variables using linear constraints is
not so easy if the solution value of a variable is in the interior of its
domain. Hence, for your case, if you have relatively small intervals that you
want to evaluate, you should consider to replace the integer variable in your
model with a set of binary variables, for example using a logarithmic expansion:
y = x0 + 2x1 + 4x2 + 8x3 + ... Then, you can formulate your constraints that
rule out a single solution on the binary x variables.


Regards,

Tobias