Separating violated cover inequalities

Question

Consider a knapsack problem with binary variables and a standard knapsack constraint $\sum_{j\in N}a_jx_j\leq b$.

• A set $C\subseteq N$ is a cover if $\sum_{j\in C}a_j >b$
• If $C\subseteq N$ is a cover, then we can state a cover inequality (CI): $\sum_{j\in C}x_j \leq |C|-1$
• If $C$ is a cover, and $S\subset C$ is also a cover, then the CI $\sum_{j\in S}x_j \leq |S|-1$ is stronger than the CI associated with $C$
• A cover $C$ is a minimal cover if $C\setminus \{j\}$ is not a cover for all $j\in C$.
• Let $C$ be a cover and $E=\{j:a_j\ge\max_{i\in C}a_i\}$, then $\sum_{j\in C\cup E}x_j\leq |C|-1$ is the extended CI.

Let $\hat{x}$ be the optimal solution to the LP relaxation of our knapsack problem. To find a violated CI, we can solve the following separation problem: $\exists C\subseteq N$, s.t. $\sum_{j\in C} a_j >b$ and $\sum_{j\in C}(1-\hat{x}_j)<1$? This we can do by solving: $\min\{\sum_{j\in N}(1-\hat{x}_j)z_j | \sum_{j\in N}a_jz_j > b,z\textrm{ binary}\}$. If the objective is less than 1, the $z$ variables define the violated cover.

(i) While this separation problem finds a violated cover, this cover doesn't necessary have to be minimal? How to find a minimal violated cover inequality?

(ii) Once we find a violated cover $C$, we can strengthen the associated inequality, e.g. by writing an extended CI or by lifting. The relation between a lifted CI and an extended CI isn't quite obvious to me: is a lifted CI always at least as strong as an extended CI? What procedure would you use to strengthen $C$?

(iii) A sequential lifting procedure such as the one below depends on the order of the variables. Is there a suggested variable ordering that's best to use?

(iv) Are there other procedures than the above lifting procedure that you would consider that leads to potentially stronger inequalities?

Answer 1

1. As a heuristic for finding a minimal violated cover inequality, you can solve your min-knapsack problem to find a cover $C$. Then, you may note that all objective function coefficients of the separation problem are non-negative, so it is only non-minimal if you have some $z_i=1$ where $\hat{x}_i=1$. Also note, that these variables does not contribute to the violation. Hence, you may simply look for items, $i$, with $z_i=\hat{x}_i=1$ which can be removed without breaking the cover property. This way you maintain the violation. Another approach is to consider the separation problem as a lexicographic optimisation problem where the high priority objective is to minimise your violation-objective, and the low priority goal is to minimise the cardinality of the cover. A lex-opt solution can be found by adding a small constant $\varepsilon>0$ to all objective function coefficients, so the function to minimise becomes $\sum_{j\in N}(1-\hat{x}_j+\varepsilon)z_i$

2. I'm am not quite sure here, because the lifted cover inequality depends on your lifting sequence. Hence, it might be possible to come up with a lifting sequence that leads to a weaker inequality. What is true, however, is that there exist at least one lifted cover inequality, that defines a facet for the knapsack polytope. The extended cover inequality is not guaranteed to be facet defining. Hence, there exist cases where a lifted cover inequality strictly dominates the corresponding extended cover inequality. Note that an extended cover inequality is just a special case of a lifted cover inequality, so the best lifted cover inequality is as good or better than the extended cover inequality.

3. There are several suggestions for generating an ordering of the variables. For example Gu et al. propose a specific lifting sequence.

I would generally recommend the paper "Separation algorithms for 0-1 knapsack polytopes" by K. Kaparis and A.N. Letchford in case you are interested in separation for the knapsack polytope.

Answer 2

A partial answer to part (ii) of your question (this was too long for a comment so I'm including it as an answer). Note that the following assumes a minimal cover.

The sequence independent lifting procedure due to Gu, Nemhauser, Savelsbergh ("Sequence Independent Lifting in Mixed Integer Programming", Journal of Combinatorial Optimization, 2000) produces a cut that is at least as strong as the corresponding extended cover inequality. Indeed, all variables with weight at least $a_1 - \lambda + \rho_1$ have a lifting coefficient of at least $1$. Here, $a_1$ is the weight of the heaviest item in the minimal cover, $\lambda = \sum_{j\in C}a_j - b$ is the excess of the cover, and $\rho_1 = \max\{0, a_2 - (a_1 -\lambda)\}$ is the excess of the cover if the heaviest item was replaced by a copy of the 2nd heaviest item. By definition $\rho_1\le\lambda$, so $a_1 - \lambda+\rho_1\le a_1$, so all variables with weight at least $a_1$ have a lifting coefficient of at least $1$, so this (weakly) dominates the extended cover cut.