A column-generation approach to the multiple knapsack problem with color constraints We study a new problem that we refer to as the multiple knapsack with color constraints (MKCP). Motivated by a real application from the steel industry, the MKCP can be formulated by generalizing the multiple knapsack problem. A real-life instance (called mkc) of this problem class is available through MIPLIB [R. E. Bixby, http://www.caam.rice.edu/ bixby/miplib/miplib3.html (2004)] and a larger instance (mkc7) is downloadable from the COIN site (IBM 2004). The focus of this paper is to present improved computational results for the two mentioned instances of this problem using a column-generation approach. We solve mkc to optimality and use Dantzig-Wolfe decomposition for upper bounding the other instance. Solving mkc to optimality took less time than it takes to solve the LP relaxation of the original formulation. The larger instance is solved to near optimality (within 0.5% of optimality) in a fraction of the time required to solve the original relaxed LP.
Keywords for this software
References in zbMATH (referenced in 3 articles )
Showing results 1 to 3 of 3.
- Koch, Thorsten; Achterberg, Tobias; Andersen, Erling; Bastert, Oliver; Berthold, Timo; Bixby, Robert E.; Danna, Emilie; Gamrath, Gerald; Gleixner, Ambros M.; Heinz, Stefan; Lodi, Andrea; Mittelmann, Hans; Ralphs, Ted; Salvagnin, Domenico; Steffy, Daniel E.; Wolter, Kati: MIPLIB 2010. Mixed integer programming library version 5 (2011)
- Song, Sang Hwa: A nested column generation algorithm to the meta slab allocation problem in the steel making industry (2009)
- Forrest, John J.H.; Kalagnanam, Jayant; Ladanyi, Laszlo: A column-generation approach to the multiple knapsack problem with color constraints (2006)