A fast algorithm for the linear multiple-choice knapsack problem

DOI10.1016/0167-6377(84)90027-0zbMath0549.90069OpenAlexW2155737905MaRDI QIDQ800227

Stanisław Walukiewicz, Krzysztof Dudzinski

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1016/0167-6377(84)90027-0

zbMATH Keywords

fast algorithmbranch-and bound approachlinear multiple-choice knapsack problemmedian finding in ordered sets

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (9)

Exact methods for the knapsack problem and its generalizations ⋮ The linking set problem: a polynomial special case of the multiple-choice knapsack problem ⋮ 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 ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ Relaxation heuristics for a generalized assignment problem ⋮ The linear multiple choice knapsack problem ⋮ A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem

Cites Work

• The complexity of selection and ranking in X+Y and matrices with sorted columns
• A note on the knapsack problem with special ordered sets
• On the computational power of pushdown automata
• An O(n) algorithm for the multiple-choice knapsack linear program
• The Linear Multiple Choice Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• The Multiple-Choice Knapsack Problem

This page was built for publication: A fast algorithm for the linear multiple-choice knapsack problem