A model in which the objective cell and all of the constraints (other than integer constraints) are linear functions of the decision variables is called a linear programming (LP) problem. Such problems are intrinsically easier to solve than nonlinear (NLP) problems. First, they are always convex, whereas a general nonlinear problem is often non-convex. Second, since all constraints are linear, the globally optimal solution always lies at an “extreme point” or “corner point” where two or more constraints intersect. (In some problems there may be multiple solutions with the same objective value, all lying on a line between two corner points.) 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 a globally optimal solution.
The Simplex LP Solving method uses the famous Simplex algorithm for linear programming, created by Dantzig in the 1940s. A dual Simplex method is used for integer programming subproblems.