Optimal Planning with Decomposition

Origin. CEMI (Central Economic-Mathematical Institute) under Fedorenko; Dantzig-Wolfe decomposition applied to planning; Soviet work on iterative planning procedures.

Mechanism. The full planning problem is too large to solve directly. Decompose it into subproblems (one per enterprise or sector) plus a master problem (the coordinator). The master problem sets prices or resource allocations; subproblems optimize locally against those signals. Information flows between levels: subproblems report demands and proposals, the master adjusts prices. Iteration converges to the global optimum under convexity.

Procedure. Formulate the full problem. Identify separable subproblems linked only by common constraints (shared resources, total targets). Initialize prices. Each subproblem optimizes given prices and reports its solution. The master checks global constraints; if violated, adjust prices (raise prices for over-demanded resources, lower for under-demanded). Repeat until convergence: prices stabilize and subproblem solutions are globally feasible.

Applies to. Large-scale optimization, multi-divisional planning, any problem too large for direct solution but decomposable into subproblems.

Limitations. Convergence requires convexity; non-convex subproblems can cause cycling or divergence. The number of iterations can be large, and each requires communication between levels. Strategic behavior by subproblems (misreporting demands) breaks the mechanism. In Soviet practice, enterprises manipulated the planning process, and the iteration never converged to anything resembling an optimum.