The linear multiple choice knapsack problem

Sanjiv Sarin; Mark H. Karwan

doi:10.1016/0167-6377(89)90008-4

The linear multiple choice knapsack problem

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

Abstract

The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. We present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The method is based on systematically perturbing the right-hand side of the knapsack constraint and the application of a dual-simplex based strategy. Computational experience with the method is also presented.

Original language	English
Pages (from-to)	95-100
Number of pages	6
Journal	Operations Research Letters
Volume	8
Issue number	2
DOIs	https://doi.org/10.1016/0167-6377(89)90008-4
State	Published - Apr 1989
Externally published	Yes

Keywords

knapsack problems
linear programming
multiple choice constraints

Access to Document

10.1016/0167-6377(89)90008-4

Cite this

@article{c6288ca8b14a4c56a508974651312802,

title = "The linear multiple choice knapsack problem",

abstract = "The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. We present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The method is based on systematically perturbing the right-hand side of the knapsack constraint and the application of a dual-simplex based strategy. Computational experience with the method is also presented.",

keywords = "knapsack problems, linear programming, multiple choice constraints",

author = "Sanjiv Sarin and Karwan, \{Mark H.\}",

year = "1989",

month = apr,

doi = "10.1016/0167-6377(89)90008-4",

language = "English",

volume = "8",

pages = "95--100",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "2",

}

TY - JOUR

T1 - The linear multiple choice knapsack problem

AU - Sarin, Sanjiv

AU - Karwan, Mark H.

PY - 1989/4

Y1 - 1989/4

N2 - The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. We present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The method is based on systematically perturbing the right-hand side of the knapsack constraint and the application of a dual-simplex based strategy. Computational experience with the method is also presented.

AB - The multiple choice knapsack problem is defined as a knapsack problem with additional mutually exclusive multiple choice constraints. We present an algorithm for solving the linear programming relaxation of the multiple choice knapsack problem. The method is based on systematically perturbing the right-hand side of the knapsack constraint and the application of a dual-simplex based strategy. Computational experience with the method is also presented.

KW - knapsack problems

KW - linear programming

KW - multiple choice constraints

UR - https://www.scopus.com/pages/publications/0024641280

U2 - 10.1016/0167-6377(89)90008-4

DO - 10.1016/0167-6377(89)90008-4

M3 - Article

SN - 0167-6377

VL - 8

SP - 95

EP - 100

JO - Operations Research Letters

JF - Operations Research Letters

IS - 2

ER -

The linear multiple choice knapsack problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this