| |
Powerful LINGO Solvers
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 Solver
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 Barrier option for LINGO 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.
The Barrier and Global options are required to utilize the Conic option
capabilities.
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.
© Copyright 2011 Lindo Systems Inc.
|
|
