I built my model on Python and am passing it to Gurobi to solve the problem. The presolve phase of Gurobi cuts down ~80% of the integer/binary variables and I am wondering if I should rethink my formulation.
$\begingroup$
$\endgroup$
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
3
First of all, the log output of a solver should not change your mind about the formulation you use. Most of the times, one can not imagine how such geometric spaces look like and it is hard to guess the reason for these 'cuts'.
However, before formulating a MILP, I guess there are some steps one should follow. Depending on the comments/suggestions I get, I will append this list:
- Check if you really need binary/integer variables. I have a feeling that almost half of the IP projects I see around can be carried out with LP.
- Check if the IP is a totally unimodular problem. This is also a less-known property considering how big the outcomes are after LP reformulation. This can be a nice source to learn. Moreover thanks to the comments of Ryan Cory-Wright, we can add balanced matrix and perfect matrix. I think this can be generalized as 'perfect formulations', where more details can be found here.
- If you have a non-linear model, there are methods to linearize it. For example, if $x$ and $y$ are binary variables and if you have $xy = 0 $, you can formulate it as $x+y\leq 1$. There are numerous tricks, I have found such a list, but I don't see it now. If someone finds it please add it as a comment :)
answered May 30, 2019 at 23:21
-
4$\begingroup$ On point 2, it's worth noting that total unimodularity isn't the only condition which provides "nice" continuous relaxations. Other IPs which are "nice" include balanced en.wikipedia.org/wiki/Perfect_matrix and perfect en.wikipedia.org/wiki/Perfect_matrix matrices $\endgroup$ May 31, 2019 at 2:58
-
1$\begingroup$ @aslv95 Are there any presolvers which check (or can check) for (try to find) unimodularity, etc. and act accordingly? Or other tools which perhaps can show what portions of a model are preventing unimodulairty, etc.? $\endgroup$ May 31, 2019 at 13:53
-
1$\begingroup$ @MarkL.Stone I have just run across some packages to check if a matrix is totally unimodular, e.g., nl.mathworks.com/matlabcentral/fileexchange/… I don't know if a solver has this property, I will definitely look for it. But I think checking these special cases is NP-hard (correct me if I am wrong), therefore I don't think solvers will include this option. $\endgroup$ May 31, 2019 at 13:57
$\begingroup$
$\endgroup$
Complementing the other good answers, please note that presolve is concerned with problem input data and tries to eliminate variables using logical reductions. While a huge reduction in the number of variables as in your case might indicate that the model is not as compact as you would desire, input data could be the reason as well.
For example, consider a capacitated facility location problem where demand split (i.e., allocating a customer to more than one facility) is not permitted (this is simply modeled via binary variables for allocation decisions). If the demands of some customers were bigger than the capacities of some facilities, then the corresponding allocation decision variables would be eliminated during the presolve phase.
Considering the above, before further analysis of your formulation for possible enhancements, I suggest you solve your model with different input data and see whether your observation is consistent for a wider range of instances.
$\begingroup$
$\endgroup$
Removing variables and constraints in presolve is a good thing. It can make the model smaller by reasoning that some variables will never appear in an optimal/feasible solution.
You can think about creating a better model for your problem (e.g. tighter LP relaxation) but I wouldn’t worry that presolve is doing a good job.
$\begingroup$
$\endgroup$
One common case where presolve can remove a lot is if you have constraints of the form $x_i = 0$. In that situation, you can save time and memory by instead omitting $i$ from the index set of $x$. Sometimes such constraints appear in the original model in the more obfuscated form $\sum_i x_i \le 0$ with $x_i \ge 0$, but the same idea applies.
$\begingroup$
$\endgroup$
You can get the presolved model from Gurobi. Having a look at the variables before and after presolve might give you some interesting insights into which variables the presolver is removing.
I name my variables according to the schema variableName[42,1]. For the analysis I compare the number of variables per group pre- and post-presolve.
