The linear multiple choice knapsack problem

DOI10.1016/0167-6377(89)90008-4zbMath0683.90051OpenAlexW2119039305MaRDI QIDQ1825130

Sanjiv Sarin, Mark H. Karwan

Publication date: 1989

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(89)90008-4

zbMATH Keywords

branch-and- boundlinear multiple choice knapsackdual-type methodsystematic perturbation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (3)

A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints ⋮ Minimum-diameter covering problems ⋮ Relief period optimization under budget constraints

Cites Work

• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A fast algorithm for the linear multiple-choice knapsack problem
• Generalized upper bounding techniques
• An O(n) algorithm for the multiple-choice knapsack linear program
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem

This page was built for publication: The linear multiple choice knapsack problem