LP based heuristics for the multiple knapsack problem with assignment restrictions

DOI10.1007/S10479-006-0048-1MaRDI QIDQ863573zbMATHOpenAlexFDO

Authors Geir Dahl, Njål Foldnes

Publication date 5 February 2007

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10852/36885

zbMATH Keywords

traffic routingrandomized roundingmultiple knapsack problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Recommendations

• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• A class of generalized greedy algorithms for the multi-knapsack problem
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• Approximability of two variants of multiple knapsack problems
• A procedure-based heuristic for 0-1 multiple knapsack problems

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 1405893 (Why is no real title available?)
• A PTAS for the multiple subset sum problem with different knapsack capacities
• An exact algorithm for large multiple knapsack problems
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Maximum matching in a convex bipartite graph
• Rounding algorithms for covering problems
• Solving Multiple Knapsack Problems by Cutting Planes

Cited in

(8)

• Approximation algorithms and relaxations for a service provision problem on a telecommunication network
• Emergency relocation of items using single trips: special cases of the multiple knapsack assignment problem
• The food bank resource allocation problem
• Time-sharing scheduling with tolerance capacities
• The assignment and loading transportation problem
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Multiple subset sum with inclusive assignment set restrictions
• An LP-based metaheuristic procedure for the k-sequential generalized assignment problem

Describes a project that uses

Uses Software

• CPLEX
• Knapsack
• MULKNAP

This page was built for publication: LP based heuristics for the multiple knapsack problem with assignment restrictions

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