Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 237, Issue 2, Pages 498-507Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2014.02.027
Keywords
Manufacturing; Discrete lot-sizing and scheduling problem; Sequence-dependent changeover costs and times; Quadratically constrained quadratic binary programming; Semidefinite relaxation; Cutting planes
Funding
- French National Research Agency through JCJC2011 for young researchers [ANR-11-JS0002-01]
Ask authors/readers for more resources
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. (C) 2014 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available