# Guides for strong MILP Formulations

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?

• 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. Jul 6 at 17:51
• 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. Jul 6 at 17:58
• 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. Jul 7 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 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). Jul 12 at 16:09

• 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.