(74c) Polyhedral Results for Discrete-Time Production Planning MIP Formulations

The scheduling and production planning of multi-product facilities has received considerable attention in the process systems engineering literature. The focus of most of the proposed approaches has been on the development of mixed-integer programming (MIP) formulations that are shown to address effectively a special class of problems. The quality of such formulations is typically assessed from the computational requirements for the solution of a limited set of example problems. In general, it can be argued that the development of MIP models for the scheduling of chemical processes has been guided by empirical (computational) rather than theoretical results. This is in sharp contrast with efforts on production planning in the operations research and mathematical programming communities, where the development of reformulations and the derivation of theoretical results concerning the structure and tightness of MIP formulations is the method of choice. The advantage of this more rigorous approach is that these results and reformulations point the way to effective solution methods. In this work, we follow the latter approach. We study the polyhedral properties of a discrete-time MIP formulation for the production planning of multi-stage multi-product continuous processes.

First, we review concepts and known results on polyhedral theory and mixed-integer programming. We introduce the basic concepts about polyhedra and polytopes (Cook et al., 1997), discuss how total unimodularity ensures the integrality of polyhedra (Nemhauser and Wolsey, 1988; Hoffman and Kruskal, 1956), and present properties of totally unimodular matrices. We then discuss total k-modularity and k-regularity, the two generalizations of total unimodularity to general matrices (Appa and Kotnyek, 2004), and review existing results and prove one new result for the characterization of k-regular matrices. We close this part with a short discussion of decomposition methods and reformulations (Pochet and Wolsey, 2006).

Second, we develop new results for the discrete-time production planning MIP formulation of (Maravelias, 2006). The original problem is decomposed into two subproblems, one that involves only assignment variables and constraints, and one that involves assignment and inventory variables and material balance constraints. We show that the constraint matrix of the first subproblem is an ?interval? matrix (Fulkerson and Gross, 1965), and thus the feasible region of the LP-relaxed problem is integral. We next derive results for the second subproblem:

1) We show that the constraint matrix is k-regular for integral data.

2) We determine the length of the planning period for which the k-regularity of the matrix implies the integrality of the LP-relaxed feasible region.

3) We show that the LP-relaxed feasible region of the second subproblem is bounded (i.e. it is a polytope).

4) We generalize our results for rational data.

The aforementioned polyhedral results enable us to develop the tightest possible formulation for the second subproblem, thus leading to the tightest MIP formulation for the original problem.

Third, we develop similar polyhedral results for two additional production planning formulations: one that includes demand backlog variables and one that includes demand backlog and shipment variables.

Fourth, we derive a series of stronger results regarding total unimodularity for special classes of problems (e.g. single-source processing units, sequential process structures) and we discuss connections between the polyhedral results we develop in this work and generalized network matrices (Ahuja et al., 1993). We also outline how specialized algorithms, such as the generalized network simplex, can be used to solve efficiently special cases of the production planning problem.

Finally, we discuss how the proposed results can be used to address large scale production planning problems and present computational results for a collection of example problems. We study a problem with three stages, five processing units, 11 chemicals and 13 tasks over a planning period of eight weeks. We study the effect of the length of the planning period and show how we can select the planning period that yields a MIP formulation with very small integrality gap. We also discuss how problem data can be modified to produce ?easy? MIP models and what the practical implication of k-regularity is. We close with the presentation of computational results for larger instances (11 processing units, 37 tasks, 31 chemicals), where a planning horizon of 8 weeks is divided into planning periods of 3-12 hours, resulting in MIP formulations with thousands of binary variables and constraints. We show how our work can be used to address these problems to optimality in reasonable computational time.

References:

Ahuja, R.K.; Magnanti, T.L.; Orlin J.B. Network Flows, Prentice Hall, 1993.

Appa, G.; Kotnyek, B. Rational and integral k-regular matrices. Discrete Mathematics, 275, 1-15, 2004.

Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijver, A. Combinatorial Optimization. Wiley-Interscience, 1997.

Hoffman, A. J.; Kruskal, J. B. Integral Boundary Points of Convex Polyhedra. In Linear Inequalities and Related Systems (Editors: Kuhn, H. W.; Tucker, A. W.), Princeton University Press, Princeton, 1956. (223-246).

Maravelias, C. T. Mixed Time Representation for State-Task Network Models. Ind. Eng. Chem. Res., 44 (24), 9129-9145, 2005.

Nemhauser, G.L.; Wolsey, L.A. Integer and Combinatorial Optimization, John Willey and Sons, Inc., New York, 1989.

Pochet, Y.; Wolsey, L.A. Production Planning by Mixed Integer Programming. Springer, 2006.