A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

We study a special case of a structured mixed integer programming model that arises in a number of applications. For the most general case of the model, called PI, we have earlier analyzed the polyhedral structure (Miller et al. [2000a]), including identifying facet-defining valid inequalities. PI is N P-hard; in this paper we focus on a special case, called PIC, that is polynomially solvable. We describe a polynomial algorithm for PIC, and we then use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that the set of inequalities presented for PI in Miller et al. [2000a] is sufficient to enable us to solve the special case PIC by linear programming. Finally, for PIC, we describe fast combinatorial separation algorithms for these inequalities.