TITLE:
Hybrid Formulation of the Multi-Item Capacitated Dynamic Lot Sizing Problem
AUTHORS:
Mayank Verma, Renduchintala Raghavendra Kumar Sharma
KEYWORDS:
Capacitated Lot Sizing, Linear Relaxation, Strong Formulation, Hybrid Formulation, Branch-and-Bound
JOURNAL NAME:
American Journal of Operations Research,
Vol.5 No.6,
November
9,
2015
ABSTRACT:
It is shown that when backorders, setup times and dynamic demand are included in capacitated lot sizing problem, the resulting classical formulation and one of the transportation formulations of the problem (referred to as CLSP_BS) are equivalent. And it is shown that both the formulations are “weak” formulations (as opposed to “strong” formulation). The other transportation version is a strong formulation of CLSP_BS. Extensive computational studies are presented for medium and large sized problems. In case of medium-sized problems, strong formulation produces better LP bounds, and takes lesser number of branch-and-bound (B&B) nodes and less CPU time to solve the problem optimally. However for large-sized problems strong formulation takes more time to solve the problem optimally, defeating the benefit of strength of bounds. This essentially is because of excessive increase in the number of constraints for the large sized problems. Hybrid formulations are proposed where only few most promising strong constraints are added to the weak formulation. Hybrid formulation emerges as the best performer against the strong and weak formulations. This concept of hybrid formulation can efficiently solve a variety of complex real life large-sized problems.