So I have a 0-1 knapsack problem:

\begin{align}\max&\quad \sum_j c_j x_j\\ \text{s.t.}&\quad \sum_j a_j x_j \leq b\\ &\quad x_j \in \{0,1\}\end{align}

but it has an additional requirement that the number of items in an optimal knapsack should be odd. I know I can model it with one extra variable, but the assignment calls for redefining separation procedure.

To my understanding, that means writing a callback procedure that will generate additional constraints in branch-and-cut algorithm. I know that 0-1 knapsacks have special kinds of inequalities to strengthen LP formulation, but I don't know how to incorporate them with the requirement of odd number of items.

  • $\begingroup$ Cross-posted math.stackexchange.com/questions/4339581/… $\endgroup$
    – RobPratt
    Commented Dec 22, 2021 at 4:22
  • $\begingroup$ The phrase "redefining the separation procedure" might not imply new cuts. It might refer to changing how a node is split into child nodes. $\endgroup$
    – prubin
    Commented Dec 22, 2021 at 16:16
  • $\begingroup$ @prubin The whole phrase is "use default branching rule and redefine separation procedure", so I thought it was to do with new cuts $\endgroup$
    – Aisec Nory
    Commented Dec 22, 2021 at 19:12
  • $\begingroup$ Yes, I would agree given the full phrase. $\endgroup$
    – prubin
    Commented Dec 22, 2021 at 20:19

1 Answer 1


Unfortunately, I also do not know how to embed 0-1-knapsack specific inequalities with the odd number solution requirement. However, I know how to generate cuts that will reduce the search space whenever an even number of items is picked. So, let $x^{*} \in \mathbb{R}^{n}$ be an optimal, eventually fractional, solution. If $\sum_{j} x^{*}_j$ is an integer even number, then we can say that $\sum_{j \in I} x_j - \sum_{k \notin I} x_k \leqslant |I| - 1$, where $I = \{j : x^*_j > 0\}$. With these thoughts in mind, fluidly we design the below separation algorithm (callback):

  1. Get $x^{*}$ and $I$.
  2. If $\sum_{j} x_j^{*}$ is integer and even then:
  3. Add $\sum_{j \in I} x_j - \sum_{k \notin I} x_k \leqslant |I| - 1$ to the formulation.

Actually, we can play a little bit with the addition of a new variable; as you commented earlier. Let $y \in \mathbb{N}$ be a natural variable, then we can force the formulation, on its integer solution space, to consider only $\sum_{j} x_j$ as odd numbers, if we say that $\sum_{j} x_j = 2 y + 1$.

Furthermore, we can try out new branching rules, where we basically branch on odd numbers.

  1. Get $x^{*}$
  2. Let $F = \lfloor \frac{\sum_{j} x^*_j}{2} \rfloor$, and $C = \lceil \frac{\sum_{j} x^*_j}{2} \rceil$
  3. If $C = F$ then:
  4. start branching on $x_j$
  5. exit
  6. If $F$ is odd then:
  7. branch on $\sum_{j} x_j \leqslant F$
  8. branch on $\sum_{j} x_j \geqslant C + 1$
  9. else:
  10. branch on $\sum_{j} x_j \leqslant F - 1$
  11. branch on $\sum_{j} x_j \geqslant C$

Case anyone has any questions or suggestions, please feel free.

UPDATE 1: Updating step 3 of the first algorithm. ps.: thanks @RobPratt for the observation and the edge case.

  • 1
    $\begingroup$ Your no-good cut is too strong. For example, it prevents setting $x_i=1$ for all $i\in I$ and $x_j=1$ for exactly one $j\notin I$. You can repair this approach by using the more general canonical no-good cut. $\endgroup$
    – RobPratt
    Commented Dec 28, 2021 at 5:50
  • $\begingroup$ Thanks for the comment. If you are talking about the step "3. Add $\sum_{j \in I} x_j \leqslant |I| - 1$ to the formulation", it is not clear for me why it prevents setting $x_j = 1$ for exactly one $j \notin J$. Can you elaborate a little bit this? $\endgroup$ Commented Dec 29, 2021 at 7:22
  • 1
    $\begingroup$ Suppose $I=\{1,2\}$. Your cut forbids $x_j=\{1,2,3\}$, which should instead be allowed. $\endgroup$
    – RobPratt
    Commented Dec 29, 2021 at 12:25
  • $\begingroup$ Oh! Now I see your point, thanks for the feedback. I have updated the answer, now I think the new inequality suits this case. $\endgroup$ Commented Dec 29, 2021 at 13:42

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.