Take Action

Home | Faculty & Research Overview | Research

Research Details

A Concise Characterization of Strong Knapsack Facets, Discrete Applied Mathematics

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.

LINK
KELLOGG INSIGHT

Explore leading research and ideas

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.
learn more

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.
LEARN MORE

DEGREE PROGRAMS

Discover the path to your goals

Whether you choose our Full-Time, Part-Time or Executive MBA program, you’ll enjoy the same unparalleled education, exceptional faculty and distinctive culture.
learn more