Enumerate all solutions to integer programming problem

Question

How can I list all feasible solutions to an integer program? Is there an algorithm whose running time is reasonably related to the total number of such solutions?

Answer 1

It's possible to enumerate all solutions, using a recursive algorithm that repeatedly invokes an integer programming solver. Basically, at each step, you pick a variable, find its range of feasible values, partition its range into two subranges, and then recursively enumerate solutions that fall into each subrange.

In pseudocode, the algorithm looks like this ($\mathcal{P}$ is an integer programming instance):

EnumSolns($\mathcal{P}$, $M$):

1. Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$. (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)

2. Let $a$ denote the smallest feasible value for $x$ (found using a call to the IP solver). Let $b$ denote its largest feasible value (another call to the IP solver).

3. Recursively call EnumSolns($\mathcal{P} \cup \{x=a\}$, $M \cup \{x\}$).

4. If $a<b$, recursively call EnumSolns($\mathcal{P} \cup \{a+1 \le x \le b\}$, $M'$) where $M'=M \cup \{x\}$ if $a+1=b$, or $M'=M$ otherwise.

To enumerate all solutions to an integer programming problem $\mathcal{P}$, call EnumSolns($\mathcal{P}$, $\emptyset$). If $s$ denotes the total number of solutions and $n$ the number of variables, the running time will be at most $O(ns)$ calls to the IP solver.

In practice, various optimizations may be possible. Some IP solvers support pushing and popping inequalities, and can remember facts that were learned during a search for the previous system of inequalities and make use of them after pushing another inequality; this may speed up this algorithm substantially.

For a 0-1 integer program, there is a simpler recursive algorithm:

Enum01Solns($\mathcal{P}$, $M$):

1. If $\mathcal{P}$ is not feasible (determined with a call to the IP solver), return.

2. Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$. (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)

3. Recursively call Enum01Solns($\mathcal{P} \cup \{x=0\}$, $M \cup \{x\}$) and Enum01Solns($\mathcal{P} \cup \{x=1\}$, $M \cup \{x\}$).

If you just want to count the number of feasible solutions to the integer program, without listing them, see Finding all solutions to an integer linear programming (ILP) problem.