Overview
Linear programming is an optimization problem where all involved functions are linear in x; in particular, all the constraints are linear inequalities and equalities. Linear programming is the subject of studying and solving linear programs. Linear programming is a general technique for solving a huge family of optimization problems. It's incredibly useful for scheduling, resource allocation, economic planning, financial portfolio management, and a ton of other similar things.
|
Linear programming is a very important class of problems, both algorithmically and combinatorial. Linear programming has many applications. From an algorithmic point-of-view, the simplex was proposed in the forties (soon after the war, and was motivated by military applications) and, although it has performed very well in practice, is known to run in exponential time in the worst-case. During the last two decades, the optimization and operations research community has witnessed an explosive development in the area of optimization theory due to the introduction and development of Interior-Point Methods (IPMs). Since optimization techniques form the basis for many methods in Operations Research (OR) and related fields, these areas have been profoundly impacted by the advancements in IPMs. This development has rapidly led to the design of new and efficient optimization codes particularly in the field of Linear Programming (LP) that have, for the first time in fifty years, offered a valid alternative to the Dantzig’s Simplex Method (SM).