Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. / Kondakov, Artem; Kochetov, Yury.
Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2018. стр. 309-320 (Communications in Computer and Information Science; Том 871).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - A core heuristic and the branch-and-price method for a bin packing problem with a color constraint
AU - Kondakov, Artem
AU - Kochetov, Yury
N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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.
AB - 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.
KW - Branch-and-price
KW - Column generation
KW - Matheuristic
UR - http://www.scopus.com/inward/record.url?scp=85049668595&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-93800-4_25
DO - 10.1007/978-3-319-93800-4_25
M3 - Conference contribution
AN - SCOPUS:85049668595
SN - 9783319937991
T3 - Communications in Computer and Information Science
SP - 309
EP - 320
BT - Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers
PB - Springer-Verlag GmbH and Co. KG
T2 - 7th International Conference on Optimization Problems and Their Applications, OPTA 2018
Y2 - 8 June 2018 through 14 June 2018
ER -
ID: 14464865