26
$\begingroup$

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?

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are there any guidelines for trading off between binary vs general integer variables? Let's say I have two formulations, one with $n$ general integer variables and the other with $N$ binary variables ($N > n$). Are there guidelines for which formulation is preferred, maybe as a function of $N/n$ or the range of the general integers (say, $0,\ldots,k$)? The answer likely depends on the number of constraints, so for simplicity, let's say the two formulations have around the same number of constraints. $\endgroup$ – Aleksandr Kazachkov Jul 2 '19 at 18:38
  • $\begingroup$ since for binary variables so much logic kicks in (propagation etc.) I would assume you always choose the binary program; do you have an example where an integer formulation is better, regardless of size? $\endgroup$ – Marco Lübbecke Jul 2 '19 at 19:54
  • 1
    $\begingroup$ This decision arose recently for me, but I did not test the two formulations against each other, and I am not sure it will make sense to do so in my setting, so the question was more from curiosity / theoretical interest. I formulated my problem with binary variables, but later found an earlier paper that worked on the same problem, had very experienced authors, and used the general integer formulation. I probably will try to implement the general integer version and see how it goes, though in the end I designed a bunch of heuristics that make the IPs typically trivial after presolve anyway. $\endgroup$ – Aleksandr Kazachkov Jul 2 '19 at 21:10
18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ On However the performance was orders(!!) of magnitude worse than before, because the original problem was symmetric, and the new one was not. Vs or.stackexchange.com/users/354/marco-l%c3%bcbbecke's answer avoid symmetric formulations I am extremely confused. $\endgroup$ – abhiieor Jul 1 '19 at 8:57
  • $\begingroup$ That’s exactly why you should test: sometimes symmetry really kills your performance, because the B&B doesn’t “know” where to go, another time it helps unearth underlying structures and speed up the performance. I was totally confused by that result (which is why I wrote the blog post about it) .Basically, you have to try. $\endgroup$ – Richard Jul 1 '19 at 10:58
  • $\begingroup$ Maybe another rule of thumb: symmetry in the objective function is bad. Symmetry in variables might be good. $\endgroup$ – Richard Jul 1 '19 at 11:01
10
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Mark is dead on. Also, regarding the inequality v. equality question, sometimes rounding error becomes a hazard. With an equality constraint, deviating from the RHS by more than the solver's tolerance in either direction can make a feasible solution look infeasible. With an inequality constraint, the hazard is only one one side, so you have possibly cut the risk of it. $\endgroup$ – prubin Jun 30 '19 at 17:51
  • $\begingroup$ Another argument I have come along in LP contexts for using inequality constraints rather than equality constraints is that by using inequality constraints, the dual variables are restricted to the positive domain, which may accelerate the solution process. I think this is why people often use a set covering formulation rather than a set partitioning formulation, even though all covering constraints hold with equality in an optimal solution. $\endgroup$ – Rolf van Lieshout Jul 1 '19 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.