Documents CPLEX behavior with respect to numeric difficulties in LP models.
CPLEX is designed to handle the numeric difficulties of linear programming automatically. In this context, numeric difficulties mean such phenomena as:
repeated occurrence of singularities;
little or no progress toward reaching the optimal objective function value;
little or no progress in scaled infeasibility;
repeated problem perturbations; and
repeated occurrences of the solution becoming infeasible.
While CPLEX will usually achieve an optimal solution in spite of these difficulties, you can help it do so more efficiently. This section characterizes situations in which you can help.
Some problems will not be solvable even after you take the measures suggested here. For example, problems can be so poorly conditioned that their optimal solutions are beyond the numeric precision of your computer.
Numerical emphasis settings
The numerical precision emphasis parameter controls the degree of numerical caution used during optimization of a model.
C++ Name NumericalEmphasisin Concert Technology
C Name CPX_PARAM_NUMERICALEMPHASISin the Callable Library
emphasis numericalin the Interactive Optimizer
At its default setting, CPLEX employs ordinary caution in dealing with the numerical properties of the computations it must perform. Under the optional setting, CPLEX uses extreme caution.
This emphasis parameter is different in style from the various tolerance parameters in CPLEX. The purpose of the emphasis parameter is to relieve the user of the need to analyze which tolerances or other algorithmic controls to try. Instead, the user tells CPLEX that the model about to be solved is known to be susceptible to unstable numerical behavior and lets CPLEX make the decisions about how best to proceed.
There may be a trade-off between solution speed and numerical caution. You should not be surprised if your model solves less rapidly at the optional setting of this parameter, because each iteration may potentially be noticeably slower than at the default. On the other hand, if the numerical difficulty has been causing the optimizer to proceed less directly to the optimal solution, it is possible that the optional setting will reduce the number of iterations, thus leading to faster solution. When the user chooses an emphasis on extreme numerical caution, solution speed is in effect treated as no longer the primary emphasis.
Numerically sensitive data
There is no absolute link between the form of data in a model and the numeric 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.
For example, consider the constraint
x1 + 2/3 x2 = 1. In perfect arithmetic, it is equivalent
x1 + 2 x2 = 3. However, if you express the fractional
form with decimal data values, some truncation is unavoidable. If
you happen to include the truncated decimal form of the constraint
in the same model with some differently-truncated form or even the
exact-integer data form, an unexpected result could easily occur.
Consider the following problem formulation:
Maximize obj: x1 + x2 Subject To c1: 0.333333 x1 + 0.666667 x2 = 1 c2: x1 + 2 x2 = 3 End
With default numeric tolerances, this will deliver
an optimal solution of
giving an objective function value of
2.0 . Now,
see what happens when using slightly more accurate data (in terms
of the fractional values that are clearly intended to be expressed):
Maximize obj: x1 + x2 Subject To c1: 0.333333333 x1 + 0.666666667 x2 = 1 c2: x1 + 2 x2 = 3 End
The solution to this problem has
giving an optimal objective function value of
a result qualitatively different from that of the first model. Since
this latter result is the same as would be obtained by removing constraint
the model entirely, this is a more satisfactory result. Moreover,
the numeric stability of the optimal basis (as indicated by the condition
number, discussed in the next section), is vastly improved.
The result of the extra precision of the input data is a model that is less likely to be sensitive to rounding error or other effects of solving problems on finite-precision computers, or in extreme cases will be more likely to produce an answer in keeping with the intended model. The first example, above, is an instance where the data truncation has fundamentally distorted the problem being solved. Even if the exact-integer data form of the constraint is not present with the decimal form, the truncated decimal form no longer exactly represents the intended meaning and, in conjunction with other constraints in your model, could give unintended answers that are "accurate" in the context of the specific data being fed to the optimizer.
particularly wary of data in your model that has been computed (within
your program, or transmitted to your program from another via an input
file) using single-precision (32-bit) arithmetic. For example, in
C, this situation would arise from using type
double. Such data will be accurate only to about
8 decimal digits, so that (for example) if you print the data, you
might see values like
0.3333333333333333. CPLEX uses double-precision
(64-bit) arithmetic in its computations, and truncated single-precision
data carries the risk that it will convey a different meaning than
the user intends.
The underlying principle behind all the cautions in this section is that information contained in the data needs to reflect actual meaning or the optimizer may reach unstable solutions or encounter algorithmic difficulties.
Measuring problem sensitivity with basis condition number kappa
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. 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
1e+13, then a change in a single matrix coefficient
in the thirteenth place (counting from the right) 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.
condition numbers on the order of
1e+7 indicate virtually
no chance of ill conditioning. Condition numbers on the order of
only a slight chance of ill conditioning, and only if the model is
also poorly scaled or has some other numerical problems. Condition
numbers on the order of
some potential for ill conditioning. Nonetheless, because the condition
number provides an upper bound on the sensitivity to change, CPLEX
usually solves models with condition numbers in this range with little
or no trouble. However, when the order of magnitude of the condition
1e+13, numerical problems are more
likely to occur.
More generally, for a given order of magnitude
for the feasibility and optimality tolerances, dividing the feasibility
tolerance by the machine precision specifies the lower threshold for
the condition number at which point the potential for numerical difficulties
begins. For example, with the default feasibility of CPLEX and optimality
1e-6 and machine precision of
the smallest condition number for which algorithmic decisions might
be made based on round-off error. This calculation explains why,
with default parameter settings, condition numbers of
the lower threshold at which point ill conditioning may occur.
Because of this effective loss of precision for matrices with high basis condition numbers, 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.
In the Interactive Optimizer, use the command
display solution kappain order to see the basis condition number of a resident basis matrix.
In Concert Technology, use the method:
In the Callable Library, use the routine
CPXgetdblqualityto access the condition number in the double-precision variable
dvalue, like this:
status = CPXgetdblquality(env, lp, &dvalue, CPX_KAPPA);
CPLEX encounters a singularity, it removes a column from the current
basis and proceeds with its work. 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 messages to screen switch
1 (one)). After it finds an optimal solution
under these conditions, 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,
CPLEX continues its work until it reaches optimality.
new singularities occur, or the same singularities recur. CPLEX observes
a limit on the number of singularities it tolerates. The parameter
this limit. By default, the limit is ten. After encountering this
many singularities, 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 save the best factorable
basis found so far in the Interactive Optimizer, use the
with the file type
bas. When using the Component
Libraries, use the method
cplex.writeBasis or the
If CPLEX encounters repeated singularities in your problem, you may want to try alternative scaling on the problem (rather than simply increasing 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.
Stalling due to degeneracy
Highly degenerate linear programs tend to stall optimization progress in the primal and dual simplex optimizers. When stalling occurs with the primal simplex optimizer, CPLEX automatically perturbs the variable bounds; when stalling occurs with the dual simplex optimizer, CPLEX perturbs the objective function.
In either case, perturbation creates a different but closely related problem. After CPLEX has solved the perturbed problem, it removes the perturbation by resetting problem data to their original values.
If 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 CPLEX perturb the problem automatically.)
start perturbation yourself, set the parameter
of its default value of
0 (zero). The perturbation
EpPer, is usually appropriate at its default
value of 1e-6, but can be set to any value 1e-8 or larger.
you observe that your problem has been perturbed more than once, then
the perturbed problem may differ too greatly from your original problem.
In such a case, consider reducing the value of the perturbation constant perturbation
EpPer in Concert Technology,
the Callable Library).
Inability to stay feasible
If a problem repeatedly
becomes infeasible in Phase II (that is, after CPLEX has achieved
a feasible solution), then numeric difficulties may be occurring.
It may help to increase the Markowitz tolerance in such a case. By
default, the value of the parameter
and suitable values range from
Sometimes slow progress in Phase I (the period when CPLEX calculates the first feasible solution) is due to similar numeric 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 worthwhile to set a higher Markowitz tolerance, just as in the more obvious case of numeric difficulties in Phase II.