linear programming
In plain wordsA mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input.
The problem of choosing values for real-valued decision variables that minimize or maximize a linear function of them while satisfying a set of linear equations and inequalities. Because the feasible set is a convex polyhedron, any local optimum is global, and when an optimum exists one occurs at a vertex. George Dantzig's simplex method walks from vertex to adjacent vertex and is fast in practice though exponential in the worst case; Leonid Khachiyan's ellipsoid method (1979) proved the problem solvable in polynomial time, and Narendra Karmarkar's interior-point method (1984) made polynomial-time algorithms practical. Every linear program has a dual problem, and when either has an optimal solution their optimal values are equal (strong duality), which yields shadow prices for resources and certificates of optimality. Linear programming is a special case of convex optimizationconvex optimization, n.: Finding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy.; it underlies the relaxations used to solve integer programsinteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find., exact solution of Markov decision processesMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice., discrete optimal transportWasserstein distance, n.: A way of comparing two spreads of probability by imagining one as heaps of sand that must be shoveled into the shape of the other: the less shoveling, weighted by distance, the more alike they are., relaxations for MAP inference in graphical modelsprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together. and the verification of neural networksneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain..
We wrote the GPU allocation as a linear program and let the solver find the cheapest schedule.
Origin
Leonid Kantorovich formulated linear models for planning production in 1939, and Tjalling Koopmans studied transportation problems; they shared the 1975 Nobel Memorial Prize in Economic Sciences. George Dantzig stated the general problem and devised the simplex method in 1947 while working on US Air Force planning. Koopmans suggested the name 'linear programming' in 1948, 'programming' then meaning the scheduling of activities.
Usage note
'Programming' means planning, not writing code. Requiring some variables to take whole-number values turns the problem into integer programminginteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find., which is NP-hard, whereas linear programs can be solved in polynomial time.
Related
- convex optimizationconvex optimization, n.: Finding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy.
- optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible.
- Lagrange multiplierLagrange multiplier, n.: A mathematical device for finding the best answer when strict rules must be obeyed: each rule becomes an extra price that grows when the rule is broken.
- Wasserstein distanceWasserstein distance, n.: A way of comparing two spreads of probability by imagining one as heaps of sand that must be shoveled into the shape of the other: the less shoveling, weighted by distance, the more alike they are.
- branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand.
- Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.
- integer programminginteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find.
Sources
- Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
- Kantorovich, L. V. (1960). Mathematical Methods of Organizing and Planning Production. Management Science 6(4), 366–422. Translation of the 1939 Russian original.
Mentioned in
integer programminginteger programming, n.: Finding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find.