Large-Scale Systems12As mathematical-programming techniques and computer capabilities evolve, the spectrum of potential appli-cations also broadens. Problems that previously were considered intractable, from a computational point ofview, now become amenable to practical mathematical-programming solutions. Today, commercial linear-programming codes can solve general linear programs of about 4000 to 6000 constraints. Although this isan impressive accomplishment, many applied problems lead to formulations that greatly exceed this existingcomputational limit. Two approaches are available to deal with these types of problems.One alternative, that we have discussed in Chapter 5, leads to the partitioning of the overall problem intomanageable subproblems, which are linked by means of a hierarchical integrative system. An application ofthis approach was presented in Chapter 6, where two interactivelinear-programming models were designedto support strategic and tactical decisions in the aluminum industry, including resource acquisition, swappingcontracts, inventory plans, transportation routes, production schedules and market-penetration strategies.This hierarchical method of attacking large problems is particularly effective when the underlying managerialprocess involves various decision makers, whose areas of concern can be represented by a specific part ofthe overall problem and whose decisions have to be coordinated within the framework of a hierarchicalorganization.Some large-scale problems are not easily partitioned in this way. They present a monolithic structurethat makes the interaction among the decision variables very hard to separate, and lead to situations whereinthere is a single decision maker responsible for the actions to be taken, and where the optimal solution isverysensitivetothe overallvariable interactions. Fortunately, theselarge-scaleproblems invariably containspecialstructure. The large-scale system approach is to treat the problem as a unit, devising specialized algorithmsto exploit the structure of the problem. This alternative will be explored in this chapter, where two of the mostimportant large-scale programming procedures—decomposition and column generation—will be examined.The idea of taking computational advantage of the special structure of a specific problem to develop anefficient algorithm is not new. The upper-bounding technique introduced inChapter 2, the revised simplex method presented in Appendix B, and the network-solution procedures dis-cussed in Chapter 8 all illustrate this point. This chapter further extends these ideas.12.1 LARGE-SCALE PROBLEMSCertain structural forms of large-scale problems reappear frequently in applications, and large-scale systemstheory concentrates on the analysis of these problems. In this context, structure means the pattern of zero andnonzero coefficients in the constraints; the most important such patterns are depicted in Fig. 12.8. The firstillustration represents a problem composed of independent subsystems. It can be written as:MinimizerXj=1cjxj+sXj=r+1cjxj+nXj=s+1cjxj,363364 Large-Scale Systems 12.1subject to:rPj=1aijxj= bi(i = 1, 2, . . . , t),sPj=r+1aijxj= bi(i = t + 1, t + 2, . . . , u),nPj=s+1aijxj= bi(i = u + 1, u + 2, . . . , m),xj≥ 0 ( j = 1, 2, . . . , n).Observethatthevariablesx1, x2, . . . , xr, thevariablesxr+1, xr+2, . . . , xs, andthevariablesxs+1, xs+2, . . . , xndo not appear in common constraints. Consequently, these variables are independent, and the problem can beapproached by solving one problem in the variables x1, x2, . . . , xr, another in the variables xr+1, xr+2, . . . , xsand a third in the variables xs+1, xs+2, . . . , xn. This separation into smaller and independent subproblemshas several important implications.First, it provides significant computational savings, since the computations for linear programs are quitesensitive to m, the number of constraints, in practice growing proportionally to m3. If each subproblem abovecontains13of the constraints, then the solution to each subproblem requires on the order of (m/3)3= m3/27computations. All three subproblems then require about 3(m3/27) = m3/9 computations, or approximately19the amount for an m-constraint problem without structure. If the number of subsystems were k, thecalculations would be only 1/k2times those required for an unstructured problem of comparable size.Figure 12.112.1 Large-Scale Problems 365Second, each of the independent subproblems can be treated separately. Data can be gathered, analyzed,and stored separately. The problem also can be solved separately and, in fact, simultaneously. Each ofthese features suggests problems composed solely with independent subsystems as the most appealing of thestructured problems.The most natural extensions of this model are to problems with nearly independent subsystems, asillustrated by the next three structures in Fig. 12.8. In the primal block angular structure, the subsystemvariables appear together, sharing common resources in the uppermost ‘‘coupling’’ constraints. For example,the subsystems might interact via a corporate budgetary constraint specifying that total capital expendituresof all subsystems cannot exceed available corporate resources.The dual block angular structure introduces complicating ‘‘coupling’’ variables. In this case, the subsys-tems interact only by engaging in some common activities. For example, a number of otherwise independentsubsidiaries of a company might join together in pollution-abatement activities that utilize some resourcesfrom each of the subsidiaries.The bordered angular system generalizes these models by including complications from both couplingvariables and coupling constraints. To solve any of these problems, we would like to decompose the system,removingthecomplicatingvariablesorconstraints, toreduce theproblemtoonewithindependentsubsystems.Several of the techniques in large-scale system theory can be given this interpretation.Dynamic models, in the sense of multistage optimization, provide another major source of large-scaleproblems. In dynamic settings, decisions must be made at several points in time, e.g., weekly ormonthly.Usually decisions made in any time period have an impact upon other time periods, so that, even whenevery instantaneous problem is small, timing effects compound the decision process and produce large,frequently extremely large, optimization problems. The staircase and block triangular