1
$\begingroup$

This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation. Most people try to reach the minimum number of constraints/variables, but I couldn't find anything that considers the size of the constraints.

In more concrete terms, I have some maximization problem for which I can make two different formulations $A$ and $B$. Both have $O(n^2)$ variables, $n$ being the size of the input.

Formulation $A$ has $O(n^3)$ constraints, each having a constant number of variables (say each constraint is a summation over four variables).

Formulation $B$ has $O(n^2)$ constraints, but many constraints are of linear size - i.e. they include summations over $O(n)$ variables.

In terms of performance, does $B$ have an advantage over $A$ ?

$\endgroup$
3
$\begingroup$

There are no hard rules for which formulation would be better especially for mixed-integer problems, however

  • The time to solve an lp relaxation usually increases with the number of nonzeros in the constraint matrix, but
  • Tighter lp relaxations usually reduce the number of lp relaxations that need to be solved.

To take your example, suppose you have a variable $y$ that is 1 only if all variables $x_0, x_2, \ldots, x_{n-1}$ have value 1, and all values are binary. You could write a single constraint $$ny \le \sum_{i=0}^n x_i$$

or $n$ constraints $$y \le x_i, \forall i \in \{0, \ldots n-1\}$$

Both sets of constraints will have the same integer-feasible set, but the $n$ constraints have a much smaller continuous-feasible set, so it is probably be much faster to solve.

$\endgroup$
  • 1
    $\begingroup$ So I guess in the end, only empirical tests will tell me if one is better than the other. Thank you for your answer. $\endgroup$ – Manuel Lafond Jan 22 '15 at 18:43

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.