Linear Programming

Linear programming problems are intrinsically easier to solve than nonlinear problems. In an NLP there may be more than one feasible region and the optimal solution might be found at any point within any such region. In contrast, an LP has at most one feasible region with "flat faces" (i.e. no curves) on its outer surface, and the optimal solution will always be found at a "corner point" on the surface where the constraints intersect. (In some problems there may be multiple optimal solutions, all of them lying along a line between corner points, with the same objective function value.) This means that an LP Solver needs to consider many fewer points than an NLP Solver, and it is always possible to determine (subject to the limitations of finite precision computer arithmetic) that an LP problem (i) has no feasible solution, (ii) has an unbounded objective, or (iii) has an optimal solution (either a single point or multiple equivalent points along a line).

Related Topics:

Problem Size and Numerical Stability

The Simplex Method