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

Question

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.

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.