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.

No comments:

Post a Comment

If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on OR-Exchange.