Linear Optimization

The methods and processes used to obtain an optimal solution for a linear programming problem. The linear programming problem is generally related to the maximization of profit for a business process under real constraints for the inputs of that process. There is a course related to this topic held by the Math Faculty at the UniversityOfWaterloo for BusinessAdministration and CombinatoricsAndOptimization majors. Or, to those interested (or insane) enough to take it as one of their math electives!

In relation to programming, the efficient optimization of linear programming problems (LPs) is still in question today. Although the RevisedSimplexMethod? is still the most efficient for solving an LP, there is room for improvement. Many pieces of software exist for businesses that implement this method in various ways. In essence, the method involves a series of matrix calculations.

The methods involved in solving LinearProgram?s coincide with the HaltingProblem (it is possible to get a problem where, when you attempt to solve it, you contract degeneracy and the solution cycles infinitely unless BlandsRule? is used), and with efficiency problems. There is also an NpIncomplete problem involved when the LinearProgram? is restricted to an integer-only solution. An example of this case would be businesses that manufacture large pieces such as airplanes. The efficient solution of IntegerLinearProgram?s (ILPs) turns out to be NP-Hard and a truly efficient solution still does not exist.

-- JoscelynKleingeld

Is LP supposed to stand for LinearProgram? or LinearProblem??

LP stands for LinearProgram?. It's a Linear Programming Problem, in particular. But it first and foremost stands for Linear Program. In business, the problems are modelled into a linear program to be run on a computer with linear optimization software. -- JoscelynKleingeld

See OptimizationPattern


EditText of this page (last edited March 28, 2004) or FindPage with title or text search