8

When developing MILPs, often there are different alternatives possible to express a constraint. The question then arises, which of the alternatives is better, meaning, which alternative is expected to perform better during the solution process.

Is the scientific community able to provide a guide for addressing the strength of a MILP formulation? Something like "disciplined convex programming" but for strong MILPs, lets call it "disciplined MILP programming"?

Does, possibly, such a guide already exist?

Clement
  • 2,252
  • 7
  • 13
  • 4
    Integer and binary variables have a tendency to be "undisciplined" relaltive to solution difficulty. Not everything you want, but it is worth looking at "Practical guidelines for solving difficult mixed integer linear programs" by lEd Klotz and Alexandra M. Newman., if you can obtain a copy. – Mark L. Stone Jul 06 '21 at 17:51
  • 3
    As Mark says, IPs tend to be "undisciplined" (if not outright ornery). There are a few guidelines known to practitioners, some problem- or model-specific. For "big M" models, smaller values of M are generally preferable (provided they're not too small). For the TSP, the Miller-Tucker-Zemlin formulation tends to have a looser relaxation than the "stamp out cycles explicitly" approach, but the latter can blow up in size fairly quickly. – prubin Jul 06 '21 at 17:58
  • 1
    Dantzig-Wolfe (columnwise) formulations are at least as tight as "normal" formulations (this is proven). The counterpart is that it requires generating variables (columns) either beforehand or dynamically, which can be challenging. But the main idea is that the more "information" you have within your variables, the tighter the model will be. – Kuifje Jul 07 '21 at 11:52
  • @prubin if you agree, I suggest that you create a community wiki answer for this question as it seems people have something to contribute. – EhsanK Jul 11 '21 at 13:52
  • @EhsanK Done. I've put in a suggested layout (general comments, comments relating to logical constraints, problem-specific comments broken down by problem types) and stuck in a few low-hanging fruit. Hopefully others will add to it (and adapt the organization as necessary). – prubin Jul 12 '21 at 16:09

1 Answers1

7

Forum users are invited to post their suggestions for tighter/better formulations of mixed integer linear programming models here. The emphasis is on getting solutions (and closing the gap) efficiently, as opposed to model expressiveness (ease of users to see what is going on in the model).

General

Logical constraints

  • For "big M" models, smaller values of $M$ will reduce the likelihood of numerical problems and make the bounds tighter ... provided they are not too small. (Too small a value may cut off feasible, possibly optimal, solutions.)
  • While it is common to refer to "big M" in the singular, and authors like to use a single symbol $M$, in practice different constraints can and frequently should use different values of $M$. So, for example, $a^{(i)\prime} x \le b_i + M z_i$ ($z$ binary, $x$ continuous, $a$ and $b$ parameters) should be $a^{(i)\prime} x \le b_i + M_i z_i$, with $M_i$ chosen to make that particular constraint valid but as tight as possible.

Specific problem types

Traveling salesperson problem (TSP)

prubin
  • 39,078
  • 3
  • 37
  • 104