LINGO includes a set of built-in solvers to tackle a wide variety of problems. Unlike many modeling packages, all of the LINGO solvers are directly linked to the modeling environment. This seamless integration allows LINGO to pass the problem to the appropriate solver directly in memory rather than through more sluggish intermediate files. This direct link also minimizes compatibility problems between the modeling language component and the solver components.
Linear Solvers
LINGO 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. The solver dynamically chooses the best pricing option based upon problem characteristics.
Barrier Solver
The optional Barrier solver provides an alternative means of solving linear models. The Barrier option utilizes 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 license option is required to utilize the Barrier solver.
Integer Solver
For models with general and binary integer restrictions, LINGO includes an integer solver that works in conjunction with the linear, nonlinear, and quadratic solvers. For linear models, the integer solver includes preprocessing and dozens of constraint "cut" generation routines that can greatly improve solution times on large classes of integer models.
Nonlinear Solvers
LINGO 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 LINGO's optional nonlinear solver is based upon a Generalized Reduced Gradient (GRG) algorithm. However, to help get to a good feasible solution quickly, LINGO also incorporates Successive Linear Programming (SLP). The nonlinear solver takes advantage of sparsity for improved speed and more efficient memory usage. The Nonlinear license option is required to solve nonlinear models.
Global Solver
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 license options are required to utilize the global optimization capabilities.
Multistart Solver
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 initialize a series of local optimizations. 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 utilize the multistart capabilties.
Quadratic Solver
In addition to solving linear and mixed integer models, with the Barrier option LINGO 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, LINGO can solve these models much more quickly than using the general nonlinear solver. LINGO can even handle quadratic models with binary and general integer restrictions. These quadratic capabilities make LINGO suitable for applications such as portfolio optimization 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 license option.
Conic Solver
The Conic solver efficiently solves 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. The Barrier and Conic options are required to utilize the Conic solver.
Stochastic Programming Solver
Incorporate risk into multi-stage optimization models, maximize expected profit, and summarize results in histograms showing the distribution of possible profit, etc. This new option allows modeling and optimization for models with uncertain elements via multistage stochastic linear, nonlinear and integer stochastic programming (SP). Benders decomposition is used for solving large linear SP models. Deterministic equivalent method is used for solving nonlinear and integer SP models. Support is available for over 20 distribution types (discrete or continuous). The Stochastic Programming solver is included in the Stochastic Programming option.
Preprocessing
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 analyzing the original formulation and mathematically condensing it into a smaller problem. The Integer solver includes extensive preprocessing and cut generation routines.
LINGO is designed, so the process of solving the model requires as little input from the user as possible. When the Solve command is initiated, LINGO analyzes the problem and, when possible, reduces the problem and even substitutes out variables. Based upon the models structure, LINGO automatically selects the appropriate solver and intelligently adjusts internal parameters.
Linearization
LINGO's Linearization capabilities can dramatically improve performance on models with common nonsmooth functions. The feature can automatically convert many nonsmooth functions and operators (e.g., @IF, @MAX and @ABS) to a series of linear, mathematically equivalent expressions. Similarly, the product of a continuous and binary variable can also be linearized. Many nonsmooth models may be entirely linearized. This allows the linear solver to quickly find a global solution to what would have otherwise been an intractable problem.
