Tuesday, May 17, 2016

Finding all solutions of a system of linear inequalities I

In this post the following system of linear inequalities was presented:
\[\boxed{\begin{align} &3 \le 5x_1+3x_2+3x_3+5x_4 \le 5 \\ &0 \le x_2+x_3 \le 1 \\ &0 \le x_1+x_4 \le 1 \\ &1 \le 3x_3+5x_4 \le 3 \\ &0 \le 5x_1+3x_2 \le 2 \\ &0 \le x_1,x_2,x_3,x_4 \le 1 \end{align}}\]
It was noted we can use linear programming (using a dummy objective) to find one solution (if it exists), The question came up: can we find all solutions? Similar questions are asked many times. There are at least a few possible answers to this question:
  1. If the \(x_j\) are continuous variables, then a system of inequalities has zero, one or infinitely many solutions. Enumerating all of them is of course out of the question.
  2. Should you even want multiple solutions? It may be better to introduce an objective that implements how we should weigh the different solutions, and thus allows us to pick the best one.
  3. In linear programming we have concept of corner points. Those points we can enumerate. There are finitely many of them but in practice there may be too many of them to enumerate all of them. Here we try this out on this problem.
  4. If we can restrict the solutions to be integers, things become simpler. Now it is possible to enumerate all of them using some MIP tricks, or we can use constraint programming tools that provide this functionality out-of-the-box.
This system is small enough to try out a few things.