@inproceedings{0ef8c490f7eb4e02a6c03c6359f67292,
title = "A core heuristic and the branch-and-price method for a bin packing problem with a color constraint",
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.",
keywords = "Branch-and-price, Column generation, Matheuristic",
author = "Artem Kondakov and Yury Kochetov",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 7th International Conference on Optimization Problems and Their Applications, OPTA 2018 ; Conference date: 08-06-2018 Through 14-06-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-93800-4_25",
language = "English",
isbn = "9783319937991",
series = "Communications in Computer and Information Science",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "309--320",
booktitle = "Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers",
address = "Germany",
}