On the polyhedral structure of a multi–item production planning model with setup times |
| |
Authors: | Andrew J Miller George L Nemhauser Martin WP Savelsbergh |
| |
Institution: | (1) University of Wisconsin, Department of Industrial Engineering, Madison, WI 53706-1572,, US;(2) Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, GA 30332-0205, US |
| |
Abstract: | We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This
model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated
production planning problems and other fixed charge network flow problems. 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 under certain conditions. We also discuss how to strengthen these inequalities by using known results
for lifting valid inequalities for 0–1 continuous knapsack problems.
Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002
Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network
flow
Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations
of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors.
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|