On the Polyhedral Structure of a Multi-Item Production Planning Model with Setup Times.

We present and study a mixed integer programing model that arises as a sub-structure in any industrial applications. This model provides a relaxation of various capacitated production planning problems, more general fixed charge network flow problems, and other structured mixed integer programs. After distinguishing the general case, which is NP -hard, from a polynomially solvable case, we analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation.