Advanced Methods
| The Large-Scale SQP Solver can use Premium Solver Platform's "multistart" or "clustering" methods for global optimization.
It can be automatically run many times from judiciously chosen starting points, and the best solution found will be returned as the optimal solution. For some smooth nonlinear problems, multistart methods will converge in probability to the globally optimal solution. For other problems, they often yield very good solutions in an acceptable amount of time -- and of course, they are far easier to use than a manual exploratory process. And you don't have to change your model at all to take advantage of these new global optimization capabilities! |
|
Sequential Quadratic Programming Method
The Large-Scale SQP Solver's Sequential Quadratic Programming method typically requires fewer major iterations or trial solutions than a Generalized Reduced Gradient (GRG) method. In both methods, each major iteration requires gradients of the problem functions, computed via finite differencing - which requires many recalculations of the Excel worksheet (one for each variable in the problem).
Since the time for recalculation tends to dominate total solution time, an SQP method that requires fewer major iterations is typically faster than a GRG method, even though it "does more work" at each major iteration - and this speed advantage grows with the size of the problem. In V8.0, these solution methods are greatly enhanced -- the Large-Scale SQP Solver now handles problems with up to ten times as many degrees of freedom as in previous versions!
Sparse Matrix Storage
Sparse matrix storage methods take advantage of sparsity in large models, where subsets of the constraints typically depend on only a small subset of the variables.
For example, the Jacobian matrix (the matrix of partial derivatives of the objective and constraints with respect to the variables) for a problem with 2,000 variables and 2,000 constraints would take about 32 megabytes for matrix storage using dense storage methods, but if this problem has the sparsity typical of larger models, it would take as little as 1 to 1.5 megabytes using the sophisticated sparse matrix storage methods in the Large-Scale SQP Solver.
Improved Methods for Numerical Stability
Large nonlinear models require hundreds of thousands to millions of floating-point arithmetic calculations. Because of the finite precision inherent in computer arithmetic, small numerical errors occur in these calculations. Nonlinear models are particularly susceptible to the cumulative effect of these errors, which can lead to a numerically unstable or ill-conditioned matrix representation of the problem.
The Large-Scale SQP Solver uses several advanced methods to deal with numerical stability, including advanced matrix factorization methods, and "elastic programming" methods for dealing with infeasibility in the QP subproblems or the overall problem. Thanks to these methods, the Large-Scale SQP Solver can find very good or optimal solutions to problems that could not be solved at all with more primitive nonlinear optimizers.
Options for Mixed-Integer Nonlinear Problems
|
The Large-Scale SQP Solver uses Premium Solver Platform's Branch and Bound method to handle integer variables and "alldifferent" constraints. If your problem includes integer constraints, you can obtain a quick solution of the relaxation (temporarily ignoring the integer constraints) without having to delete these constraints and then re-enter them later. You can control the number of Branch and Bound subproblems and the number of integer feasible solutions found before the Solver stops. And you can speed up the solution of problems with integer constraints by supplying an integer cutoff value -- often known from a previous run. |
|
In Version 8.0, the Large-Scale SQP Solver offers several new methods for faster solution of linear programming problems with integer variables.
It uses preprocessing and probing techniques to preset values for some binary integer variables based on the settings of others. It automatically recognizes, and takes advantage of "cliques" (also called Special Ordered Sets), tightens bounds on constraints, and reorders the variables to be branched upon. It also uses cut generation techniques to automatically add new constraints, known as knapsack cuts or lifted cover inequalities, that reduce the size of the LP feasible region without eliminating any integer solutions. These methods can save significant time on LP/MIP problems, depending on the model.