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.