(356a) On the Combinatorial Properties of Discrete-Time Production Planning and Scheduling MIP Models for Continuous Processes

We develop a series of combinatorial results for mixed-integer programming formulations for production planning and scheduling. We study the widely used discrete-time formulations for production planning of continuous processes. The difficulty to solve fast the general case of these models may suggest that there exist certain important special cases which might be solved fast by specialized algorithms of combinatorial nature.

In this work we show that for a set of important special cases, the constraint matrices of these problems belong to known classes of matrices in the combinatorial optimization literature. Specifically, we study certain five important cases and prove that the constraint matrices of the associated problems fall in one of the following categories of matrices: network, totally unimodular, binet or 2-regular. Totally unimodular matrices are of great importance in combinatorial optimization since they define a special class of polynomial time solvable integer programs. Specifically, every integer program whose constraint matrix is totally unimodular matrix can be solved as a linear program by relaxing the integrality constraint since the associated polyhedron is integral. Network matrices, an important subclass of totally unimodular matrices, are defined on directed graphs. The underlying graphical structure of network matrices made possible to devise very fast methods to solve the associated integer programming problem (e.g. network simplex method); it has been reported in the relevant literature that the network simplex method can be up to 200 times faster than the general-purpose linear programming methods. In this work we prove that there are special cases whose constraint matrices are network or totally unimodular and thereby, very fast methods are available.

Recently, it has been shown that these advantages of network matrices can be extended to their bidirected graph generalization, the binet matrices. Specifically, it has been shown that there exists a strongly polynomial algorithm for the class of binet integer programming problems. The solvability of these cases are due to the fact that all the aforementioned classes of matrices define polyhedra which have very interesting integrality properties (e.g. for any right-hand-side vector with even number, the polyhedron associated with a 2-regular matrix is integral) which are also discussed in this work.

The proposed results can be used in multiple ways to enhance the solution of more general problems. For example, for general batchsizes, we can show that the corresponding matrices are ê-regular. This is because ê-regularity is preserved under several matrix operations and because row (or column) multiplication/division weakens/preserves ê-regularity. Also, we show that more general problems with shipments of raw materials and products, as well as problems with shipments and backlogged demand lead to formulations whose incidence matrices have similar properties.