The theory of two-level planning (alternatively, Kornai–Liptak decomposition) is a method that
decomposes large problems of
linear optimization
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
into sub-problems. This decomposition simplifies the solution of the overall problem. The method also models a method of coordinating economic decisions so that decentralized firms behave so as to produce a global optimum. It was introduced by the Hungarian economist
János Kornai
János Kornai (21 January 1928 – 18 October 2021) was a Hungarian economist noted for his analysis and criticism of the command economies of Eastern European communist states. He also covered macroeconomic aspects in countries undergoing pos ...
and the mathematician Tamás Lipták in 1965. It is an alternative to
Dantzig–Wolfe decomposition
Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have se ...
.
Description
The LP problem must have a special structure, known as a block angular structure. This is the same structure required for the Dantzig Wolfe decomposition:
There are some constraints on overall resources (D) for which a central planning agency is assumed to be responsible, and n blocks of coefficients (F1 through Fn) that are the concern of individual firms.
The central agency starts the process by providing each firm with tentative resource allocations which satisfy the overall constraints D. Each firm optimizes its local decision variables assuming the global resource allocations are as indicated. The solution of the firm LP's yield Lagrange multipliers (prices) for the global resources which the firms transmit back to the planning agency.
In the next iteration, the central agency uses the information received from firms to come up with a revised resource allocation; for example if firm i reports a high shadow price for resource j, the agency will grant more of this resource to this firm and less to other firms. The revised tentative allocations are sent back to the individual firms and the process continues.
It has been shown that this process will converge (though not necessarily in a finite number of steps) towards the global solution for the overall problem. (In contrast the Dantzig Wolfe method converges in a finite number of steps).
The DW and KL methods are dual: in DW the central market establishes prices (based on firm demands for resources) and sends these to the firms who then modify the quantities they demand, while in KL the central agency sends out quantity information to firms and receives bids (i.e. firm specific pricing information) from firms.
See also
*
Dantzig–Wolfe decomposition
Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have se ...
*
Benders' decomposition
Benders decomposition (or Benders' decomposition) is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications ...
*
Column generation
Column generation or delayed column generation is an efficient algorithm for solving large linear programs.
The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by sol ...
References
* J. Kornai, T. Liptak: ''Two-level Planning'', Econometrica, 1965, Vol. 33, pp. 141–169
{{instecon
Linear programming
Decomposition methods