Mathematical models and decomposition methods for the multiple knapsack problem

DOI10.1016/J.EJOR.2018.10.043zbMath1430.90480OpenAlexW2898872836MaRDI QIDQ1755383

Mauro Dell'Amico, Manuel Iori, Silvano Martello, Maxence Delorme

Publication date: 9 January 2019

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11585/683147

zbMATH Keywords

combinatorial optimizationdecomposition methodsexact algorithmsmultiple knapsack problempseudo-polynomial formulations

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (18)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ A Branch-and-Price Algorithm for the Multiple Knapsack Problem ⋮ Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem ⋮ A new upper bound for the multiple knapsack problem ⋮ Optimal selection of touristic packages based on user preferences during sports mega-events ⋮ Half-cycle: a new formulation for modelling kidney exchange problems ⋮ One-dimensional stock cutting resilient against singular random defects ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup ⋮ A decomposition approach for multidimensional knapsacks with family‐split penalties ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ A hybrid evolutionary search for the generalized quadratic multiple knapsack problem ⋮ Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events ⋮ The multiple multidimensional knapsack with family-split penalties ⋮ A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ Faster algorithms for \(k\)-subset sum and variations

Uses Software

• Knapsack
• MULKNAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Bin packing and related problems: general arc-flow formulation with graph compression
• A binary multiple knapsack model for single machine scheduling with machine unavailability
• A branch-and-bound algorithm for hard multiple knapsack problems
• An exact algorithm for large multiple knapsack problems
• Solution of the zero-one multiple knapsack problem
• Heuristic algorithms for the multiple knapsack problem
• A bound and bound algorithm for the zero-one multiple knapsack problem
• Exact solution of bin-packing problems using column generation and branch-and-bound
• Upper bounds and algorithms for the maximum cardinality bin packing problem.
• A 3/4-approximation algorithm for multiple subset sum
• A PTAS for the multiple subset sum problem with different knapsack capacities
• Computational aspects of clearing continuous call double auctions with assignment constraints and indivisible demand
• Logic based Benders' decomposition for orthogonal stock cutting problems
• Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints
• An application of the multiple knapsack problem: the self-sufficient marine
• A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
• A procedure-based heuristic for 0-1 multiple knapsack problems
• A typology of cutting and packing problems
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• An improved typology of cutting and packing problems
• The Multiple Subset Sum Problem
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
• Combinatorial Benders' Cuts for the Strip Packing Problem
• A Linear Programming Approach to the Cutting-Stock Problem
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• An Algorithm for Large Zero-One Knapsack Problems
• A New Linear Programming Approach to the Cutting Stock Problem
• A heuristic routine for solving large loading problems
• An Algorithm for the Solution of 0-1 Loading Problems
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• An algorithm for 0-1 multiple-knapsack problems
• Solving Multiple Knapsack Problems by Cutting Planes
• Reducibility among Combinatorial Problems
• The Meet-in-the-Middle Principle for Cutting and Packing Problems
• The Loading Problem
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Mathematical models and decomposition methods for the multiple knapsack problem