A hybrid VNS matheuristic for a bin packing problem with a color constraint
DOI:
https://doi.org/10.2298/YJOR200117009KKeywords:
VNS, Matheuristic, Local Search, Large Neighborhood, Column GenerationAbstract
We study a new variant of the bin packing problem with a color constraint. Given a finite 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 unification of colors for its items and cannot exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem, we present approximability results and design a hybrid matheuristic based on the column generation technique. A hybrid VNS heuristic is applied to the pricing problem. The column generation method provides a lower bound and a core subset of the most promising bin patterns. Fast heuristics and exact solution for this core produce upper bounds. Computational experiments for test instances with number of items up to 500 illustrate the efficiency of the approach.References
Alekseeva, E., Kochetov, Yu., and Plyasunov, A. “An exact method for the discrete (r|p) centroid problem”, Journal of Global Optimization, 63 (3) (2015) 445–460.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. Complexity and approximation: Combinatorial optimization problems and their approximability properties, Springer Science & Business Media, 2012.
Ausiello, G., D’Atri, A., and Protasi, M. “Structure preserving reductions among convex optimization problems”, Journal of Computer and System Sciences, 21 (1) (1980) 136–153.
Avella, P., Boccia, M., Salerno, S., and Vasilyev, I. “An aggregation heuristic for large scale p-median problem”, Computers & Operations Research, 39 (7) (2012) 1625–1632.
Balogh, J., Békési, J., Dosa, G., Kellerer, H., and Tuza, Z. Black and white bin packing, Approximation and Online Algorithms, Springer, 2012, 131–144.
Böhm, M., Sgall, J., and Veselý, P. Online colored bin packing, In: Bampis E. Svensson O. (eds) Approximation and Online Algorithms, WAOA 2014, Lecture Notes in Computer Science, vol 8952, Springer, Cham., 35–46.
Chvatal, V. “A greedy heuristic for the set-covering problem”, Mathematics of Operations Research, 4 (3) (1979) 233–235.
Coffman Jr, E.D., Garey, M.R., and Johnson D.S. Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, pages 46–93. PWS Publishing Co., Boston, MA, United States, 1996.
Kochetov, Yu., Davydov, I., and Carrizosa, E. “A local search heuristic for the (r|p) centroid problem in the plane”, Computers & Operations Research, 52 (B) (2014) 334–340.
Dawande, M., Kalagnanam, J., and Sethuraman J. “Variable sized bin packing with color constraints”, Electronic Notes in Discrete Mathematics, 7 (2001) 154–157.
Ding, C., Zhang, Ya., Li, T., and Holbrook, S. R. Biclustering protein complex interactions with a biclique finding algorithm, Sixth International Conference on Data Mining (ICDM’06), Hong Kong, China, IEEE, 2006, 178–187.
Dinur, I., Steurer, D. Analytical approach to parallel repetition, Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, NY, United States, May 2014, 624–633.
Farley, A.A. “A note on bounding a class of linear programming problems, including cutting stock problems”, Operations Research, 38 (5) (1990) 922–923.
Fleischner, H., Mujuni, E., Paulusma, D., and Szeider, S. “Covering graphs with few complete bipartite subgraphs”, Theoretical Computer Science, 410 (21) (2009) 2045–2053.
Gschwind, T., and Irnich, S. “Dual inequalities for stabilized column generation revisited”, INFORMS Journal on Computing, 28 (1) (2016) 175–194.
Inc. Gurobi Optimization, Gurobi optimizer reference manual, 2015.
Hansen, P., and Mladenović, N. “Variable neighborhood search: Principles and applications”, European Journal of Operational Research, 130 (3) (2001) 449–467.
Jansen, K. “An approximation scheme for bin packing with conflicts”, Journal of Combinatorial Optimization, 3 (4) (1999) 363–377.
Kochetov, Yu.A. Facility location: discrete models and local search methods. In Chvatal V., editor, Combinatorial Optimization. Methods and Applications, IOS Press, Amsterdam, Netherlands, 2011, 97–134.
Kochetov, Yu.A., and Kondakov, A.A. “VNS matheuristic for a bin packing problem with a color constraint”, Electronic Notes on Discrete Mathematics, 58 (2017) 39–46.
Muritiba, A.E.F., Iori, M., Malaguti, E., and Toth, P. “Algorithms for the bin packing problem with conflicts”, INFORMS Journal on Computing, 22 (3) (2010) 401–415.
Peeters, M., and Degraeve, Z. “The co-printing problem: A packing problem with a color constraint”, Operations Research, 52 (4) (2004) 623–638.
Shachnai, H., and Tamir, T. “Polynomial time approximation schemes for class-constrained packing problems”, Journal of Scheduling, 4 (6) (2001) 313–338.
Vanderbeck, F. “Computational study of a column generation algorithm for bin packing and cutting stock problems”, Mathematical Programming, 86 (3) (1999) 565–594.
Xavier, E.C., and Miyazawa, F.K. “The class constrained bin packing problem with applications to video-on-demand”, Theoretical Computer Science, 393 (1) (2008) 240–259.
Downloads
Published
Issue
Section
License
Copyright (c) 2021 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
