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

Sanjiv Sarin
, Mark H. Karwan

Industrial and Systems Engineering

Industrial and systems engineering with North Carolina A&T State University
State University of New York at Buffalo

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

6 Scopus citations

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. © 1989.

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 - Jan 1 1989

Keywords

knapsack problems
linear programming
multiple choice constraints

Access to Document

10.1016/0167-6377(89)90008-4

Cite this

@article{213bad72e25240948c4b01460c14e39b,

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. {\textcopyright} 1989.",

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

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

year = "1989",

month = jan,

day = "1",

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/1/1

Y1 - 1989/1/1

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. © 1989.

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. © 1989.

KW - knapsack problems

KW - linear programming

KW - multiple choice constraints

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=0024641280&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=0024641280&origin=inward

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