"Best practices" for formulating MIPs

Question

Often there are many alternatives ways for formulating a MIP. For example:

1. The model contains inequality constraints that must hold with equality in an optimal solution.
2. The model contains continuous variables that will necessarily be integer in an optimal (or just integer feasible) solution.
3. The model contains variables that have a value of at most 1 in an optimal solution.

In these cases, the modeler can decide whether to (1) include the constraints as equality constraints or not, (2) declare the variables as integer or continuous variables and (3) to declare the variables with upper bounds of 1 or not. When using commercial solvers, I have noticed that the performance may vary significantly dependent on such choices. Hence, I am wondering whether there are any rules of thumb for formulating MIPs in solvers. More generally, what information is valuable to solvers and what information may even hurt performance?

Answer 1

This is an extremely interesting question. I agree with @Richard that you have to try it out. I have seen that tiny changes to a model can make huge differences, but in my experience, more general changes to a model may have more impact in the end. There are, I think, some guidelines that may help, from algorithmics and theory.

Why do we choose "big $M$ as small as possible" (so, in fact, we look for small $M$)? Because we know that the LP based B&B algorithm which solves our MILPs can benefit from a better bound. Then again, since we know that big $M$ usually gives horrible relaxations, we try to avoid it altogether. A reformulation may help, maybe at the expense of investing more variables. Maybe too many, in that case, you would need a different algorithm (like dynamic variable or constraint generation). In my view, the model and the algorithm (may) go hand in hand. General observations:

• use binary variables instead of general integers
• avoid symmetric formulations
• think of completely different representations of a solution (eg in the cutting stock problem, variables can represent (a) how often an item is cut from a particular roll, or (b) an entire cutting pattern given as non-negative integer numbers, or (c) an entire cutting pattern given as a path in an acyclic network, or or or.
• look at the LP solution in the root node: anything you "see" that the LP is allowed to do that would be forbidden for the IP? May give an extra constraint. Or a cutting plane.

It may happen that the vanialla solver on an ugly model is still faster than a specialized solver on the elaborate model, and this is frustrating at first, but then we realize that this is what drives solver development.

Answer 2

I’m assuming that we want our models to be solved as quickly as possible. If that is the case, then the honest answer is: you need to try the models out and see.

To give you a concrete example (see here): through what I thought was a super-clever reformulation, I was able to remove 85% of the variables in the problem, and I thought that this would make it super fast. However the performance was orders(!!) of magnitude worse than before, because the original problem was symmetric, and the new one was not.

I always try to put the tightest upper bound I have, make my big-M as small as possible, use continuous over binary/integer when I can, but honestly, you cannot know anything for sure until you test it.

Answer 3

Perhaps you are only talking about MILPs, but you don't say, so I will say something of interest for MINLPs.

Regarding point 1:

• Suppose your model has a convex nonlinear inequality constraint, $f(x) \le c$, i.e., $f(x)$ is convex.

and

• It is known that the constraint will be active at the optimum, of any continuous relaxation i.e., $f(x) = c$, for instance because the continuous relaxations are concave programs with compact constraints, thereby having global optimum at an extreme of the constraints

Then you are usually better off entering the constraint as an inequality rather than as an equality. That is because the inequality constraint is convex, and generally much easier for an optimizer to deal with than a nonlinear equality constraint, which is a non-convex constraint. You might think you'd be doing the optimizer a favor by specifying the equality constraint, thereby cleaving off $f(x) < c$ from consideration, but such a "favor" will usually backfire.

However, in the case of a linear equality constraint known to hold with equality at the optimum of the original problem, or a continuous relaxation, I think it would generally be better, and in any event, not worse (except for (un)lucky "stars aligning" cases), to specify such a linear constraint as an equality constraint.

Regarding point 3, I have a pretty hard time imagining it would be better to not provide an upper bound of 1 than to provide it when you know the optimal variable value is at most 1. But I suppose for some particular model and solver, the stars could always align such that specifying such an upper bound slowed things down.

I will leave others to comment on point 2.

Answer 4

In addition to previous answers, I like to cite the following book, which discuss in details several different options (and kind of good practices) to model different common applications:

Model Building in Mathematical Programming, by H. Paul Williams. March, 2013. ISBN: 978-1-118-44333-0.

Every chapter is very interesting and is worth of (re)reading several times.