2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.