Finding a maximum violated infeasible subset

Question

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.}

Answer 1

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