LINDO Systems has begun shipping a new release of LINDO API that includes new features to allow users to incorporate uncertainty into their optimization models. LINDO API 10.0 also includes enhancements to the linear, integer and global solvers.
LINDO API 10.0 Enhancements
Faster Solutions on Linear Models with Improved Simplex Solver
Enhancements to the Simplex solvers boost performance on large linear models. Large models solve an average of 35% faster using primal simplex and 20% faster for dual simplex.
Additional LP solver enhancements include a new extension to support multiple objective criteria.
Improved Integer Solver with new features
A new optimization mode has been introduced to ensure reproducibility of runs.
Investigate alternative optima more quickly. Enhancements to the K-Best algorithm allow finding K best solutions in little more time than finding one solution.
Find faster solutions to models with knapsack constraints and block structures using new heuristic algorithms.
New preprocessing level tightens variable bounds for better performance on classes of nonlinear models.
Enhanced Stochastic Solver
Large linear multistage SP instances solve 60% faster with improved cut management for Nested Benders Decomposition Method.
Better handling of multistage SP models which do not have full-recourse.
Extensions to the parser allow the use of arbitrarily complex functions of stochastic parameters.
Improved Global Solver
Performance of Global solver has been dramatically improved on classes of quadratic problems. In particular, non-convex quadratic problems rejected by other solvers, or otherwise solvable only slowly to a local optimum by traditional NLP solvers. Can solve some previously intractable problems to global optimality, especially financial portfolio models with minimum buy quantities, and/or limit on number of instruments at nonzero level.
Incorporates a new bound tightening process to the linearization procedure and improves solvability of linearized model. Dramatically faster, more robust performance on many models with functions like MAX( ), MIN( ), ABS( ), x*z where z = 0 or 1, etc.
Extended collection of user callable matrix operations for working with covariance matrices such as in financial portfolio design. Routines include general eigenvalue decomposition, cholesky factorization for generating correlated random variables, Semi-Definiteness (SDP) constraints, plus linear regression, e.g. for doing demand forecasting for production planning models.
LINDO API includes a set of built-in solvers to tackle a wide variety of problems. It offers increased control of the algorithms and solver parameters. This allows the user to customise the solution strategy to individual applications to achieve optimal control and speed.
The LINDO API is available with three state of the art solvers for linear models.
Primal and Dual Simplex Solvers
The base version includes the Primal and Dual Simplex solvers, which incorporate numerous enhancements for maximum speed and robustness. Pricing options, for instance, include partial pricing and Devex. You have the option to choose the best pricing strategy based upon problem characteristics.
The optional Barrier solver provides an alternative means of solving linear models. The Barrier option utilises a barrier or interior point method to solve linear models. Unlike the Simplex solvers that move along the exterior of the feasible region, the Barrier solver moves through the interior space to find the optimum. Depending upon the size and structure of a particular model, the Barrier solver may be significantly faster than the Simplex solvers and can provide exceptional speed on large linear models, particularly on sparse models with more than 5,000 constraints or highly degenerate models. The Barrier licence option is required to utilise the Barrier solver.
For models with general and binary integer restrictions, LINDO API includes an integer solver that works in conjunction with the linear, nonlinear and quadratic solver. For linear models, you have the ability to tailor the solution strategy and apply different classes of cuts to ensure maximum speed on particular problem structures.
LINDO API is the first full-featured callable solver to offer general nonlinear capabilities. LINDO API includes a number of ways to find locally or globally optimal solutions to nonlinear models.
General Nonlinear Solver
For nonlinear programming models, the primary underlying technique used by LINDO API's optional nonlinear solver is based upon a Generalised Reduced Gradient (GRG) algorithm. However, to help get to a good feasible solution quickly, LINDO API also incorporates Successive Linear Programming (SLP). The nonlinear solver takes advantage of sparsity for improved speed and more efficient memory usage. The Nonlinear licence option is required to solve nonlinear models.
Local search solvers are generally designed to search only until they have identified a local optimum. If the model is non-convex, other local optima may exist that yield significantly better solutions. Rather than stopping after the first local optimum is found, the Global solver will search until the global optimum is confirmed. The Global solver converts the original non-convex, nonlinear problem into several convex, linear subproblems. Then, it uses the branch-and-bound technique to exhaustively search over these subproblems for the global solution. The Nonlinear and Global licence options are required to utilise the global optimisation capabilities.
When limited time makes searching for the global optimum prohibitive, the Multistart solver can be a powerful tool for finding good solutions more quickly. This intelligently generates a set of candidate starting points in the solution space. Then, the general nonlinear solver intelligently selects a subset of these to initialise a series of local optimisations. For non-convex nonlinear models, the quality of the solution returned by the multistart solver will be superior to that of the general nonlinear solver. The Nonlinear and Global license options are required to utilise the multistart capabilities.
In addition to solving linear and mixed integer models, with the Barrier option LINDO API can automatically detect and solve models in which the objective function and/or some constraints include quadratic terms. By taking advantage of the quadratic structure, LINDO API can solve these models much more quickly than using the general nonlinear solver. LINDO API can even handle quadratic models with binary and general integer restrictions. These quadratic capabilities make LINDO API suitable for applications such as portfolio optimisation problems, constrained regression problems, and certain classes of difficult logistics problems (e.g., layout problems, fixed-charge-network problems with quadratic objectives). The Quadratic solver is included in the Barrier licence option.
The Barrier option includes a Conic solver to efficiently solve Second Order Cone Problems (SOCP). By expressing certain nonlinear models as SOCPs, the Conic solver can be used to solve the model substantially faster than the general nonlinear solver.
Preprocessing and User Control
Preprocessing routines are included in all solvers. The Linear and Nonlinear solvers include scaling and model reduction techniques. Scaling procedures can improve speed and robustness on numerically difficult models. Model reduction techniques can often make models solve faster by analysing the original formulation and mathematically condensing it into a smaller problem. The Integer solver includes extensive preprocessing and cut generation routines.
LINDO API is designed, so the user has as much control over the input to the solvers as possible. When the Solve routine is initiated, LINDO API analyses the problem and considers internal parameters set by the user to achieve optimal performance for your particular problem.
LINDO API's linearisation capabilities can dramatically improve performance on models with common nonsmooth functions. The feature can automatically convert many nonsmooth functions and operators (e.g., max and absolute value) to a series of linear, mathematically equivalent expressions. Many nonsmooth models may be entirely linearised. This allows the linear solver to quickly find a global solution to what would have otherwise been and intractable problem.