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.