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
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 OptimizerLINDO 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 OptimizerLINDO 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 OptimizerLINDO 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 OptimizerLINDO 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.
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.
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:
Priority orders: Assign higher priority to the integer variables that should be decided earlier, these tend to represent decisions that are strategic or activate processes. The order, the variables are defined in MPL indicates the MIP priority, earlier the definition the higher the priority.
Variable selection: Specifying the rule that selects the variable to branch on can have considerable benefits. In LINDO one can set this parameter by suing the option "MIPBranchRule", the default is zero but often using basis rounding with pseudo costs (setting 1) or pseudo reduced costs (setting 3) can make help in difficult models.
Heuristic setting: LINDO has a number of heuristics that can be used to find initial integer feasible solutions, finding good solutions fast greatly benefits the subsequent brand and bound search process eliminating may "bad" branches. For difficult problems one should try to set the heuristic level parameter ("MIPHeuristicLevel") to 3,4 or 5. Higher value settings will cause more time to be spent in the heuristic, which may not be worthwhile.
Cuts: Addition of cuts helps eliminate non-integer feasible regions from the LP relaxed convex hull. This provides improved bounds during the branch and bound process. The option "MIPCutLevel" which is a bit setting has a default value of 22526 which means 12 types of cuts are set out of 14. To include full cut generation one can set this value to 32766. The more cuts added, the larger the inherent matrix becomes which can increase the processing time at the nodes. However usually on difficult models an aggressive cut strategy is the best mode of practice.
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").
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
For full description of all the LINDO Parameters that are supported in MPL please go to the LINDO Option Parameters page.