A concise characterization of strong knapsack facets

Sunil Chopra, Sangho Shim*, Daniel E. Steffy

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)136-152
Number of pages17
JournalDiscrete Applied Mathematics
Volume253
DOIs
StatePublished - Jan 30 2019

Keywords

  • 2-slope facet
  • Cyclic group problem
  • Integer programming
  • Knapsack facets
  • Shooting experiment

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A concise characterization of strong knapsack facets'. Together they form a unique fingerprint.

  • Cite this