Optimization Modeling with Spreadsheets, 3rd Edition

9 HEURISTIC SOLUTIONS WITH THE EVOLUTIONARY SOLVER

In previous chapters, we have encountered three powerful optimization procedures—the linear solver, the branch-and-bound procedure, and the nonlinear solver. For linear models, we use the linear solver. This algorithm is reliable: It always finds a global optimum when the model does not contain an unbounded objective function or conflicting constraints. For linear programming models with integer constraints, we also rely on the linear solver. The integer constraints are added in the problem formulation, informing the linear solver to use its branch-and-bound procedure in the search for an optimal solution. The branch-and-bound procedure relies on solving a series of linear programs, so if Solver does not run out of time, this is a reliable procedure, too. However, when the model does not satisfy the conditions of linearity, the linear solver is of no use.

For nonlinear programming problems, we use the nonlinear solver. This algorithm is not as reliable as the linear solver because it may stop its hill climbing at a local optimum. Moreover, it is unable to determine whether it has found a global optimum or stopped short of one. We can at least improve our chances of finding a global optimum by rerunning the nonlinear solver from a variety of different starting points, a process we can automate with the MultiStart option. However, when the problem is not composed of smooth functions, the nonlinear solver often fails to help. ...