• Simplex Method Lp
• Simplex Lp1020

Solver’s basic purpose is to find a solution – that is, values for the decision variables in your model – that satisfies all of the constraints and maximizes or minimizes the objective cell value (if there is one). The kind of solution you can expect, and how much computing time may be needed to find a solution, depends primarily on three characteristics of your model:

1. Your model size (number of decision variables and constraints, total number of formulas)
2. The mathematical relationships (e.g. linear or nonlinear) between the objective and constraints and the decision variables
3. The use of integer constraints on variables in your model

Other issues, such as poor scaling, can also affect solution time and quality, but the above characteristics affect the intrinsic solvability of your model. Although faster algorithms and faster processors can help, some non-convex or non-smooth models could take years or decades to solve to optimality on the fastest imaginable computers.

Reference 1, page 82. Simplex Overview. The simplex method is an algorithm for solving linear programming problems. It is based on the fact that an optimal solution to a linear programming problem always lies at an extreme point. The Simplex LP Solving method is designed for these problems. If your objective and constraints are smooth nonlinear functions of the decision variables, solution times will be longer.

Your model’s total size and the use of integer constraints are both relatively easy to assess when you examine your model. The mathematical relationships, which are determined by the formulas in your model, may be harder to assess, but they often have a decisive impact on solution time and quality – as further explained starting with this topic.

To summarize:

• If your objective and constraints are linear functions of the decision variables, you can be confident of finding a globally optimal solution reasonably quickly, given the size of your model. This is a linear programming problem; it is also a convex optimization problem (since all linear functions are convex). The Simplex LP Solving method is designed for these problems.
• If your objective and constraints are smooth nonlinear functions of the decision variables, solution times will be longer. If the problem is convex, you can be confident of finding a globally optimal solution, but if it is non-convex, you can only expect a locally optimal solution – and even this may be hard to find. The GRG Nonlinear Solving method is designed for these problems.
• If your objective and constraints are non-smooth and non-convex functions of the decision variables (for example if you use IF, CHOOSE and LOOKUP functions whose arguments depend on decision variables), the best you can hope for is a “good” solution (better than the initial values of the variables), not a locally or globally optimal solution. The Evolutionary Solving method is designed for these problems.
• You can use integer, binary, and alldifferent constraints on variables with all three Solving methods. However, these constraints make the problem non-convex and much harder to solve.

Simplex Method Lp

Simplex Lp1020

With the Simplex LP Solving method, you can find a globally optimal solution given enough time – but you may have to settle for a solution that’s “close to optimal” found in a more reasonable amount of time. With the GRG Nonlinear and Evolutionary Solving methods, you should expect a “good,” but not provably optimal solution.