Linear programming
It has proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.
In the late 1930s, Soviet mathematician Leonid Kantorovich and American economist Wassily Leontief independently delved into the practical applications of linear programming.
The turning point came during World War II when linear programming emerged as a vital tool.
It found extensive use in addressing complex wartime challenges, including transportation logistics, scheduling, and resource allocation.
Linear programming proved invaluable in optimizing these processes while considering critical constraints such as costs and resource availability.
Post-WWII, the method gained widespread recognition and became a cornerstone in various fields, from operations research to economics.
The overlooked contributions of Kantorovich and Leontief in the late 1930s eventually became foundational to the broader acceptance and utilization of linear programming in optimizing decision-making processes.
[6] About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs.
[4] In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method.
From 1946 to 1947 George B. Dantzig independently developed general linear programming formulation to use for planning problems in the US Air Force.
[8] In 1947, Dantzig also invented the simplex method that, for the first time efficiently, tackled the linear programming problem in most cases.
[8] Dantzig provided formal proof in an unpublished report "A Theorem on Linear Inequalities" on January 5, 1948.
However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the simplex algorithm.
Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations.
Likewise, linear programming was heavily used in the early formation of microeconomics, and it is currently utilized in company management, such as planning, production, transportation, and technology.
Although the modern management issues are ever-changing, most companies would like to maximize profits and minimize costs with limited resources.
Suppose that a farmer has a piece of farm land, say L hectares, to be planted with either wheat or barley or some combination of the two.
If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2.
Additionally, every feasible solution for a linear program gives a bound on the optimal value of the objective function of its dual.
Covering and packing LPs commonly arise as a linear programming relaxation of a combinatorial problem and are important in the study of approximation algorithms.
[15] In practice, the simplex algorithm is quite efficient and can be guaranteed to find the global optimum if certain precautions against cycling are taken.
[15][20] In contrast to the simplex algorithm, which finds an optimal solution by traversing the edges between vertices on a polyhedral set, interior-point methods move through the interior of the feasible region.
The convergence analysis has (real-number) predecessors, notably the iterative methods developed by Naum Z. Shor and the approximation algorithms by Arkadi Nemirovski and D. Yudin.
The algorithm was not a computational break-through, as the simplex method is more efficient for all but specially constructed families of linear programs.
The development of such algorithms would be of great theoretical interest, and perhaps allow practical gains in solving large LPs as well.
It would be of great practical and theoretical significance to know whether any such variants exist, particularly as an approach to deciding if LP can be solved in strongly polynomial time.
[29] Essentially, these methods attempt to find the shortest pivot path on the arrangement polytope under the linear programming problem.
There are however some important subclasses of IP and MIP problems that are efficiently solvable, most notably problems where the constraint matrix is totally unimodular and the right-hand sides of the constraints are integers or – more general – where the system has the total dual integrality (TDI) property.
Integral linear programs are of central importance in the polyhedral aspect of combinatorial optimization since they provide an alternate characterization of a problem.
Terminology is not consistent throughout the literature, so one should be careful to distinguish the following two concepts, One common way of proving that a polyhedron is integral is to show that it is totally unimodular.
