Suppose we have a MILP model. How can we say this model is tight or not? How to make it more tight? Any advice or example?
1$\begingroup$ You can watch the recent "Gurobi Tech Talk – Converting Weak to Strong MIP Formulations" gurobi.com/resource/… $\endgroup$– Mark L. StoneApr 4, 2022 at 19:42
2$\begingroup$ It would generally say that tightness of a model is usually relative to another model. Of course, if there is no optimalitet gap, then it is tight in itself. But maybe that is just my way of thinking about it $\endgroup$– SuneApr 4, 2022 at 19:51
I agree with @Sune: tightness generally means the difference between the integer and convex hulls (so, in practical terms, the gap between the optimal solution and the solution of the LP relaxation), and judging it is typically in comparison to other models for the same problem.
As to how to tighten a model, there are no universal recipes that I've ever seen. In a "big M" type model, smaller (but adequately large) values of $M$ will tend to yield tighter models. Seemingly redundant constraints sometimes result in tighter relaxations (possibly by virtue of leading the presolver to a reduction it might not otherwise have found), but there are no guarantees there. Sometimes redundant constraints are just redundant.
When there are multiple distinct formulations of the same problem, sometimes one will be provably tighter than another. A case in point is the traveling salesman problem. A model with subtour elimination constraints, while larger, is typically tighter than a model using the Miller-Tucker-Zemlin formulation.
$\begingroup$ Thanks @prubin , does tighter mean smaller feasibility space ? $\endgroup$ Apr 5, 2022 at 9:56
1$\begingroup$ A reduction in the set of integer feasible solutions (without losing the optimum) would definitely make the model "tighter", but the term is used more broadly. So if models A and B have the same feasible sets but the continuous relaxation of A is smaller than the continuous relaxation of B, A would typically be considered "tighter". $\endgroup$– prubin ♦Apr 5, 2022 at 15:35
On a theoretical level, you can define tightness as the difference in volume of the feasible space between the LP relaxation and the original MIP. This is a mostly theoretical point though as in practice you have no real way of calculating this volume; also, solvers will add cutting planes to reduce this volume during the solution process.
Therefore, a more practical definition is the fact that there is a gap between the LP relaxation and the MIP solution that is not easily closed. The word "easily" here refers to standard presolve and cutting plane techniques such as MIR cuts, bound strengthening etc. This also means that you often only know that a model formulation is weak once you try to solve it and the log output of the solver shows you something like this:
0 0 72.70714 0 85 - 72.70714 - - 0s 0 0 72.70714 0 162 - 72.70714 - - 0s 0 0 72.70714 0 125 - 72.70714 - - 0s 0 0 72.70714 0 99 - 72.70714 - - 0s 0 0 72.70714 0 81 - 72.70714 - - 0s 0 2 72.70714 0 79 - 72.70714 - - 0s H 1774 804 80.0000000 72.70714 9.12% 11.8 0s H 1866 791 78.0000000 72.70714 6.79% 12.0 0s H 1869 783 77.0000000 72.70714 5.58% 12.0 0s H 2073 456 75.0000000 72.70714 3.06% 12.4 1s H 2106 446 74.0000000 72.73393 1.71% 21.0 3s H 2340 493 73.0000000 72.73393 0.36% 25.7 4s
I have found that if you want to tighten your model formulation, you should first try to increase the aggressiveness of cuts added by the solver (Cuts = 3 in Gurobi for example), as well as adding cuts manually that are problem specific.
Then of course you can change your model, which is though easier said than done. @prubin's example of a TSP is a good one here. Finally, you may even ask whether you can maybe change your entire approach: do you need all the variables to be integer? Can you apply some column generation or other advances techniques? Can you sacrifice some accuracy for a dramatic improvement in runtime?
I'm sorry to hear that you did not find our Tech Talk very useful. Can you elaborate what we could have done to make it more interesting to you?