VNS matheuristic for a bin packing problem with a color constraint

Y. Kochetov; A. Kondakov

doi:10.1016/j.endm.2017.03.006

VNS matheuristic for a bin packing problem with a color constraint

Y. Kochetov, A. Kondakov

Research output: Contribution to journal › Article › peer-review

8 Citations (Scopus)

Abstract

We study a new variant of the bin packing problem. Given a set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the union of colors for its items and can not exceed the bin capacity. We want to pack all items into the minimal number of bins. For this NP-hard problem we apply the column generation technique based on the VNS matheuristic for the pricing problem. To get optimal or near optimal solutions we apply VNS matheuristic again using optimal solution for the large scale linear programming relaxation. Computational experiments are reported for the randomly generated test instances with large bin capacity and number of items up to 250.

Original language	English
Pages (from-to)	39-46
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	58
DOIs	https://doi.org/10.1016/j.endm.2017.03.006
Publication status	Published - 1 Apr 2017

Keywords

column generation
large neighborhood
local search
Matheuristic

Access to Document

10.1016/j.endm.2017.03.006

Cite this

@article{7567997619fa42c98a98294bc341f012,

title = "VNS matheuristic for a bin packing problem with a color constraint",

abstract = "We study a new variant of the bin packing problem. Given a set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the union of colors for its items and can not exceed the bin capacity. We want to pack all items into the minimal number of bins. For this NP-hard problem we apply the column generation technique based on the VNS matheuristic for the pricing problem. To get optimal or near optimal solutions we apply VNS matheuristic again using optimal solution for the large scale linear programming relaxation. Computational experiments are reported for the randomly generated test instances with large bin capacity and number of items up to 250.",

keywords = "column generation, large neighborhood, local search, Matheuristic",

author = "Y. Kochetov and A. Kondakov",

year = "2017",

month = apr,

day = "1",

doi = "10.1016/j.endm.2017.03.006",

language = "English",

volume = "58",

pages = "39--46",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - VNS matheuristic for a bin packing problem with a color constraint

AU - Kochetov, Y.

AU - Kondakov, A.

PY - 2017/4/1

Y1 - 2017/4/1

N2 - We study a new variant of the bin packing problem. Given a set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the union of colors for its items and can not exceed the bin capacity. We want to pack all items into the minimal number of bins. For this NP-hard problem we apply the column generation technique based on the VNS matheuristic for the pricing problem. To get optimal or near optimal solutions we apply VNS matheuristic again using optimal solution for the large scale linear programming relaxation. Computational experiments are reported for the randomly generated test instances with large bin capacity and number of items up to 250.

AB - We study a new variant of the bin packing problem. Given a set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the union of colors for its items and can not exceed the bin capacity. We want to pack all items into the minimal number of bins. For this NP-hard problem we apply the column generation technique based on the VNS matheuristic for the pricing problem. To get optimal or near optimal solutions we apply VNS matheuristic again using optimal solution for the large scale linear programming relaxation. Computational experiments are reported for the randomly generated test instances with large bin capacity and number of items up to 250.

KW - column generation

KW - large neighborhood

KW - local search

KW - Matheuristic

UR - http://www.scopus.com/inward/record.url?scp=85017460790&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2017.03.006

DO - 10.1016/j.endm.2017.03.006

M3 - Article

AN - SCOPUS:85017460790

VL - 58

SP - 39

EP - 46

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -

VNS matheuristic for a bin packing problem with a color constraint

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this