If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why?

  • 5
    $\begingroup$ If you have an exponential number of them (e.g., for the TSP, the set of constraints that forbid cycling), then you have a problem. $\endgroup$
    – Kuifje
    Dec 6 '21 at 12:30
  • 3
    $\begingroup$ The number of constraints may indicate how well the formulation will scale. For a given problem, a formulation with $O(n)$ constraints might work better than a formulation with $O(n^2)$ constraints for large problems even if the second formulation is tighter. See for example the various formulations for the clique problem "Worst-case analysis of clique MIPs" (Naderi et al., 2021) DOI PDF $\endgroup$
    – fontanf
    Dec 6 '21 at 15:05

In academic publications (where the point is to present a model and possibly computational scheme to solve an actual problem) I typically do not bother to count the constraints. First, the reader can do it themselves from the algebraic formulation. Second, the reader is more interested in whether "realistic" instances of problem are solvable with "reasonable" hardware in "reasonable" time, which they find out in the experimental results.

I do agree with the comment that formulations requiring an exponential number of constraints are potentially problematic, if there is a need for them to scale. I say "if" because in some cases you are presenting computational results for problems of the size that users will likely encounter. For instance, if you are creating bus routes for school children, the fact that computation time blows up as the number of kids attending the school tends to infinity is probably not very relevant.


I agree with @prubin on academic publications.

However if your audience consist of "laymen", e.g. when working as a consultant, a discussion can be helpful: Providing insight into how a change of parameters affects the number of constraints (and more importantly: the number of decisions to be made, i.e. the number of variables) helps them to get a better understanding of the complexity of the underlying problem.

Reconsidering @prubin's example: One could present a table showing the number of constraints (and variables) for 5, 10, 20, .... school children.


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.