Skip to Main content Skip to Navigation
Journal articles

An implementation of exact knapsack separation

Abstract : Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated p-median problem and capacitated network location problem to optimality.
Document type :
Journal articles
Complete list of metadata
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 9:44:25 AM
Last modification on : Thursday, April 28, 2022 - 5:01:30 PM

Links full text




Igor A Vasilyev, Maurizio Boccia, Said Hanafi. An implementation of exact knapsack separation. Journal of Global Optimization, Springer Verlag, 2016, 66 (1), pp.127-150. ⟨10.1007/s10898-015-0294-3⟩. ⟨hal-03400563⟩



Record views