Using extended MIP formulations for a production/sequencing and a production/distribution problem

In this chapter we consider ways in which extended formulations (EFs) can be used computationally. We develop simple hybrid heuristics that use the EFs to get good dual bounds and decide on variables to be fixed, and formulations in the original space of variables to provide feasible solutions and good primal solutions. We also consider ways to further improve the dual bounds using a variant of Benders' algorithm. A few instances, two problems, discrete lot-sizing with start-ups on identical parallel machines, and two-level production/transportation, are used to demonstrate the approach, and for each problem computational results on a handful of instances are presented