A few strong knapsack facets

Sunil Chopra, Sangho Shim*, Daniel E. Steffy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We perform a shooting experiment for the knapsack facets and observe that 1/k-facets are strong for small k; in particular, k dividing 6 or 8.We also observe spikes of the size of 1/k-facets when k = n or when kC1 divides n+1.We discuss the strength of the 1/n-facets introduced by Aráoz et al. (Math Program 96:377– 408, 2003) and the knapsack facets given by Gomory’s homomorphic lifting. A general integer knapsack problem is a knapsack subproblem where a portion, often a significant majority, of the variables are missing from the master knapsack problem. The number of projections of 1/k-facets on a knapsack subproblem of l variables is O.(⌈k/2⌉), note that this is independent of the size of the master problem. Since 1/k-facets are strong for small k, we define the 1/k-inequalities which include the 1/d-facets with d dividing k and fix k to be a small constant such as k / 6 or k = 8. We develop an efficient way of enumerating violated valid 1/k-inequalities. For each violated 1/k-inequality, we determine its validity by solving a small integer programming problem, the size of which depends only on k.

Original languageEnglish (US)
Title of host publicationModeling and Optimization
Subtitle of host publicationTheory and Applications, MOPTA, Selected Contributions
EditorsBoris Defourny, Tamas Terlaky
PublisherSpringer New York LLC
Pages77-94
Number of pages18
ISBN (Print)9783319236988
DOIs
StatePublished - Jan 1 2015
EventInternational Conference on Modeling and Optimization: Theory and Applications, MOPTA, 2014 - Bethlehem, United States
Duration: Aug 13 2014Aug 15 2014

Publication series

NameSpringer Proceedings in Mathematics and Statistics
Volume147
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017

Other

OtherInternational Conference on Modeling and Optimization: Theory and Applications, MOPTA, 2014
CountryUnited States
CityBethlehem
Period8/13/148/15/14

Keywords

  • Cutting planes
  • Facets
  • Knapsack problem
  • Master knapsack polytope
  • Shooting experiment

ASJC Scopus subject areas

  • Mathematics(all)

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

Cite this