The linear multiple choice knapsack problem

DOI10.1016/0167-6377(89)90008-4MaRDI QIDQ1825130zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 3889280
• An O(n) algorithm for the multiple-choice knapsack linear program
• A branch and bound algorithm for solving the multiple-choice knapsack problem
• A fast algorithm for the linear multiple-choice knapsack problem
• A minimal algorithm for the multiple-choice knapsack problem

Cites work

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

Cited in

(20)

• scientific article; zbMATH DE number 2010048 (Why is no real title available?)
• An O(n) algorithm for the multiple-choice knapsack linear program
• Relief period optimization under budget constraints
• The multiple-choice multi-period knapsack problem
• scientific article; zbMATH DE number 3889280 (Why is no real title available?)
• A fast algorithm for the linear multiple-choice knapsack problem
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A multi-criteria approach to approximate solution of multiple-choice knapsack problem
• A branch and bound algorithm for solving the multiple-choice knapsack problem
• A dynamic programming approach to solving the multiple choice knapsack problem
• Budgeting with bounded multiple-choice constraints.
• scientific article; zbMATH DE number 3860891 (Why is no real title available?)
• Minimum-diameter covering problems
• Solution of multiple-choice knapsack problem encountered in high-level synthesis of vlsi circuits
• The linear multiple choice knapsack problem with equity constraints
• Solving the linear multiple choice knapsack problem with two objectives: Profit and equity
• scientific article; zbMATH DE number 3906236 (Why is no real title available?)
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• Exact methods for the knapsack problem and its generalizations
• A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825130)