A Branch-and-Price Algorithm for the Multiple Knapsack Problem

DOI10.1287/ijoc.2022.1223OpenAlexW4292737938MaRDI QIDQ5060791

Olivier Lalonde, Jean-François Côté, Bernard Gendron

Publication date: 11 January 2023

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2022.1223

zbMATH Keywords

Lagrangian relaxationbranch-and-pricemultiple knapsack problem

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Uses Software

• Knapsack
• MULKNAP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A binary multiple knapsack model for single machine scheduling with machine unavailability
• A branch-and-bound algorithm for hard multiple knapsack problems
• A branch-and-price algorithm for the capacitated facility location problem
• A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem
• A polynomial algorithm for the multiple knapsack problem with divisible item sizes
• 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
• Mathematical models and decomposition methods for the multiple knapsack problem
• A procedure-based heuristic for 0-1 multiple knapsack problems
• LP models for bin packing and cutting stock problems
• A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
• Arc flow formulations based on dynamic programming: theoretical foundations and applications
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• A new upper bound for the multiple knapsack problem
• A Simple but Usually Fast Branch-and-Bound Algorithm for the Capacitated Facility Location Problem
• Using Extra Dual Cuts to Accelerate Column Generation
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A heuristic routine for solving large loading problems
• An Algorithm for the Solution of 0-1 Loading Problems
• An algorithm for 0-1 multiple-knapsack problems
• The Meet-in-the-Middle Principle for Cutting and Packing Problems
• Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems