On the polyhedral structure of a multi-item production planning model with setup times
AbstractWe 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. After distinguishing the general case, which is N P-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. Among other results, we present valid inequalities that induce facets of the convex hull in the general case. These inequalities suffice to solve this model by linear programming in the polynomially solvable case mentioned above, and they have proven computationally effective in solving capacitated lot-sizing problems (see also Miller et al. [2000a, 2000b]).
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2000052.
Date of creation: 00 Nov 2000
Date of revision:
Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
Mixed integer programming; production planning; polyhedral combinatorics; capacitated lot-sizing; ﬁxed charge network ﬂow.;
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS).
If references are entirely missing, you can add them using this form.