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?