# Finding a maximum violated infeasible subset

Given a binary optimization problem of the following form:

\begin{align} min\; &cx&\\ &Dx \leq e&\\ &\sum_{i\in S} x_i \leq r(S) &\forall S\in \mathbb{S}\\ &x_i binary &\forall i\in N \end{align}

The set $$\mathbb{S}$$ is the family of all infeasible subsets, i.e. all infeasible combinations of items $$i$$. For every $$S\in \mathbb{S}$$ we have $$\sum_{i\in S} x_i \leq r(S)$$, where $$r(S)$$ is the maximum number of items that can be selected from $$S$$ in any feasible solution. Note that because $$S$$ is an infeasible subset, it must hold that $$r(S) \leq |S|-1$$. For a given $$S\in \mathbb{S}$$, it's possible to compute $$r(S)$$ via a simple MIP. The family $$\mathbb{S}$$ is however exponentially large so it's not possible to precompute the entire set, so the intend is to add these constraints through a cutting plane procedure.

For a given LP solution $$\bar{x}$$, I would like to verify whether there exists a set $$S\in \mathbb{S}$$ for which the constraint is violated. More precisely, I'd like to find the set $$S'$$ that maximizes the violation: $$argmax_{S'\in \mathbb{S}}\sum_{i\in S'}\bar{x}_i-r(S')$$.

To have a concrete example, let's assume that $$\mathbb{S}=\{S\subset N|\sum_{i\in S}a_i>b\}$$ is the family of subsets that exceed a knapsack constraint*. Let $$z_i$$ be a binary variable indicating whether item $$i$$ is a member of set $$S'$$. To find the most violated set $$S'$$, we would have to solve: \begin{align} \max \sum_{i\in N}\bar{x}_iz_i-r(z) \end{align}

where

\begin{align} r(z)=&\max \sum_{i\in N}y_i&\\ &\sum_{i\in N}a_iy_i\leq b&\\ &y_i\leq z_i & \forall i\in N\\ &y_i binary &\forall i\in N \end{align}

If the resulting objective is strictly positive, a violated set has been found. My question: is there a way to reformulate this separation problem into single model (e.g. $$\max \sum_{i\in N}\bar{x}_iz_i-r$$ with $$r\geq \dots$$)? If not, how would one solve this formulation?

*: in my problem, the infeasible sets are more complex than knapsack constraints, but I use it here for illustrative purposes.

• I think I understand what you want to do, but the $r(S')$ versus $r(z)$ is a bit confusing because one argument is a set and the other argument is a characteristic vector of a set. Also, the argmax should not mix $S'$ and $z$: $\sum_{i\in S'} \bar{x}_i z_i$ is just $\sum_{i\in S'} \bar{x}_i$. Jun 2 at 20:54

Here's where I think you are heading: \begin{align} &\max_{z\in\{0,1\}^N} \left[\sum_{i\in N} \bar{x}_i z_i - \max_{y\in\{0,1\}^N} \left(\sum_{i\in N} y_i: \sum_{i\in N} a_i y_i \le b \land \bigwedge_{i\in N} (y_i \le z_i) \right) \right] \\ &= \max_z \left[\bar{x}^T z - \max_y \left(e^T y: a^T y \le b \land y \le z \right) \right] \\ &= \max_z \left[\bar{x}^T z + \min_y \left(-e^T y: a^T y \le b \land y \le z \right) \right] \\ &\stackrel{*}{=} \max_{z, \eta, y} \left[\bar{x}^T z + \eta: \eta \le -e^T y \land a^T y \le b \land y \le z \right] \\ &= \max_{z, r, y} \left[\bar{x}^T z - r: r \ge e^T y \land a^T y \le b \land y \le z \right] \end{align} But the $$\stackrel{*}{=}$$ step is suspect. In particular, it leads to the false conclusion that it is always optimal to take $$r=0$$ and $$y_i=0$$ for all $$i$$. If your actual subproblem (not knapsack) is totally unimodular, you can relax $$y$$, dualize the subproblem, and maximize over $$z$$ and the dual variables. Otherwise, relaxing $$y$$ yields only a bound.
A generic approach is to use combinatorial Benders decomposition, with the master problem over $$z$$ and the subproblem over $$y$$ for fixed $$z=\hat{z}$$. If the subproblem is infeasible, the Benders feasibility cuts prohibit that $$\hat{z}$$. If the subproblem is optimal but the objective value disagrees with $$\hat{\eta}$$, the Benders optimality cuts prohibit that $$(\hat{z},\hat{\eta})$$. But then you would be using a cutting-plane algorithm to find cuts for a cutting-plane algorithm...