×

Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem. (English) Zbl 1506.90219

Summary: The two-dimensional knapsack problem consists in packing a set of small rectangular items into a given large rectangle while maximizing the total reward associated with selected items. We restrict our attention to packings that emanate from a \(k\)-stage guillotine-cut process. We introduce a generic model where a knapsack solution is represented by a flow in a directed acyclic hypergraph. This hypergraph model derives from a forward labelling dynamic programming recursion that enumerates all non-dominated feasible cutting patterns. To reduce the hypergraph size, we make use of further dominance rules and a filtering procedure based on Lagrangian reduced costs fixing of hyperarcs. Our hypergraph model is (incrementally) extended to account for explicit bounds on the number of copies of each item. Our exact forward labelling algorithm is used to solve the max-cost flow model in the base hyper-graph with side constraints to model production bounds. Results of numerical comparison against existing approaches are reported on instances from the literature and on datasets derived from a real-world application.

MSC:

90C27 Combinatorial optimization
90C10 Integer programming
90C39 Dynamic programming

References:

[1] Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European J. Oper. Res., 183, 3, 1109-1130, (2007), URL http://dx.doi.org/10.1016/j.ejor.2005.12.047 · Zbl 1278.90347
[2] Gilmore, P. C.; Gomory, R. E., Multistage cutting stock problems of two and more dimensions, Oper. Res., 13, 1, 94-120, (1965), URL http://dx.doi.org/10.1287/opre.13.1.94 · Zbl 0128.39601
[3] Vanderbeck, F., A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem, Manage. Sci., 47, 6, 864-879, (2001), URL http://dx.doi.org/10.1287/mnsc.47.6.864.9809 · Zbl 1232.90326
[4] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Oper. Res., 25, 1, 30-44, (1977), URL http://dx.doi.org/10.1287/opre.25.1.30 · Zbl 0369.90059
[5] Beasley, J. E., Algorithms for unconstrained two-dimensional guillotine cutting, J. Oper. Res. Soc., 36, 4, 297-306, (1985), URL http://dx.doi.org/10.1057/jors.1985.51 · Zbl 0589.90040
[6] Russo, M.; Sforza, A.; Sterle, C., An improvement of the knapsack function based algorithm of gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem, Int. J. Prod. Econ., 145, 2, 451-462, (2013), URL https://doi.org/10.1016/j.ijpe.2013.04.031
[7] Russo, M.; Sforza, A.; Sterle, C., An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems, Comput. Oper. Res., 50, 97-114, (2014), URL http://dx.doi.org/10.1016/j.cor.2014.04.001 · Zbl 1348.90554
[8] Dolatabadi, M.; Lodi, A.; Monaci, M., Exact algorithms for the two-dimensional guillotine knapsack, Comput. Oper. Res., 39, 1, 48-53, (2012), URL http://dx.doi.org/10.1016/j.cor.2010.12.018 · Zbl 1251.90237
[9] Lodi, A.; Monaci, M., Integer linear programming models for 2-staged two-dimensional knapsack problems, Math. Program., 94, 2-3, 257-278, (2003), URL http://dx.doi.org/10.1007/s10107-002-0319-9 · Zbl 1030.90064
[10] Puchinger, J.; Raidl, G. R., Models and algorithms for three-stage two-dimensional bin packing, European J. Oper. Res., 183, 3, 1304-1327, (2007), URL http://dx.doi.org/10.1016/0377-2217(95)00128-X · Zbl 1135.90029
[11] Morabito, R.; Arenales, M. N., Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach, European J. Oper. Res., 94, 3, 548-560, (1996), URL http://dx.doi.org/10.1016/0377-2217(95)00128-X · Zbl 0947.90537
[12] Martin, R. K.; Rardin, R. L.; Campbell, B. A., Polyhedral characterization of discrete dynamic programming, Oper. Res., 38, 1, 127-138, (1990), URL http://dx.doi.org/10.1287/opre.38.1.127 · Zbl 0711.90066
[13] Valério de Carvalho, J. M., Exact solution of bin-packing problems using column generation and branch-and-bound, Ann. Oper. Res., 86, 629-659, (1999), URL http://dx.doi.org/10.1023/A:1018952112615 · Zbl 0922.90113
[14] Macedo, R.; Alves, C.; Valério de Carvalho, J. M., Arc-flow model for the two-dimensional guillotine cutting stock problem, Comput. Oper. Res., 37, 6, 991-1001, (2010), URL http://dx.doi.org/10.1016/j.cor.2009.08.005 · Zbl 1178.90292
[15] Kenyon, C.; Rémila, E., A near-optimal solution to a two-dimensional cutting stock problem, Math. Oper. Res., 25, 4, 645-656, (2000) · Zbl 0977.90043
[16] Seiden, S. S.; Woeginger, G. J., The two-dimensional cutting stock problem revisited, Math. Program., 102, 3, 519-530, (2005), URL https://doi.org/10.1007/s10107-004-0548-1 · Zbl 1078.90044
[17] Martinelli, R.; Pecin, D.; Poggi, M., Efficient elementary and restricted non-elementary route pricing, European J. Oper. Res., 239, 1, 102-111, (2014), URL http://dx.doi.org/10.1016/j.ejor.2014.05.005 · Zbl 1339.90061
[18] Irnich, S.; Desaulniers, G.; Desrosiers, J.; Hadjar, A., Path-reduced costs for eliminating arcs in routing and scheduling, INFORMS J. Comput., 22, 2, 297-313, (2010), URL http://dx.doi.org/10.1287/ijoc.1090.0341 · Zbl 1243.90064
[19] Detienne, B.; Sadykov, R.; Tanaka, S., The two-machine flowshop total completion time problem: branch-and-bound algorithms based on network-flow formulation, European J. Oper. Res., 252, 3, 750-760, (2016), URL http://dx.doi.org/10.1016/j.ejor.2016.02.003 · Zbl 1346.90337
[20] Furini, F.; Malaguti, E.; Thomopulos, D., Modeling two-dimensional guillotine cutting problems via integer programming, INFORMS J. Comput., 28, 4, 736-751, (2016) · Zbl 1355.90081
[21] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Program., 6, 1, 62-88, (1974), URL http://dx.doi.org/10.1007/BF01580223 · Zbl 0284.90057
[22] Sadykov, R.; Vanderbeck, F., Column generation for extended formulations, EURO J. Comput. Optim., 1, 1-2, 81-115, (2013), URL http://dx.doi.org/10.1007/s13675-013-0009-9 · Zbl 1305.90312
[23] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 3, 155-170, (2008), URL http://dx.doi.org/10.1002/net.v51:3 · Zbl 1144.90514
[24] Christofides, N.; Hadjiconstantinou, E., An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts, European J. Oper. Res., 83, 1, 21-38, (1995), URL http://dx.doi.org/10.1016/0377-2217(93)E0277-5 · Zbl 0903.90134
[25] Ibaraki, T.; Nakamura, Y., A dynamic programming method for single machine scheduling, European J. Oper. Res., 76, 1, 72-82, (1994), URL http://dx.doi.org/10.1016/0377-2217(94)90007-8 · Zbl 0806.90064
[26] Hifi, M.; Roucairol, C., Approximate and exact algorithms for constrained (un) weighted two-dimensional two-staged cutting stock problems, J. Comb. Optim., 5, 4, 465-494, (2001), URL http://dx.doi.org/10.1023/A:1011628809603 · Zbl 1135.90389
[27] Hadjiconstantinou, E.; Iori, M., A hybrid genetic algorithm for the two-dimensional single large object placement problem, European J. Oper. Res., 183, 3, 1150-1166, (2007), URL http://dx.doi.org/10.1016/j.ejor.2005.11.061 · Zbl 1146.90481
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.