The linear multiple choice knapsack problem
type: Item
instance of: scholarly article
title: The linear multiple choice knapsack problem
zbMATH Open document ID: 0683.90051
DOI: 10.1016/0167-6377(89)90008-4
author: Sanjiv Sarin
author: Mark H. Karwan
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4119930
zbMATH Keywords: linear multiple choice knapsack
zbMATH Keywords: systematic perturbation
zbMATH Keywords: branch-and- bound
zbMATH Keywords: dual-type method
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90008-4
OpenAlex ID: W2119039305
cites work: Generalized upper bounding techniques
cites work: A fast algorithm for the linear multiple-choice knapsack problem
cites work: An O(n) algorithm for the multiple-choice knapsack linear program
cites work: A o(n logn) algorithm for LP knapsacks with GUB constraints
cites work: The Multiple-Choice Knapsack Problem
cites work: The Linear Multiple Choice Knapsack Problem
cites work: An O(n) algorithm for the linear multiple choice knapsack problem and related problems
description: scientific article; zbMATH DE number 4119930