Numeric difficulties

Numerical emphasis settings

The numerical precision emphasis parameter controls the degree of numerical caution used during optimization of a model.

• C++ Name NumericalEmphasis in Concert Technology

• C Name CPX_PARAM_NUMERICALEMPHASIS in the Callable Library

• emphasis numerical in 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 1/3 x1 + 2/3 x2 = 1. In perfect arithmetic, it is equivalent to 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 x1=1.0 and x2=1.0 , 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 x1=3.0 and x2=0.0, giving an optimal objective function value of 3.0 , a result qualitatively different from that of the first model. Since this latter result is the same as would be obtained by removing constraint c1 from 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.

Be 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 float instead of 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.3333333432674408 instead of 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 is 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.

Specifically, condition numbers on the order of 1e+7 indicate virtually no chance of ill conditioning. Condition numbers on the order of 1e+8 to 1e+9 indicate 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 1e+10 to 1e+13 have 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 number exceeds 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 tolerances of 1e-6 and machine precision of 1e-16, 1e+10 is 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 1e+10 define 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 kappa in order to see the basis condition number of a resident basis matrix.

• In Concert Technology, use the method:

  IloCplex::getQuality(IloCplex::Kappa) (C++)

  IloCplex.getQuality(IloCplex.QualityType.Kappa) (Java)

  Cplex.GetQuality(Cplex.QualityType.Kappa) (.NET)

• In the Callable Library, use the routineCPXgetdblquality to access the condition number in the double-precision variable dvalue, like this:

  
  status = CPXgetdblquality(env, lp, &dvalue, CPX_KAPPA);
  

Repeated singularities

Whenever 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 CPX_PARAM_SCRIND is set to 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.

Occasionally, new singularities occur, or the same singularities recur. CPLEX observes a limit on the number of singularities it tolerates. The parameter SingLim specifies 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 write command with the file type bas. When using the Component Libraries, use the method cplex.writeBasis or the routine CPXwriteprob.

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

To start perturbation yourself, set the parameter PerInd to 1 instead of its default value of 0 (zero). The perturbation constant, EpPer, is usually appropriate at its default value of 1e-6, but can be set to any value 1e-8 or larger.

If 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 constant (EpPer in Concert Technology, CPX_PARAM_EPPER in 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 EpMrk is 0.01, and suitable values range from 0.0001 to 0.99999.

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.