5
$\begingroup$

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?

enter image description here

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

Improve this question
$\endgroup$
1
  • $\begingroup$ To find a minimal violated cover, can't you just minimize $\sum_{j\in N} z_j$ subject to $\sum_{j\in N} a_j z_j > b$ and $\sum_{j\in N} (1-\hat{x}_j)z_j < 1?$ $\endgroup$
    – prubin ♦
    Apr 19 at 18:19

2 Answers 2

Reset to default
3
$\begingroup$

  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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ would you please, what you mean by Hence, you can simply look for items, $i$, with $z_i=x^i=1$ which can be removed without breaking the cover property? Is it mean we need also to modify the RHS of CI by the number of omitted variables? (e.g. Let $x_1+x_2+x_3+x_4 \leq 3$ be a CI for a knapsak in $\mathbb{B^6}$ with x^ $= \{0.5,0.75,1,1,0,0\}$. By that, the CI can be rewritten as, $x_1+x_2 \leq 1$?) $\endgroup$
    – A.Omidi
    Apr 16 at 12:07
  • 1
    $\begingroup$ @A.Omidi Yes that is correct: you would need to update the RHS too. After solving the separation problem $\min\{\sum_{j\in N}(1-\hat{x}_j)z_j | \sum_{j\in N}a_jz_j > b,z\textrm{ binary}\}$, you can simply set $z_i=0$ for any $i$ where $\hat{x}_i=1$ because this will not change the objective function. However, you must check whether the constraint $\sum_{j\in N}a_jz_j > b$ is still satisfied (i.e. it might not be possible to set all $z_i$ to 0 whenever $\hat{x}_i=1$. $\endgroup$
    – Joris Kinable
    Apr 18 at 17:14
  • $\begingroup$ @JorisKinable, thanks so much for informative comments. 🙏 $\endgroup$
    – A.Omidi
    Apr 18 at 21:18
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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