Problem Detail: 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$ ?
Asked By : Manuel Lafond
Answered By : David Nehme
There are no hard rules for which formulation would be better especially for mixed-integer problems, however the following things are correlated
- The number of nonzeros in the constraint matrix and time to solve lp relaxations
- The tightness of the lp relaxation and 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37459 Ask a Question Download Related Notes/Documents
