Standard

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. p. 309-320 (Communications in Computer and Information Science; Vol. 871).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Kondakov, A & Kochetov, Y 2018, A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. in Optimization Problems and Their Applications - 7th International Conference, OPTA 2018, Revised Selected Papers. Communications in Computer and Information Science, vol. 871, Springer-Verlag GmbH and Co. KG, pp. 309-320, 7th International Conference on Optimization Problems and Their Applications, OPTA 2018, Omsk, Russian Federation, 08.06.2018. https://doi.org/10.1007/978-3-319-93800-4_25

APA

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

Vancouver

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

Author

Kondakov, Artem ; Kochetov, Yury. / 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. Springer-Verlag GmbH and Co. KG, 2018. pp. 309-320 (Communications in Computer and Information Science).

BibTeX

@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",

}

RIS

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