Top

Published in:

2018 | OriginalPaper | Chapter

A Core Heuristic and the Branch-and-Price Method for a Bin Packing Problem with a Color Constraint

Authors : Artem Kondakov, Yury Kochetov

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Genetic Algorithm for the Pooling-Inventory-Capacity Problem in Spare Part Supply Systems

next chapter On Calculation and Estimation of Flow Transmission Probability in a Communication Network

Avella, P., Boccia, M., Salerno, S., Vasilyev, I.: An aggregation heuristic for large scale p-median problem. Comput. Oper. Res. 39(7), 1625–1632 (2012)MathSciNetCrossRef

Balogh, J., Békési, J., Dosa, G., Kellerer, H., Tuza, Z.: Black and white bin packing. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 131–144. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38016-7_12CrossRefMATH

Böhm, M., Sgall, J., Veselý, P.: Online colored bin packing. In: Bampis, E., Svensson, O. (eds.) WAOA 2014. LNCS, vol. 8952, pp. 35–46. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18263-6_4CrossRefMATH

Dawande, M., Kalagnanam, J., Sethuraman, J.: Variable sized bin packing with color constraints. Electron. Not. Discrete Math. 7, 154–157 (2001)MathSciNetCrossRef

Ding C., Zhang Y., Li T., Holbrook S.R.: Biclustering protein complex interactions with a biclique finding algorithm. In: Sixth International Conference on Data Mining (ICDM 2006), pp. 178–187. IEEE (2006)

Farley, A.A.: A note on bounding a class of linear programming problems, including cutting stock problems. Oper. Res. 38(5), 922–923 (1990)CrossRef

Gschwind, T., Irnich, S.: Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1), 175–194 (2016)MathSciNetCrossRef

Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2015)

Jansen, K., Porkolab, L.: Preemptive parallel task scheduling in O(n) + Poly(m) time. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol. 1969, pp. 398–409. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-40996-3_34CrossRef

10.

Jansen, K.: An approximation scheme for bin packing with conflicts. J. Comb. Optim. 3(4), 363–377 (1999)MathSciNetCrossRef

11.

Kartak, V.M., Ripatti, A.V., Scheithauer, G., Kurz, S.: Minimal proper non-irup instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187, 120–129 (2015)MathSciNetCrossRef

12.

Kochetov, Yu., Ivanenko, D.: Computationally difficult instances for the uncapacitated facility location problem. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Problem Solvers, vol. 32, pp. 351–367. Springer, Boston (2005). https://doi.org/10.1007/0-387-25383-1_16CrossRef

13.

Kochetov, Yu., Kondakov, A.: VNS matheuristic for a bin packing problem with a color constraint. Electron. Not. Discrete Math. 58, 39–46 (2017)MathSciNetCrossRef

14.

Margot, F.: Symmetry in integer linear programming. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958–2008, pp. 647–686. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-540-68279-0_17CrossRefMATH

15.

Muritiba, A.E.F., Iori, M., Malaguti, E., Toth, P.: Algorithms for the bin packing problem with conflicts. Informs J. Comput. 22(3), 401–415 (2010)MathSciNetCrossRef

16.

Peeters, M., Degraeve, Z.: The co-printing problem: a packing problem with a color constraint. Oper. Res. 52(4), 623–638 (2004)MathSciNetCrossRef

17.

Shachnai, H., Tamir, T.: Polynomial time approximation schemes for class-constrained packing problems. J. Sched. 4(6), 313–338 (2001)MathSciNetCrossRef

18.

Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1), 111–128 (2000)MathSciNetCrossRef

19.

Xavier, E.C., Miyazawa, F.K.: The class constrained bin packing problem with applications to video-on-demand. Theoret. Comput. Sci. 393(1), 240–259 (2008)MathSciNetCrossRef

Title: A Core Heuristic and the Branch-and-Price Method for a Bin Packing Problem with a Color Constraint
Authors: Artem Kondakov
Yury Kochetov
Publisher: Springer International Publishing
Book: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_25

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner