3
$\begingroup$

Is the following expression a knapsack constraint?

$ \sum_i a(i) y(i) \ge W$, where $y(i)$ binaries, $a(i),W$ reals.

What confuses me is the $\ge$ sign.

Alternatively, do solvers generate cuts out of this expression?

$\endgroup$
1
  • 3
    $\begingroup$ If you compliment the variables $y(i)=1-z(i)$, substitute, and rearrange terms, you get a classic knapsack constraint. And yes, solvers generally separate cuts from all available structures. $\endgroup$
    – Sune
    Apr 22, 2023 at 21:14

2 Answers 2

2
$\begingroup$

If you complement the variables $y_i=1−z_i$, substitute, and rearrange terms, you get a classic knapsack constraint. And yes, solvers generally separate cuts from all available structures.

A simple set of valid inequalities (which could be used as cuts) for your “inverted knapsack constraint” are the so-called knapsack cover inequalities: $$ \sum_{i\in N\setminus S}\min \left\{ a_i, W-\sum_{i\in S}a_i\right\}y_i\geq W-\sum_{i\in S}a_i $$ Here $N$ is the index set for the variables, and $S\subseteq N$ is such that $\sum_{i\in S}a_i<W$. In “Lifting the Knapsack Cover Inequalities for the Knapsack Polytope” Letchford and Souli show how to strengthen these inequalities through lifting.

$\endgroup$
0
$\begingroup$

Either you are looking at knapsack cover ($a_i(1-y)_i$ where $y_i=0$) inequality or its part of minimizing knapsack problem. Modern solvers will relax the MIP and then may apply cuts like Gomory cuts.

$\endgroup$

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.