A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints

DOI10.1016/S0305-0548(03)00021-2zbMath1046.90046OpenAlexW1974632181MaRDI QIDQ1433165

George Kozanidis, Emanuel Melachrinoudis

Publication date: 15 June 2004

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0305-0548(03)00021-2

zbMATH Keywords

branch-and-bound algorithmmixed integer knapsack problemmultiple choice constraints

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Boolean programming (90C09)

Related Items (4)

Development of a hybrid dynamic programming approach for solving discrete nonlinear Knapsack problems ⋮ Solving the linear multiple choice knapsack problem with two objectives: Profit and equity ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

Uses Software

• LINDO
• Knapsack
• LINGO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A fast algorithm for the linear multiple-choice knapsack problem
• A note on the knapsack problem with special ordered sets
• Approximate algorithms for some generalized knapsack problems
• A minimal algorithm for the multiple-choice knapsack problem
• The linear multiple choice knapsack problem
• An efficient algorithm for determining the convex hull of a finite planar set
• LAPACK95 Users' Guide
• An O(n) algorithm for the multiple-choice knapsack linear program
• A computational study of a multiple-choice knapsack algorithm
• On the solution of special generalized upper-bounded problems: The LP/GUB knapsack problem and the λ-form separable convex objective function problem
• A o(n logn) algorithm for LP knapsacks with GUB constraints
• The Linear Multiple Choice Knapsack Problem
• The Multiple-Choice Knapsack Problem
• A Bibliographical Survey On Some Well-Known Non-Standard Knapsack Problems

This page was built for publication: A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints