2
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ This is a vast topic. Search on "cutting planes". $\endgroup$ – Chris Godsil Nov 5 '11 at 16:37
3
$\begingroup$

I see that you have specified that $A x_0 \geq 0$ and $x_0 \in \{0,1\}^n$. Then the "simplest" cut is the so-called "no-good" cut, which just forces one of the components to change: $$ \sum_{j : (x_0)_j = 0} x_j + \sum_{j : (x_0)_j = 1} (1-x_j) \geq 1.$$ This will definitely cut off the corner of the hypercube $x_0$. (And only that corner of the hypercube). It is definitely not a "deep" cut in any sense of that word. A very nice paper with many more details, perhaps answering some of your other question is "Forbidden Vertices." https://arxiv.org/abs/1309.2545

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Amelio Vazquez-Reina Nov 5 '11 at 18:46
  • $\begingroup$ Good point, I had overlooked that. $\endgroup$ – Hans Engler Nov 5 '11 at 19:40
0
$\begingroup$

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$

$\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.