Start of Main Content
Journal Article
A Concise Characterization of Strong Knapsack Facets
Discrete Applied Mathematics
Author(s)
For the integer knapsack problem, the 1/k-facets with k dividing 6 or 8 were shown to
be very strong and efficiently separated (Chopra et al., 2015; Shim et al., 2017). We give a concise characterization of the 1/k-facets for each k dividing 6, 8 in terms of a concise description of the coefficients. This allows these inequalities to be separated efficiently. We develop a reduced linear programming formulation to speed up identification of the facets hit during the shooting experiment, and confirm the strength of the 1/k-facets with k dividing 6 or 8 in higher dimensional problems.
Date Published:
2018
Citations:
Chopra, Sunil, Sangho Shim, Daniel Steffy. 2018. A Concise Characterization of Strong Knapsack Facets. Discrete Applied Mathematics.