(198e) Polyhedral Results for a Discrete-Time Mip Formulation for Production Planning

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 solve well a class of problems. The quality of such formulations is typically assessed from the computational requirements for the solution of a 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 decomposition 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 [Kotnyek, 2002; 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 (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 show how the proposed results can be used to address large scale production planning 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 our results enable us to select the planning period that yield a MIP formulation with zero integrality gap that is solved in few seconds. We also present results for larger instances, where planning horizons of 6-12 weeks are divided into planning periods of 3-6 hours, resulting in MIP formulations with thousands of binary variables and constraints. We show how our results can be used to address these problems to optimality in reasonable computational time.

References:

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

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).

Kotnyek, B. (2002). A generalization of totally unimodular and network matrices. PhD Thesis, London School of Economics and Political Science, London, UK.

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

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.