1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jun 2, 2023 at 20:54

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ yes this was exactly where I was heading and I got stuck on the same *step. I was hoping there was some nice trick to get around this issue. My subproblem is not totaly unimodular. In fact, it also has a weak LP relaxation, so this might not be a very viable approach. $\endgroup$ Jun 2, 2023 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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