Research Details

Abstract

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.

Type

Article

Author(s)

Sunil Chopra, Sangho Shim, Daniel Steffy

Date Published

2018

Citations

Chopra, Sunil, Sangho Shim, and Daniel Steffy. 2018. A Concise Characterization of Strong Knapsack Facets. Discrete Applied Mathematics.