Northwestern Kellogg logo

Take Action

Home | Faculty & Research Overview | Research

Research Details

The Multiple-Choice Knapsack Problem, Operations Research

Abstract

The multiple-choice knapsack problem is defined as a binary knapsack problem with the addition of disjoint multiple-choice constraints. The strength of the branch-and-bound algorithm we present for this problem resides with the quick solution of the linear programming relaxation and its efficient, subsequent reoptimization as a result of branching. An implemented version of this algorithm has performed well on a large set of test problems. We cite computational results as well as a comparison with a previously reported algorithm. Several useful applications of the multiple-choice knapsack problem are also suggested.

Type

Article

Author(s)

Prabhakant Sinha, Andris Zoltners

Date Published

1979

Citations

Sinha, Prabhakant, and Andris Zoltners. 1979. The Multiple-Choice Knapsack Problem. Operations Research.(3): 503-515.

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