Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets

We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: 𝑖) enumerating a finite set of possible optimal multipliers for the knapsack constraint; 𝑖𝑖) for each candidate, adjusting optimally the remaining multipliers. We prove that 𝑖𝑖) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time exact separation algorithm and two efficient greedy heuristics. Computational experiments on Generalized Assignment Problem instances confirm the effectiveness of the approach in terms of cut strength and computational efficiency.