LINDO for MPL

LINDO has been steadily adding onto its software various features allowing greater functionality year on year. Today the LINDO solver suite has a diverse number of optimizers that can be used to solve more diverse types of mathematical programming problems than any other solver on the market. LINDO for MPL gives users access to this multi faceted solver from within the user-friendly Windows environment of MPL

Algorithmic Features

The LINDO solver has various intricate routines that can aid in the solution process, these include scaling and model reduction, scaling can improve speed and robustness on numerically unstable problems. Model reduction 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. LINDO is the most complete solver on the market today, it has the functionality that allows it to solve more problem types in mathematical programming that any other, ranging from linear programming to nonconvex nonlinear programming problems.

LINDO Simplex Optimizer

LINDO Simplex Optimizers 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.

LINDO Barrier Optimizer

LINDO 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.

LINDO Integer Optimizer

LINDO Integer Optimizer uses sophisticated branch and bound algorithmic techniques to solve problems that contain general and/or binary integer restrictions. It is equipped with advanced preprocessing, heuristic and cut generation tools.

LINDO Nonlinear Optimizer

LINDO Nonlinear Optimizers have a vast array of algorithmic features that allows one to solve many classes of models in Nonlinear Programming:

LINDO has optimizers that can do both local and global searches. The local search solver is based upon a Generalized Reduced Gradient (GRG) algorithm. However, to help get to a good feasible solution quickly, it also incorporates Successive Linear Programming (SLP). 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. If there are time constraints in solving one can choose to utilize LINDO's multistart feature, this intelligently generates a set of candidate starting points in the solution space. Then local search techniques intelligently select a subset of these to initialize a series of local optimizations.

Performance Tuning

For LPs

In general if the model is sparse with fewer constraints than columns, LINDO's primal simplex method works best, whereas the primal simplex optimizer tends to do better on sparse models with fewer variables than constraints. The primal simplex method also performs better if the model is degenerate. The barrier algorithm works best on structured models or very large models. Degeneracy is not an issue for the barrier method, thus highly degenerate problems one should use the barrier algorithm to solve the LP.

For MIPs

MIP problems can be extremely difficult to solve, though there are no steadfast rules on enhancing MIP performance, certain things may be advantageous in improving the performance on some models and be a hinderous on other problems. Below are some of the considerations one should look into when try to solve difficult MIP problems:

For NLPs

The area of nonlinear programming is diverse, and there is no anyone method that can handle all types of NLPs unlike in linear programming. If the NLPs are large or are highly nonlinear in nature, utilizing the global optimizer will generally give bad performance. Models larger than 100 variables can be extremely difficult to solve to proven global optimality. Large models should use the local solver, MPL by default will use LINDO's local optimizer when solving NLP one has to specify the boolean option "UseGlobalOptimizer" to activate the global solver. One can employ a multi-start methodology using the local solver to find better local optima, this naturally will increase the total solve time but should result in better solutions. Typically one should set a multi-start value of 4 or 5 (setting: "NLPMaxLocalSearch").

LINDO Log Output

MPL shows the progress of LINDO during a solve run in the message window which also can be relayed to a log file. One can set various log file parameters in MPL, allowing one to display log information for NLPs and MIPs. The log initially displays information about the model, for LPs and MIPS it will also show the a summary of the scaling done by LINDO, the message log has the following appearance:


STATUS: Optimizing 'VegetableOilBlending' with LINDO 5.0.1.100 solver
tpre     ncons    nvars   nnzA     time
 ini       5       10      27      0.00
Scaling LP data (c,A,b,l,u)...
Abs. Ranges (Sc):             Max.            Min.             Cond.
Matrix Coef. (A):           2.00000         0.37500           5.33333
Obj. Vector  (c):           1.01563         0.42969           2.36364
RHS Vector (b):           250.00000       200.00000           1.25000
Lower Bounds (l):       1.0000e+030     1.0000e+030           1.00000
Upper Bounds (u):       1.0000e+020     5.0000e+019           2.00000
    Iter Deg(%)          Dual obj          Prim inf          Dual inf     Ninf    Time     
      0   0.00  1.5000000000e+022  1.375000000e+020         0.0000000       2     0.09  (D)
      6  14.29     305000.0000000      9800.0000000         0.0000000       1     0.11  (D)
*     8  11.11      17592.5925926         0.0000000         0.0000000       0     0.11  (D)

For LPs LINDO will display the iteration number, the dual/primal objective value, iteration infeasibility and the time of the iteration.

For a local NLP log the output will include the objective, primal and dual infeasibities for the iterations. One can set the amount of log information displayed by setting the "NLPTrace" option.


STATUS: Optimizing 'Lindo_NLP1' with LINDO 5.0.1.100 NLP solver
tpre   ncons    nvars    nnzA   time
 ini     2        2        4    0.03
  Iter  Phase   nInf         Objective         Pinf(sum)       Dinf(rgmax)
     0      0      0   0.00000000e+000   0.00000000e+000   0.00000000e+000
     1      0      0   0.00000000e+000   0.00000000e+000   0.00000000e+000
     2      0      0   0.00000000e+000   0.00000000e+000   0.00000000e+000
     3      3      0  -1.59276283e-002   0.00000000e+000   3.96202369e+000
     4      3      0  -4.82833607e-002   0.00000000e+000   5.20508260e-001
     5      4      0  -6.39748819e-002   0.00000000e+000   4.43421062e-001
     6      4      0  -6.49205336e-002   0.00000000e+000   1.63642121e-001
     7      4      0  -6.49358031e-002   0.00000000e+000   1.20919723e-002
     8      4      0  -6.49358681e-002   0.00000000e+000   9.03285900e-004
     9      4      0  -6.49358683e-002   0.00000000e+000   5.05179198e-005
    10      4      0  -6.49358683e-002   0.00000000e+000   1.12613835e-006
    11      4      0  -6.49358683e-002   0.00000000e+000   8.83899376e-009
Solver Statistics
  Solver name:      Lindo
  Objective value:  -0.0649358682555269
  Iterations:       0
  Solution time:    3.57 sec
  Result code:      5

The log output for LINDO's global solver has various information regarding convexity and iteratively displays the best solution found (UPPER BOUND) and the best bound (LOWER BOUND) thus far, and has the following appearance:


Starting global optimization ...
Number of nonlinear functions/operators:  2
 EP_MULTIPLY  EP_SIN 
Starting GOP presolve ...
Computing reduced bound...
Searching for an initial solution...
Initial objective value: 0.000000e+000
Starting reformulation ...
Model                       Input   Operation    Atomic      Convex
Number of variables  :       1            2        5            5
Number of constraints:       1            2        5           14
integer variables    :       0            0        0            0
nonlinear variables  :       1            1        3            0      
Starting global search ...
 Initial upper bound on objective: -7.834761e+000 
 Initial lower bound on objective: -9.700742e+000 
  #ITERs    TIME(s)    LOWER BOUND     UPPER BOUND    BOXES
        1         0  -9.700742e+000   -7.834761e+000        1 (*N) 
        2         0  -9.505975e+000   -9.505322e+000        1 (*N) 
        3         0  -9.505975e+000   -9.505322e+000        1 (*I) 
Terminating global search ...
Global Optimum found

LINDO Parameter Options

For full description of all the LINDO Parameters that are supported in MPL please go to the LINDO Option Parameters page.


Back To Top | Maximal Home Page | List of Solvers | Previous Page | Next Page