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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

4 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииOptimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
ИздательSpringer-Verlag GmbH and Co. KG
Страницы309-320
Число страниц12
ISBN (печатное издание)9783319937991
DOI
СостояниеОпубликовано - 1 янв 2018
Событие7th International Conference on Optimization Problems and Their Applications, OPTA 2018 - Omsk, Российская Федерация
Продолжительность: 8 июн 201814 июн 2018

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том871
ISSN (печатное издание)1865-0929

Конференция

Конференция7th International Conference on Optimization Problems and Their Applications, OPTA 2018
СтранаРоссийская Федерация
ГородOmsk
Период08.06.201814.06.2018

Fingerprint Подробные сведения о темах исследования «A core heuristic and the branch-and-price method for a bin packing problem with a color constraint». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Kondakov, A., & Kochetov, Y. (2018). A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. В Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers (стр. 309-320). (Communications in Computer and Information Science; Том 871). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-93800-4_25