# How to redefine separation procedure to get 0-1 knapsack with odd number of items

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.

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

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.

• 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. Dec 28, 2021 at 5:50
• 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? Dec 29, 2021 at 7:22
• Suppose $I=\{1,2\}$. Your cut forbids $x_j=\{1,2,3\}$, which should instead be allowed. Dec 29, 2021 at 12:25
• Oh! Now I see your point, thanks for the feedback. I have updated the answer, now I think the new inequality suits this case. Dec 29, 2021 at 13:42