Location Analysis
- PDF / 1,148,892 Bytes
- 64 Pages / 547.087 x 737.008 pts Page_size
- 26 Downloads / 203 Views
Lack of Memory
Lagrangian Function
▶ Exponential Arrivals ▶ Markov Processes ▶ Markov Property ▶ Memoryless Property ▶ Poisson Process ▶ Queueing Theory
The general mathematical-programming problem of minimizing f(x) subject to a set of constraints {gi(x) bi} has associated with it a Lagrangian P function defined as L(x, l) ¼ f(x) + ili[gi(x)bi], where the components li of the nonnegative vector l are called Lagrange multipliers. For a primal linear-programming problem, the Lagrange multipliers can be interpreted as the variables of the corresponding dual problem.
Lagrange Multipliers See The multiplicative, linear-combination constants that appear in the Lagrangian of a mathematical programming problem. They are generally dual variables if the dual exists, so-called shadow prices in linear programming, giving the rate of change of the optimal value with constraint changes, under appropriate conditions.
▶ Lagrangian Relaxation ▶ Nonlinear Programming
Lagrangian Relaxation Monique Guignard University of Pennsylvania, Philadelphia, PA, USA
See Introduction ▶ Lagrangian Function ▶ Nonlinear Programming
Lagrangian Decomposition ▶ Integer and Combinatorial Optimization ▶ Lagrangian Relaxation
Many practical optimization problems include decision variables that are integer or 0-1. These problems, called mixed-integer programming problems or MIP for short, are in general difficult to solve, and there have been traditionally two classes of approaches to solve them: branch-and-bound or enumeration, and heuristic methods, either ad hoc or generic. Broadly speaking, branch-and-bound methods construct a tree, usually
S.I. Gass, M.C. Fu (eds.), Encyclopedia of Operations Research and Management Science, DOI 10.1007/978-1-4419-1153-7, # Springer Science+Business Media New York 2013
L
846
binary, that allows the systematic exploration of all integer or 0-1 combinations of the discrete variables. Logical considerations and/or bounds on the optimal value computed as one moves down the tree may allow the pruning of a branch and backtracking to its root because one discovers that it would lead to infeasibilities or inferior solutions. Typically, bounds are obtained by solving a simpler, relaxed, optimization problem, most of the time the continuous relaxation of the MIP problem in which integer or 0-1 variables are allowed to take on fractional values. Heuristics, on the other hand, search for better and better feasible integer solutions, and do not usually compute bounds on the optimum, and therefore, even though they are getting more and more sophisticated and excel at finding optimal or near optimal solutions, cannot guarantee the quality of the solutions found. Lagrangian relaxation stands somehow at the crossroads of both approaches. More powerful in terms of bound quality than the continuous relaxation, it also produces partially infeasible, but integer, solutions. These can usually serve as excellent starting points for specialized heuristics, referred to as Lagrangian heuristics. Contrary to the general heuri
Data Loading...
