Facets, algorithms, and polyhedral characterizations for a multi-item production planning model with setup times

Miller, A.J.;Nemhauser, G.L.;Savelsbergh, M.W.P.
(2001) Integer Programming and Combinatorial Optimization. 8th International IPCO Conference. Proceedings — Location: Utrecht, Netherlands (13.June.2001)

Files

No attached file found for this publication.

Details

Authors
  • Miller, A.J.
    Author
  • Nemhauser, G.L.
    Author
  • Savelsbergh, M.W.P.
    Author
Abstract
We present and study a mixed integer programming model that arises as a substructure in many 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. We analyze the polyhedral structure of the convex hull of this model; among other results, we present valid inequalities that induce facets of the convex hull in the general case, which is NP-hard. We then present an extended formulation for a polynomially solvable case for which the LP always gives an integral solution. Projecting from this extended formulation, we show that the inequalities presented for the general model suffice to solve this polynomially solvable case by linear programming in the original variable space.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Miller, A. J., Nemhauser, G. L., & Savelsbergh, M. W. P. (2001). Facets, algorithms, and polyhedral characterizations for a multi-item production planning model with setup times. In Aardal, K.; Gerards, B.; (ed.), Integer Programming and Combinatorial Optimization. 8th InternationalIPCO Conference. Proceedings (Lecture Notes in Computer ScienceVol.2081) (p. p. 318-332). Springer-verlag. https://hdl.handle.net/2078.5/221030