Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say we have a binary linear programming problem:

\begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & &\mathbf{Ax} \ge 0 \\ \end{aligned} \end{equation*}

with $c \in \mathbb{R}^N$ (a cost vector), $\mathbf{x} = (x_1, \ldots, x_{N}) \in \{0,1\}^{N}$ (representing solutions to the problem), and $A \in \mathbb{Z}^{m \,x\, n}$, a matrix that defines the feasible set of binary solutions.

Say we would like to make a specific solution $\mathbf{x_o}$ unfeasible in the problem above. What set of inequalities can we add to the original problem to accomplish this? (i.e. what would be a valid "cutting plane" that would preserve all the other solutions and exclude $\mathbf{x_o}$?)

Is there a way to do this without adding extra variables?

Finally, and loosely speaking, what would be the "most compact" set of additional inequalities that once added to the problem would accomplish this goal? (compact in the sense of having the least number of inequalities and variables participating in them).

Addendum:

A generalization of the problem above would be to exclude solutions $\mathbf{x}$ whose projections on a specific set of indices $\left({i_1, \ldots, i_k}\right)$ with $k\le N$ are $\mathbf{y_0}$. A solution to this would apply to the original problem above by making the set of indices $\left({i_1, \ldots, i_k}\right) = \left(1, \ldots N \right)$

For a particular example, say $\mathbf{x}$ has ten dimensions (i.e. $\mathbf{x}$ are binary vectors of length ten), and that we want to remove from the problem all vectors $\mathbf{x}$ whose first five coordinates are $\left(0,1,0,1,1\right)$


Notes:

  • Since $\mathbf{x_o}$ is a solution to the original problem it cannot be in the interior of the convex hull of solutions of the original problem.
share|improve this question
    
This is a vast topic. Search on "cutting planes". –  Chris Godsil Nov 5 '11 at 16:37

3 Answers 3

This can Be Done. The Trick is to Think of an objective which clearly maximizes the x_i. For x_i = 0 choose c_i = - 1, for x_i = 1 choose c_i = 1. the given Point is clearly the only Point with maximizes this Objective. So we restrict the "objective" only excluding the One Point.

Naturally this can also Expanded to projections.

share|improve this answer

If $\mathbf{x}_0$ is in the interior of the convex hull of all feasible binary solutions, it can't be done. Adding linear inequalities will always result in a convex subset of the relaxed problem (where $\mathbf{x}$ can be a real vector). If you eliminate $\mathbf{x}_0$ with inequalities from the feasible set, you'll also eliminate other feasible solution with binary entries.

share|improve this answer
    
Thanks @Hans. I believe that by definition since $\mathbf{x_0}$ is a solution to the original problem, $\mathbf{x_0}$ cannot be in the interior of the convex hull, since all $\mathbf{x}$ are a binary vectors and a binary vector cannot be represented as a convex combination of other binary vectors. In any case I'll clarify that $\mathbf{x_0}$ is a binary vector that was a solution to the original problem –  user815423426 Nov 5 '11 at 18:46
    
Good point, I had overlooked that. –  Hans Engler Nov 5 '11 at 19:40

I think $\mathbf{x}_0^T\mathbf{x}\leq\mathbf{x}_0^T \mathbf{x}_0-c$ for an appropriate positive constant $c$ should do the trick.

This is a deep cut that singles out the half-space on one side of the line perpendicular to $\mathbf{x}_0$

Might need to change $\leq$ to $\geq$ depending on which side of the line is the interior. In that case, $-c$ changes to $+c$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.