A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

DOI10.1007/S10479-008-0452-9MaRDI QIDQ610980zbMATH OpenOpenAlexFDO

Authors Andrea Bettinelli, Alberto Ceselli, Giovanni Righini

Publication date 13 December 2010

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

Full work available at URL https://doi.org/10.1007/s10479-008-0452-9

zbMATH Keywords

bin packingbranch-and-pricecolumn generation

Mathematics Subject Classification ID

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

Recommendations

• An exact algorithm for the type-constrained and variable sized bin packing problem
• Heuristics for the variable sized bin-packing problem
• Relaxations and exact solution of the variable sized bin packing problem
• Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items
• Efficient algorithms for the offline variable sized bin-packing problem

Cites work

• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
• A local-search-based heuristic for the demand-constrained multidimensional knapsack problem
• A Minimal Algorithm for the Bounded Knapsack Problem
• A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem
• Accelerating column generation for variable sized bin-packing problems
• Algorithms for packing and scheduling problems. (Abstract of thesis)
• Algorithms for the variable sized bin packing problem
• Anomalous behavior in bin packing algorithms
• Column generation approaches to ship scheduling with flexible cargo sizes
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• Models and bounds for two-dimensional level packing problems
• Ship routing and scheduling with flexible cargo sizes
• Solving the variable size bin packing problem with discretized formulations
• Using extra dual cuts to accelerate column generation
• Variable Sized Bin Packing
• Variable-sized bin packing: Tight absolute worst-case performance ratios for four approximation algorithms

Cited in

(16)

• A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function
• Solving robust bin-packing problems with a branch-and-price approach
• Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
• Variable neighborhood search for quadratic multiple constraint variable sized bin-packing problem
• An exact algorithm for the type-constrained and variable sized bin packing problem
• Random sampling and machine learning to understand good decompositions
• A lexicographic pricer for the fractional bin packing problem
• A branch-and-price algorithm for the temporal bin packing problem
• Efficient algorithms for the offline variable sized bin-packing problem
• Solving the variable size bin packing problem with discretized formulations
• Branch and Price for Chance-Constrained Bin Packing
• Branch-and-price and beam search algorithms for the variable cost and size bin packing problem with optional items
• Bin Packing Problem with Time Lags
• Relaxations and exact solution of the variable sized bin packing problem
• Algorithms for the bin packing problem with scenarios
• Algorithms and complexity results for the 0-1 knapsack problem with group fairness

Describes a project that uses

Uses Software

• Knapsack
• CPLEX
• SCIP

This page was built for publication: A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

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