6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You can watch the recent "Gurobi Tech Talk – Converting Weak to Strong MIP Formulations" gurobi.com/resource/… $\endgroup$
    – Mark L. Stone
    Apr 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$
    – Sune
    Apr 4, 2022 at 19:51

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @prubin , does tighter mean smaller feasibility space ? $\endgroup$
    – Optimization team
    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
5
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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