A branch and bound algorithm for solving the multiple-choice knapsack problem

DOI10.1016/0377-0427(84)90023-2MaRDI QIDQ760766zbMATH OpenOpenAlexWikidataFDO

Authors D. Kharzeev

Publication date 1984

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(84)90023-2

zbMATH Keywords

branch and bound algorithmcomparisonspegging testComputational experiencemultiple-choice knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Boolean programming (90C09)

Recommendations

• scientific article; zbMATH DE number 3889280
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• scientific article; zbMATH DE number 3860891
• The linear multiple choice knapsack problem
• A fast algorithm for the linear multiple-choice knapsack problem

Cites work

• scientific article; zbMATH DE number 3668317 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3748730 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3559281 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3410784 (Why is no real title available?)
• A computational study of a multiple-choice knapsack algorithm
• A mathematical programming system for preference and compatibility maximized menu planning and scheduling
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• Pivot and Complement–A Heuristic for 0-1 Programming
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• The 0-1 knapsack problem with multiple choice constraints
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem

Cited in

(29)

• An O(n) algorithm for the multiple-choice knapsack linear program
• A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints
• scientific article; zbMATH DE number 4139486 (Why is no real title available?)
• Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm
• Approximate and exact algorithms for the fixed-charge knapsack problem
• An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint
• Computational comparison on the partitioning strategies in multiple choice integer programming
• The bottleneck generalized assignment problem
• scientific article; zbMATH DE number 3889280 (Why is no real title available?)
• An approximate binary search algorithm for the multiple-choice knapsack problem
• A fast algorithm for the linear multiple-choice knapsack problem
• Algorithm 632: A program for the 0–1 multiple knapsack problem
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Experimental investigations of combined algorithms of branch and bound method and dynamic programming method for knapsack problems
• A Branch-and-Price Algorithm for the Multiple Knapsack Problem
• A multi-criteria approach to approximate solution of multiple-choice knapsack problem
• scientific article; zbMATH DE number 1149800 (Why is no real title available?)
• An exact algorithm for the fixed-charge multiple knapsack problem
• scientific article; zbMATH DE number 3860891 (Why is no real title available?)
• A minimal algorithm for the multiple-choice knapsack problem
• The use of duality to determine the branching order of variables and to estimate the bounds in the solution of the knapsack problem
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• An improved binary search algorithm for the multiple-choice knapsack problem
• A branch-and-bound algorithm for hard multiple knapsack problems
• An Exact Algorithm for the Multiple-Choice Multidimensional Knapsack Based on the Core
• A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints
• A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
• The linear multiple choice knapsack problem
• A solution method for a knapsack problem and its variant

This page was built for publication: A branch and bound algorithm for solving the multiple-choice knapsack problem

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