Tight MIP Formulations for Bounded Up/Down Times and Interval-Dependent Start-Ups

Switching machines on and off is an important aspect of unit commitment problems and production planning problems, among others. Here we study tight mixed integer program- ming formulations for two aspects of such problems: bounded length on- and off-intervals, and interval-dependent start-ups. For the problem with both these aspects we develop a tight (convex hull) formulation involving additional variables. For the bounded interval problem we present a tight net- work dual formulation based on new integer variables that allows us to simultaneously treat lower and upper bounds on the interval lengths. This in turn leads to more general results, including simpler proofs of known tight formulations for problems with just lower bounds. For the interval-dependent start-up problem we develop a path formulation that allows us to describe the convex hull of solutions in the space of machine-on and interval-dependent start-up variables