A concise characterization of strong knapsack facets

Sunil Chopra; Sangho Shim; Daniel E. Steffy

doi:10.1016/j.dam.2018.05.006

A concise characterization of strong knapsack facets

Sunil Chopra, Sangho Shim^*, Daniel E. Steffy

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	136-152
Number of pages	17
Journal	Discrete Applied Mathematics
Volume	253
DOIs	https://doi.org/10.1016/j.dam.2018.05.006
State	Published - 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

Access to Document

10.1016/j.dam.2018.05.006

Cite this

@article{93a721d55e8d4dc6a97aa100db3f5328,

title = "A concise characterization of strong knapsack facets",

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.",

keywords = "2-slope facet, Cyclic group problem, Integer programming, Knapsack facets, Shooting experiment",

author = "Sunil Chopra and Sangho Shim and Steffy, {Daniel E.}",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2019",

month = jan,

day = "30",

doi = "10.1016/j.dam.2018.05.006",

language = "English (US)",

volume = "253",

pages = "136--152",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - A concise characterization of strong knapsack facets

AU - Chopra, Sunil

AU - Shim, Sangho

AU - Steffy, Daniel E.

PY - 2019/1/30

Y1 - 2019/1/30

N2 - 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.

AB - 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.

KW - 2-slope facet

KW - Cyclic group problem

KW - Integer programming

KW - Knapsack facets

KW - Shooting experiment

UR - http://www.scopus.com/inward/record.url?scp=85047485569&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85047485569&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.05.006

DO - 10.1016/j.dam.2018.05.006

M3 - Article

AN - SCOPUS:85047485569

SN - 0166-218X

VL - 253

SP - 136

EP - 152

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A concise characterization of strong knapsack facets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this