An evaluation of semidefinite programming based approaches for discrete lot-sizing problems. (English) Zbl 1304.90010
Summary: The present work is intended as a first step towards applying semidefinite programming models and tools to discrete lot-sizing problems including sequence-dependent changeover costs and times. Such problems can be formulated as quadratically constrained quadratic binary programs. We investigate several semidefinite relaxations by combining known reformulation techniques recently proposed for generic quadratic binary problems with problem-specific strengthening procedures developed for lot-sizing problems. Our computational results show that the semidefinite relaxations consistently provide lower bounds of significantly improved quality as compared with those provided by the best previously published linear relaxations. In particular, the gap between the semidefinite relaxation and the optimal integer solution value can be closed for a significant proportion of the small-size instances, thus avoiding to resort to a tree search procedure. The reported computation times are significant. However improvements in SDP technology can still be expected in the future, making SDP based approaches to discrete lot-sizing more competitive.
Keywords:
manufacturing; discrete lot-sizing and scheduling problem; sequence-dependent changeover costs and times; quadratically constrained quadratic binary programming; semidefinite relaxation; cutting planesReferences:
| [1] | Anjos, M. F.; Kennings, A.; Vannelli, A., A semidefinite optimization approach of the single-row layout problem with unequal dimensions, Discrete Optimization, 2, 113-122 (2005) · Zbl 1077.90046 |
| [2] | Belvaux, G.; Wolsey, L. A., Modelling practical lot-sizing problems as mixed-integer programs, Management Science, 47, 7, 993-1007 (2001) · Zbl 1232.90169 |
| [3] | Benson, S. J.; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal on Optimization, 10, 2, 443-461 (2000) · Zbl 0997.90059 |
| [4] | Buschkühl, L.; Sahling, F.; Helber, S.; Tempelmeier, H., Dynamic capacitated lot-sizing problems: Classification and review of solution approaches, OR Spectrum, 32, 231-261 (2010) · Zbl 1183.90162 |
| [5] | Dastidar, S. G.; Nagi, R., Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs, Computers & Operations Research, 32, 2987-3005 (2005) · Zbl 1071.90529 |
| [6] | Engau, A., Recent progress in interior-point methods: Cutting-plane methods and warm starts, (Handbook of semidefinite, conic and polynomial optimiztion. Handbook of semidefinite, conic and polynomial optimiztion, International series in operations research and management science (2012), Springer), 471-488 · Zbl 1334.90101 |
| [7] | Eppen, G. D.; Martin, R. K., Solving multi-item capacitated lot-sizing problems using variable redefinition, Operations Research, 35, 6, 832-848 (1987) · Zbl 0639.90046 |
| [8] | Ferreira, D.; Clark, A. R.; Almada-Lobo, B.; Morabito, R., Single-stage formulations for synchronized two-stage lot-sizing and scheduling in soft drink production, International Journal of Production Economics, 136, 255-265 (2012) |
| [9] | Fleischmann, B., The discrete lot sizing and scheduling problem, European Journal of Operational Research, 44, 337-348 (1990) · Zbl 0689.90043 |
| [10] | Gicquel, C.; Minoux, M.; Dallery, Y., On the discrete lot-sizing and scheduling problem with sequence-dependent changeover times, Operations Research Letters, 37, 32-36 (2009) · Zbl 1154.90552 |
| [11] | Gicquel, C.; Minoux, M.; Dallery, Y., Exact solution approaches for the discrete lot-sizing and scheduling problem with identical parallel resources, International Journal of Production Research, 49, 9, 2587-2603 (2011) · Zbl 1211.90071 |
| [12] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088 |
| [14] | Helmberg, C., Semidefinite programming, European Journal of Operational Research, 137, 3, 461-482 (2002) · Zbl 1008.90044 |
| [15] | Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM Journal of Optimization, 10, 3, 673-696 (2000) · Zbl 0960.65074 |
| [16] | Helmberg, C.; Rendl, F.; Weismantel, R., A semidefinite programming approach to the quadratic knapsack problem, Journal of Combinatorial Optimization, 4, 2, 197-215 (2000) · Zbl 0970.90075 |
| [17] | Jans, R.; Degraeve, Z., Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches, European Journal of Operational Research, 177, 1855-1875 (2007) · Zbl 1102.90002 |
| [18] | Jans, R.; Degraeve, Z., Modelling industrial lot sizing problems: A review, Industrial Journal of Production Research, 46, 6, 1619-1643 (2008) · Zbl 1160.90407 |
| [20] | Lovàsz, B.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM Journal on Optimization, 1, 166-190 (1991) · Zbl 0754.90039 |
| [21] | Mhanna, S.; Jabr, R., Application of semidefinite programming relaxation and selective pruning to the unit commitment problem, Electric Power System Research, 90, 85-92 (2012) |
| [22] | Pochet, Y.; Wolsey, L. A., Production planning by mixed integer programming (2006), Springer Science · Zbl 1102.90039 |
| [23] | Poljak, S.; Rendl, F.; Wolkowicz, H., A recipe for semidefinite relaxation of (0-1) quadratic programming, Journal of Global Optimization, 7, 51-73 (1995) · Zbl 0843.90088 |
| [24] | Povh, J.; Rendl, F., Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optimisation, 6, 231-241 (2009) · Zbl 1167.90597 |
| [25] | Rendl, F., Semidefinite relaxations for partitioning, assignment and ordering problems, 40R-Quaterly Journal of Operations Research, 10, 321-346 (2012) · Zbl 1262.90150 |
| [26] | Roupin, F., From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems, Journal of Combinatorial Optimization, 8, 469-493 (2004) · Zbl 1079.90085 |
| [27] | Salomon, M.; Solomon, M.; van Wassenhove, L.; Dumas, Y.; Dauzère-Pérès, S., Solving the discrete lotsizing and scheduling problem with sequence dependant set-up costs and set-up times using the travelling salesman problem with time windows, European Journal of Operational Research, 100, 494-513 (1997) · Zbl 0918.90087 |
| [28] | Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3, 3, 411-430 (1990) · Zbl 0712.90050 |
| [29] | Silva, C.; Magalhaes, J. M., Heuristic lot size scheduling on unrelated parallel machines with applications in the textile industry, Computers & Industrial Engineering, 50, 79-89 (2006) |
| [30] | Skutella, M., Convex quadratic and semidefinite programming relaxations in scheduling, Journal of the ACM, 48, 2, 206-242 (2001) · Zbl 1323.90024 |
| [31] | van Eijl, C. A.; van Hoesel, C. P.M., On the discrete lot-sizing and scheduling problem with Wagner-Whitin costs, Operations Research Letters, 20, 7-13 (1997) · Zbl 0889.90084 |
| [32] | Wagner, H. M.; Whitin, T. M., Dynamic version of the economic lot size model, Management Science, 5, 1, 89-96 (1958) · Zbl 0977.90500 |
| [33] | Yamashita, M.; Fujisawa, K.; Fukuda, M.; Kobayashi, K.; Nakata, K.; Nakata, M., Latest developments in the SDPA family for solving large-scale SDPs, (Handbook on semidefinite, conic and polynomial optimization. International series in operations research and management science (2012), Springer), 687-714 · Zbl 1334.90119 |
| [34] | Zhao, Q.; Kharisch, S. E.; Rendl, F.; Wolkovicz, H., Semidefinite programming relaxations for the quadratic assignment problem, Journal of Combinatorial Optimization, 2, 71-109 (1998) · Zbl 0904.90145 |
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.
