ILOG CPLEX is designed to handle the numerical difficulties of linear programming automatically. In this context, numerical difficulties mean such phenomena as repeated occurrence of singularities, little or no progress toward realizing the objective function value, little or no progress in scaled infeasibility, repeated problem perturbations, repeated occurrences of the problem becoming infeasible. While ILOG CPLEX will usually achieve an optimal solution in spite of these difficulties, you can help it do so more efficiently. This section describes situations in which you can help.
Some problems will not be solvable even after you take the measures we suggest. Such problems are so poorly conditioned that their optimal solutions are beyond the numerical precision of your computer.
There is no absolute link between the form of data in a model and the numerical difficulty the problem poses. Nevertheless, certain choices in how you present the data to CPLEX can have an adverse effect.
Placing large upper bounds (say, in the neighborhood of 1e9 to 1e12) on individual variables can cause difficulty during Presolve. If you intend for such large bounds to mean "no bound is really in effect" it is better to simply not include such bounds in the first place.
Large coefficients anywhere in the model can likewise cause trouble at various points in the solution process. Even if the coefficients are of more modest size, a wide variation (say, six or more orders of magnitude) in coefficients found in the objective function or right hand side, or in any given row or column of the matrix, can cause difficulty either in Presolve when it makes substitutions, or in the optimizer routines, particularly the barrier optimizer, as convergence is approached.
A related source of difficulty is the form of rounding when fractions are represented as decimals; expressing 1/3 as .33333333 on a computer that in principle computes values to about 16 digits can introduce an apparent "exact" value that will be treated as given but may not represent what you intend. This difficulty is compounded if similar or related values are represented a little differently elsewhere in the model. The underlying principle behind all these cautions is that "information" contained down in the 8th or 10th decimal place of data needs to convey actual meaning or the optimizer may start to draw false conclusions.
Ill-conditioned matrices are sensitive to minute changes in problem data. That is, in such problems, small changes in data can lead to very large changes in the reported problem solution. ILOG CPLEX provides a basis condition number to measure the sensitivity of a linear system to the problem data. You might also think of the basis condition number as the number of places in precision that can be lost.
For example, if the basis condition number at optimality is 1e13, then a change in a single matrix coefficient in the thirteenth place may dramatically alter the solution. Furthermore, since many computers provide about 16 places of accuracy in double precision, only three accurate places are left in such a solution. Even if an answer is obtained, perhaps only the first three significant digits are reliable.
Because of this effective loss of precision for matrices with high basis condition numbers, ILOG CPLEX may be unable to select an optimal basis. In other words, a high basis condition number can make it impossible to find a solution.
Whenever ILOG CPLEX encounters a singularity, it removes a column from the current basis and proceeds with its work. ILOG CPLEX reports such actions to the log file (by default) and to the screen (if you are working in the Interactive Optimizer or if the message-to-screen indicator CPX_PARAM_SCRIND is set to 1 (one)). Once it finds an optimal solution under these conditions, ILOG CPLEX will then re-include the discarded column to be sure that no better solution is available. If no better objective value can be obtained, then the problem has been solved. Otherwise, ILOG CPLEX continues its work until it reaches optimality.
Occasionally, new singularities occur, or the same singularities recur. ILOG CPLEX observes a limit on the number of singularities it tolerates. By default, the limit is ten. After encountering ten singularities, ILOG CPLEX will save in memory the best factorable basis found so far and stop its solution process. You may want to save this basis to a file for later use.
To change the number of singularities that ILOG CPLEX tolerates:
To save the best factorable basis found so far in the Interactive Optimizer, use the writesav. When using the Component Libraries, use the method cplex.exportModel() or the routine CPXwriteprob().
If ILOG CPLEX encounters repeated singularities in your problem, you may want to try alternative scaling on the problem (rather than simply increasing ILOG CPLEX tolerance for singularities). Scaling explains how to try alternative scaling.
If alternate scaling does not help, another tactic to try is to increase the Markowitz tolerance. The Markowitz tolerance controls the kinds of pivots permitted. If you set it near its maximum value of 0.99999, it may make iterations slower but more numerically stable. Inability to Stay Feasible shows how to change the Markowitz tolerance.
If none of these ideas help, you may need to alter the model of your problem. Consider removing the offending variables manually from your model, and review the model to find other ways to represent the functions of those variables.
Highly degenerate linear programs tend to stall optimization progress in the primal and dual simplex optimizers. When stalling occurs with the primal simplex optimizer, ILOG CPLEX automatically perturbs the variable bounds; when stalling occurs with the dual simplex optimizer, ILOG CPLEX perturbs the objective function.
In either case, perturbation creates a different but closely related problem. Once ILOG CPLEX has solved the perturbed problem, it removes the perturbation by resetting problem data to their original values.
If ILOG CPLEX automatically perturbs your problem early in the solution process, you should consider starting the solution process yourself with a perturbation. (Starting in this way will save the time that would be wasted if you first allowed optimization to stall and then let ILOG CPLEX perturb the problem automatically.)
To start perturbation yourself:
If you observe that your problem has been perturbed more than once, then consider whether the simplex perturbation-limit parameter is too large. The perturbation-limit parameter determines the number of iterations ILOG CPLEX tries before it assumes the problem has stalled. At its default value, 0 (zero), ILOG CPLEX determines internally how many iterations to perform before declaring a stall. If you set this parameter to some other nonnegative integer, then ILOG CPLEX uses that limit to determine when a problem has stalled. If you reduce the perturbation-limit parameter, you may be able to reduce the number of times the problem is necessarily perturbed.
To reduce the simplex perturbation-limit parameter:
If a problem repeatedly becomes infeasible in Phase II (that is, after ILOG CPLEX has achieved a feasible solution), then numerical difficulties may be occurring. It may help to increase the Markowitz tolerance in such a case. By default, its value is 0.01, and suitable values range from 0.0001 to 0.99999.
To increase Markowitz tolerance:
Sometimes slow progress in Phase I (the period when ILOG CPLEX calculates the first feasible solution) is due to similar numerical difficulties, less obvious because feasibility is not gained and lost. In the progress reported in the log file, an increase in the printed sum of infeasibilities may be a symptom of this case. If so, it may be worth while to set a higher Markowitz tolerance, just as in the more obvious case of numerical difficulties in Phase II.
