Article ID: | iaor2004975 |
Country: | Germany |
Volume: | 94 |
Issue: | 2/3 |
Start Page Number: | 375 |
End Page Number: | 405 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Savelsbergh M.W.P., Nemhauser G.L., Miller A.J. |
Keywords: | programming: integer |
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.