Theory of two-level planning

Last updated

The theory of two-level planning (alternatively, Kornai–Liptak decomposition) is a method that decomposes large problems of linear optimization 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 and the mathematician Tamás Lipták in 1965. It is an alternative to Dantzig–Wolfe decomposition.

In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different matrix decompositions; each finds use among a particular class of problems.

Linear programming

Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

János Kornai, until 1945 János Kornhauser, is a Hungarian economist noted for his analysis and criticism of the command economies of Eastern European communist states.



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:

DW Block Angular Matrix.jpg

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 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 sections dedicated to discussing this decomposition algorithm.

Related Research Articles

George Dantzig American mathematician

George Bernard Dantzig was an American mathematical scientist who made contributions to industrial engineering, operations research, computer science, economics, and statistics.

Numerical analysis study of algorithms that use numerical approximation for the problems of mathematical analysis

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. Numerical analysis naturally finds application in all fields of engineering and the physical sciences, but in the 21st century also the life sciences, social sciences, medicine, business and even the arts have adopted elements of scientific computations. As an aspect of mathematics and computer science that generates, analyzes, and implements algorithms, the growth in power and the revolution in computing has raised the use of realistic mathematical models in science and engineering, and complex numerical analysis is required to provide solutions to these more involved models of the world. Ordinary differential equations appear in celestial mechanics ; numerical linear algebra is important for data analysis; stochastic differential equations and Markov chains are essential in simulating living cells for medicine and biology.

Mathematical optimization field in applied mathematics; the selection of a best element (with regard to some criterion) from some set of available alternatives

In mathematics, computer science and operations research, mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO).

Column generation

Column generation or delayed column generation is an efficient algorithm for solving larger linear programs.

Water supply network system of engineered hydrologic and hydraulic components which provide water supply

A water supply system or water supply network is a system of engineered hydrologic and hydraulic components which provide water supply. A water supply system typically includes:

  1. A drainage basin.
  2. A raw water collection point where the water accumulates, such as a lake, a river, or groundwater from an underground aquifer. Raw water may be transferred using uncovered ground-level aqueducts, covered tunnels or underground water pipes to water purification facilities.
  3. Water purification facilities. Treated water is transferred using water pipes.
  4. Water storage facilities such as reservoirs, water tanks, or water towers. Smaller water systems may store the water in cisterns or pressure vessels. Tall buildings may also need to store water locally in pressure vessels in order for the water to reach the upper floors.
  5. Additional water pressurizing components such as pumping stations may need to be situated at the outlet of underground or above ground reservoirs or cisterns.
  6. A pipe network for distribution of water to the consumers and other usage points.
  7. Connections to the sewers are generally found downstream of the water consumers, but the sewer system is considered to be a separate system, rather than part of the water supply system.
Cutting-plane method

In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.

Numerical partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

Project Portfolio Management (PPM) is a senior leadership discipline that drives strategic execution and maximizes business value delivery through the selection, optimization, and oversight of project investments which align to business goals and strategies. PPM is the centralized management of the processes, methods, and technologies used by project managers and project management offices (PMOs) to analyze and collectively manage current or proposed projects based on numerous key characteristics. The objectives of PPM are to determine the optimal resource mix for delivery and to schedule activities to best achieve an organization’s operational and financial goals, while honouring constraints imposed by customers, strategic objectives, or external real-world factors. The International standard defines the framework of the Project Portfolio Management

Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes and purchase materials.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

In project management, resource levelling is defined by A Guide to the Project Management Body of Knowledge as "A technique in which start and finish dates are adjusted based on resource limitation with the goal of balancing demand for resources with the available supply." Resource leveling problem could be formulated as an optimization problem. The problem could be solved by different optimization algorithms such as exact algorithms or meta-heuristic methods.

The genetic algorithm is an operational research method that may be used to solve scheduling problems in production planning.

In numerical analysis, the balancing domain decomposition method (BDD) is an iterative method to find the solution of a symmetric positive definite system of linear algebraic equations arising from the finite element method. In each iteration, it combines the solution of local problems on non-overlapping subdomains with a coarse problem created from the subdomain nullspaces. BDD requires only solution of subdomain problems rather than access to the matrices of those problems, so it is applicable to situations where only the solution operators are available, such as in oil reservoir simulation by mixed finite elements. In its original formulation, BDD performs well only for 2nd order problems, such elasticity in 2D and 3D. For 4th order problems, such as plate bending, it needs to be modified by adding to the coarse problem special basis functions that enforce continuity of the solution at subdomain corners, which makes it however more expensive. The BDDC method uses the same corner basis functions as, but in an additive rather than multiplicative fashion. The dual counterpart to BDD is FETI, which enforces the equality of the solution between the subdomain by Lagrange multipliers. The base versions of BDD and FETI are not mathematically equivalent, though a special version of FETI designed to be robust for hard problems has the same eigenvalues and thus essentially the same performance as BDD.

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 such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders.

In applied mathematics, branch and price is a method of combinatorial optimization for solving integer linear programming (ILP) and mixed integer linear programming (MILP) problems with many variables. The method is a hybrid of branch and bound and column generation methods.

Philip Starr "Phil" Wolfe was an American mathematician and one of the founders of convex optimization theory and mathematical programming.