## Thursday, April 12, 2012

### Excluding a Solution

This is another frequently asked question in OR forums: How does one exclude an otherwise feasible solution from consideration in a mathematical programming problem? The answer is apparently well known to some but not as widely disseminated as one might hope.  I'll treat four cases. Note that, in all cases, what I say applies to both linear and nonlinear problems.

#### All variables divisible (continuous)

Short answer: you cannot. Excluding a single point from the feasible region renders it non-convex (or, if the point is an extreme point, at least not closed). That is the kiss of death for conventional optimization algorithms. Metaheuristics may still work, though.

#### All variables binary

This case is easy. Let $x \in \{0,1\}^n$ be your vector of decision variables, and let $\bar{x}$ be the solution you wish to exclude. Just add the constraint $$\sum_{i: \bar{x}_i =0}x_i + \sum_{i:\bar{x}_i =1}(1-x_i)\ge 1.$$ The only solution in $\{0,1\}^n$ that violates it is $x=\bar{x}$.

#### All variables general integer

This one is trickier. Let $x \in \mathbb{Z}^n$ be your vector of variables. If you are only going to exclude a single solution $\bar{x}$, and if $x$ is bounded (say $L_i\le x_i \le U_i$, $i=1,\dots,n$), you can introduce binary variables $y,z\in \{0,1\}^n$ of the same dimension as $x$, for a total of $2n$ new binary variables. Now add the constraints \begin{eqnarray*}x_i & \ge & \bar{x}_i+1+(L_i-1-\bar{x}_i)y_i \qquad \forall i \\x_i & \le & \bar{x}_i-1+(U_i+1-\bar{x}_i)z_i \qquad  \forall i\\ \sum_{i=1}^n (y_i+z_i) & \le & 2n-1.\end{eqnarray*} The only way $x=\bar{x}$ is if $y_i=1=z_i \forall i$, which the last constraint precludes.

On the other hand, if you plan to exclude a sequence of solutions, this gets prohibitively expensive in terms of the number of binary variables and number of constraints being added. It is probably more efficient approach simply to recode x in terms of binary variables. That is, for each $i=1,\dots,n$ write $$x_i=y_{i0}+2y_{i1}+\dots+2^ky_{ik_i}$$ where $k_i=\left\lceil{U_i}\right\rceil$ and the $y_{ij}$ are all binary. (For simplicity, I'm assuming $L_i\ge 0$ here, but the adjustment if $L_i<0$ is easy.) You now have all variables binary, which reduces to the previous case.

#### A mix of integer and divisible variables

We're back to being screwed. You can use one of the tricks above, applied to just the integer variables, to exclude a single solution and all other solutions with the same projection onto the subspace of divisible variables. Excluding just the one solution, however, cannot be done.