Start of Main Content
Author(s)

Sunil Chopra

Sangho Shim

Daniel Steffy

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.