Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem

DOI10.1016/j.ejor.2004.06.034zbMath1085.90030OpenAlexW2066420593MaRDI QIDQ2572248

Zeger Degraeve, Marc Peeters

Publication date: 16 November 2005

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.06.034

zbMATH Keywords

Integer programmingPackingBranch-and-price

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (13)

Integer linear programming models for the skiving stock problem ⋮ Improved approaches to the exact solution of the machine covering problem ⋮ The skiving stock problem and its relation to hypergraph matchings ⋮ Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation ⋮ Large proper gaps in bin packing and dual bin packing problems ⋮ Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model ⋮ Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case ⋮ The proper relaxation and the proper gap of the skiving stock problem ⋮ Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory ⋮ Integer rounding and modified integer rounding for the skiving stock problem ⋮ Lower bounds and algorithms for the minimum cardinality bin covering problem ⋮ An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case ⋮ Improved flow-based formulations for the skiving stock problem

Uses Software

• LINDO
• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic bounds for dual bin-packing
• Bin packing: Maximizing the number of pieces packed
• An exact algorithm for IP column generation
• Branch-and-price algorithms for the one-dimensional cutting stock problem
• Dual bin packing with items of random sizes
• An exact algorithm for the dual bin packing problem
• Heuristics for the integer one-dimensional cutting stock problem: A computational study
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• A Linear Programming Approach to the Cutting-Stock Problem
• Routing with time windows by column generation
• A Column Generation Approach to the Urban Transit Crew Scheduling Problem
• Case Studies from Industry: Skiving Addition to the Cutting Stock Problem in the Paper Industry
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• Optimal Integer Solutions to Industrial Cutting Stock Problems
• A Linear Programming Approach to the Cutting Stock Problem—Part II

This page was built for publication: Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem