Solution of Nonlinear Programming Problems by Partitioning

An important class of mathematical programming problems is the scheduling of manufacturing and transportation systems. In many cases, the independent variables which describe the manufacturing system are interrelated in a highly nonlinear manner. The majority of the system variables are normally required to represent transportation and allocation. These variables appear linearly and must satisfy a system of equalities which is very large if considered as a single matrix.

With such systems it is usually possible to select a relatively small number of the system variables so that when these selected (decision or coupling) variables are held fixed the complete nonlinear system can be partitioned into a number of relatively small independent linear sub-problems.

An iterative method for the solution of such problems has been presented [Rosen, J. B. 1963. Convex partition programming. R. L. Graves, P. Wolfe, eds. Recent Advances in Mathematical Programming. McGraw Hill, 159–176.]. The method starts with initial values for the decision variables and solves the separate linear subproblems. The optimal solution to each subproblem is then used to determine that the complete system optimum has been found or to find improved values of the decision variables. This procedure is continued until the complete system optimum has been obtained.

Application of the Partition Programming method to a typical large manufacturing-transportation system will be described, including computational experience. This will illustrate that the method can be successfully used for systems which do not satisfy the mathematical requirements which insure convergence of the method to a global optimum. The economic interpretation of an optimal solution will be discussed, showing how the complete system shadow prices are obtained from those of the individual subproblems.