We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) 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.

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

Gualandi, Stefano;Avella, Pasquale;Mele, Michele
2026-01-01

Abstract

We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) 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.
2026
Chvátal-Gomory cuts
Cutting planes
Generalized assignment problem
Knapsack problem
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12070/78365
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact