A core heuristic and the branch-and-price method for a bin packing problem with a color constraint

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

Abstract

We study a new bin packing problem with a color constraint. A finite set of items and an unlimited number of identical bins are given. Each item has a set of colors. Each bin has a color capacity. The set of colors for a bin is the union of colors for its items and its cardinality can not exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem, we design the core heuristic based on the column generation approach for the large-scale formulation. A hybrid VNS matheuristic with large neighborhoods is used for solving the pricing problem. We use our core heuristic in the exact branch-and-price method. Computational experiments illustrate the ability of the core heuristic to produce optimal solutions for randomly generated instances with the number of items up to 250. High-quality solutions on difficult instances with regular structure are found.

Original languageEnglish
Title of host publicationOptimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
PublisherSpringer-Verlag GmbH and Co. KG
Pages309-320
Number of pages12
ISBN (Print)9783319937991
DOIs
Publication statusPublished - 1 Jan 2018
Event7th International Conference on Optimization Problems and Their Applications, OPTA 2018 - Omsk, Russian Federation
Duration: 8 Jun 201814 Jun 2018

Publication series

NameCommunications in Computer and Information Science
Volume871
ISSN (Print)1865-0929

Conference

Conference7th International Conference on Optimization Problems and Their Applications, OPTA 2018
CountryRussian Federation
CityOmsk
Period08.06.201814.06.2018

Keywords

  • Branch-and-price
  • Column generation
  • Matheuristic

Fingerprint

Dive into the research topics of 'A core heuristic and the branch-and-price method for a bin packing problem with a color constraint'. Together they form a unique fingerprint.

Cite this