An Algorithm for Structured, Large-Scale Quadratic Programming Problems

摘要

An algorithm for structured, large-scale, convex quadratic programming problems is described. The structure of the constraint matrix is block diagonal with a small number of coupling constraints and variables. The algorithm utilizes twice a decomposition procedure that was developed earlier. The first time the decomposition procedure is used to break up the coupling constraints, and the second time it is used to break up the coupling variables. Preliminary computational results are also reported. The block diagonal structure with a small number of coupling constraints and variables usually arises from the formulation of multitime period and multidivision production scheduling and distribution models in large corporations. Each block is concerned with the operation of one division during one time period considered in isolation. The coupling constraints arise from the use of common resources of all divisions or from combining the output of divisions to meet overall demands. The coupling variables represent activities that affect the operation of divisions in more than one time period.