A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem

DOI10.1016/0377-0427(93)E0264-MzbMath0828.65070OpenAlexW2037490069WikidataQ56324036 ScholiaQ56324036MaRDI QIDQ1894383

Yanyan Li

Publication date: 10 January 1996

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(93)e0264-m

zbMATH Keywords

integer programmingdynamic programmingnumerical examplesbranch-and-bound methodLagrangian dualitymultiple-choice knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Dynamic programming (90C39)

Related Items (6)

Dynamic programming algorithms for the bi-objective integer knapsack problem ⋮ A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem ⋮ An exact algorithm for the reliability redundancy allocation problem ⋮ An efficient algorithm for the Lagrangean dual of nonlinear knapsack problems with additional nested constraints ⋮ A multi-criteria approach to approximate solution of multiple-choice knapsack problem ⋮ Heuristic allocation based on a dynamic programming state-space representation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A branch and bound algorithm for solving the multiple-choice knapsack problem
• A dynamic programming approach to solving the multiple choice knapsack problem
• Some computational results on real 0-1 knapsack problems
• Exact methods for the knapsack problem and its generalizations
• An improved direct descent algorithm for binary knapsack problems
• The 0-1 knapsack problem with multiple choice constraints
• A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem
• A computational study of a multiple-choice knapsack algorithm
• Pivot and Complement–A Heuristic for 0-1 Programming
• Hard Knapsack Problems
• Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints
• Storage cost considerations in secondary index selection
• Surrogate Constraint Duality in Mathematical Programming
• An Algorithm for Nonlinear Knapsack Problems
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• A mathematical programming system for preference and compatibility maximized menu planning and scheduling
• A hybrid approach to discrete mathematical programming
• The Multiple-Choice Knapsack Problem

This page was built for publication: A hybrid dynamic programming/branch-and-bound algorithm for the multiple- choice knapsack problem