Back to Search
Start Over
A comparison of mixed integer programming formulations of the capacitated lot-sizing problem
- Source :
- International Journal of Production Research. 56:7064-7084
- Publication Year :
- 2017
- Publisher :
- Informa UK Limited, 2017.
-
Abstract
- We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulatio...
- Subjects :
- 0209 industrial biotechnology
Mathematical optimization
021103 operations research
Strategy and Management
Branch and price
0211 other engineering and technologies
CPU time
Binary number
02 engineering and technology
Management Science and Operations Research
Upper and lower bounds
Industrial and Manufacturing Engineering
Sizing
Linear programming relaxation
Matrix (mathematics)
020901 industrial engineering & automation
Integer programming
Mathematics
Subjects
Details
- ISSN :
- 1366588X and 00207543
- Volume :
- 56
- Database :
- OpenAIRE
- Journal :
- International Journal of Production Research
- Accession number :
- edsair.doi...........5055cdcd87c3cac3be1cad07b7deb069