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- bounddual-type methodlinear multiple choice knapsacksystematic perturbation

Mathematics Subject Classification ID

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

Review text

The multiple choice knapsack problem is a knapsack problem with additional multiple choice constraints. Because it is generally solved by branch-and-bound, an efficient solution technique for its linear programming relaxation is essential. This paper presents such a solution algorithm which has two important features compared with current methods: (1) it is a dual-type method which makes it easy to restart with a modified right-hand side and (2) it is faster than the Dudzinski-Walukiewicz algorithm. The algorithm proceeds by systematically perturbing the right-hand side and using a dual simplex pivot after each perturbation. The complexity is empirically found to be O(k), where k is the total number of variables, and the computation time is 2 to 3 times lower than the convex-dominance step of the Dudzinski-Walukiewicz algorithm.

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

(23)

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

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)