On the benchmark instances for the bin packing problem with conflicts

DOI10.1007/978-3-030-63072-0_14zbMATH Open1481.90269arXiv1706.03526OpenAlexW3133870113MaRDI QIDQ2056901FDOQ2056901

Tiziano Bacci, Sara Nicoloso

Publication date: 8 December 2021

Abstract: Many authors, mainly in the context of the Bin Packing Problem with Conflicts, used the random graph generator proposed in "Heuristics and lower bounds for the bin packing problem with conflicts" [M. Gendreau, G. Laporte, and F. Semet, Computers & Operations Research, 31:347-358, 2004]. In this paper we prove that the graphs generated in this way are not arbitrary but threshold ones. Computational results show that instances with threshold conflict graphs are easier to solve w.r.t. instances with arbitrary conflict graphs.

Full work available at URL: https://arxiv.org/abs/1706.03526

zbMATH Keywords

threshold graphsbin packing with conflictsrandom graph generator

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristics and lower bounds for the bin packing problem with conflicts
• Algorithms for the bin packing problem with conflicts
• New lower bounds for bin packing problems with conflicts
• Column generation based primal heuristics
• Heuristics for determining the number of warehouses for storing non-compatible products
• Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
• Bin packing and related problems: general arc-flow formulation with graph compression
• Dual inequalities for stabilized column generation revisited
• Approximation algorithms for time constrained scheduling
• Solving vertex coloring problems as maximum weight stable set problems
• A branch-and-price algorithm for the bin packing problem with conflicts
• The min-conflict packing problem
• A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems
• A DSS based on optimizer tools and MTS meta-heuristic for the warehousing problem with conflicts
• Heuristics for solving the bin-packing problem with conflicts
• A Multi-start Tabu Search Based Algorithm for Solving the Warehousing Problem with Conflict
• On the benchmark instances for the bin packing problem with conflicts

Cited In (2)

• On the benchmark instances for the bin packing problem with conflicts
• Algorithms for the bin packing problem with conflicts

This page was built for publication: On the benchmark instances for the bin packing problem with conflicts

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