If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why?
$\begingroup$
$\endgroup$
2
-
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$– KuifjeDec 6, 2021 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$– fontanfDec 6, 2021 at 15:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
