Friendly bin packing instances without integer round-up property

DOI10.1007/S10107-014-0791-ZzbMath1311.90082OpenAlexW1963954876MaRDI QIDQ2340275

Romeo Rizzi, Mauro Dell'Amico, Manuel Iori, Alberto Caprara, José Carlos Díaz Díaz

Publication date: 16 April 2015

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-014-0791-z

zbMATH Keywords

bin packing problemPetersen graphinteger round-up property

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (19)

Tightness of sensitivity and proximity bounds for integer linear programs ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ 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 ⋮ Exact solution of network flow models with strong relaxations ⋮ Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ BPPLIB: a library for bin packing and cutting stock problems ⋮ Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory ⋮ Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints ⋮ An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case ⋮ Stabilized branch-and-price algorithms for vector packing problems ⋮ A lexicographic pricer for the fractional bin packing problem ⋮ A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems ⋮ About the Structure of the Integer Cone and Its Application to Bin Packing ⋮ New exact techniques applied to a class of network flow formulations ⋮ Improved flow-based formulations for the skiving stock problem ⋮ A branch-and-price algorithm for the temporal bin packing problem ⋮ Minimal proper non-IRUP instances of the one-dimensional cutting stock problem

Cites Work

• Unnamed Item
• A survey of dual-feasible and superadditive functions
• Bidimensional packing by bilinear programming
• An instance of the cutting stock problem for which the rounding property does not hold
• Worst-case analyses, linear programming and the bin-packing problem
• Families of non-IRUP instances of the one-dimensional cutting stock problem
• LP models for bin packing and cutting stock problems
• A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
• Heuristic and Exact Algorithms for the Identical Parallel Machine Scheduling Problem
• Bin Packing via Discrepancy of Permutations
• A Linear Programming Approach to the Cutting-Stock Problem
• Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem
• A Linear Programming Approach to the Cutting Stock Problem—Part II

This page was built for publication: Friendly bin packing instances without integer round-up property