Triangularity of the basis in linear programs for material requirements planning (Q1119175)

In material requirements planning (MRP) one seeks a production schedule minimizing the costs of producing and inventory holding of several products, either assembly parts of other products or finished goods. It is assumed that the assembly structure is fixed and the demand of finished goods is known over a finite horizon. This problem may be stated as a linear program, but with seemingly prohibitive dimensions. For the case of a single finished product and no limits on production and storage, it is shown that any basis of the corresponding LP is triangular, hence easy to solve. The authors suggest to exploit this property in a decomposition approach for the general problem in combination with parallel processing.