Originally posted by: JohannaH

Hello,


I'm using CPLEX 12.4 sometimes through modeler AMPL, sometimes directly via the Interactive Optimizer or the Python API (once the ".lp" is generated).
And I'm trying to solve MIP problems.


1. Setting tolerances

Regarding feasibility, (simplex) optimality, and integrality tolerances, how should they be set?
For feasibility tolerance, we should have something of the order of condition number * machine precision?
Indeed,
If tolerance > kappa * machine error >= output error: infeasible problem may become feasible
If tolerance < kappa * machine error = output error upper bound: feasible problem may become infeasible
No?


2. Kappa stats interpretation

Here is an example kappa stats result:
> Branch-and-cut subproblem optimization:
> Max condition number:                    1.3078e+12
> Percentage (number) of stable bases:     100.00%   (65940874011)
> Percentage (number) of suspicious bases:  0.00%   (144)
> Percentage (number) of unstable bases:    0.00%   (27)
> Percentage (number) of ill-posed bases:   0.00%   (0)

Most bases have a condition number < 10^7 and, if machine precision is 10^-16: maximum round-off error for one simplex iteration <= 10^-9 < feasibility tolerance
So we shouldn't worry too much, and we could tighten a bit the feasibility tolerance, right?


3. Tolerance violations

First I'd like to make sure I'm understanding the solution quality statistics:
> MILP solution error (Ax=b) (Total, Max)        5.61434e-08  1.62981e-09
error on equality constraints Ax = b ?
> MILP x bound error (Total, Max)                3.06930e-06  1.67385e-06
error on x <= x_max ?
> MILP x integrality error (Total, Max)          7.65813e-07  1.09402e-07
x = integer number ?
> MILP slack bound error (Total, Max)            2.09104e-06  2.75671e-07
error on inequality constraints Ax <= b ?

Here MILP x bound max error is greater than tolerance (set to 10^-6 by default).
What is an acceptable tolerance violation?

By the way, why would we want to look at the sum of errors? To have an approximate number of maximum possible errors?


4.

Also I've ran into instances whose resulting message was "optimal with unscaled infeasibilities".
It means that the absolute tolerances applied to the problem after scaling? (if scaling is not disabled)
Are relative tolerances re-computed if rows and columns are modified through preprocessing (for example aggregation and reduction)?


Thank you for your help,
Best regards

#CPLEXOptimizers
#DecisionOptimization

1. Assuming that by "become" you mean "appear to be", you are correct. As to how to set the tolerances, I usually leave them at defaults unless/until I see verifiable anomalies (models I are know are infeasible producing "feasible" answers or vice versa, or "optimal" solutions that are not plausibly optimal). In those cases, if I can identify a particular culprit (a constraint with bad numerics, say), I may loosen (or tighten, depending on what is needed) a specific tolerance. More likely, though, I will either (a) turn on the numerical emphasis parameter or (b) try to reformulate to improve a bad kappa value.

2. Yes, there's no sign that you need to worry, and you could tighten feasibility a bit ... but will you gain anything from doing so? If you have a MIP and the constraints each contain at least one divisible variable, tightening feasibility tolerances could easily just result to a change in the n-th decimal places of the divisible variables, where n > anything anyone cares about in implementing the solution.

3. I'm not positive, but I think the bound violations greater than 1e-6 might be the result of presolving. AFAIK, all the tolerances are applied to the presolved model, but I believe the solution quality statistics are with respect to the original model. So the worst bound violation in the presolved model might have been less than 1e-6 (if the presolver replaced original variables with combinations of original variables -- I don't know what transformations the presolver does, and I'm pretty sure that if I did know my head would explode). As for the sum of errors, I think it's insurance against the case where the worst errors are not bad in magnitude, but there are enough not-quite-terrible errors scattered throughout the solution to make the solution suspect.

4. The solution to the presolved model was optimal and feasible (to within specified tolerances). After reversing the presolve transformation, to convert that solution back to the equivalent solution of the original model, there were some feasibility tolerance violations in the original model. Yes, relative (and absolute, I believe) tolerances are recomputed after the preprocessing steps have been reversed.

Cheers,

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JohannaH

1.

By identifying a particular culprit, you mean a constraint that shows tolerance violations?

(a) turning numerical emphasis on: please see below

(b) ok for the reformulation in order to (maybe) improve condition number

 

2.

Actually, most of my variables are binary so I'd rather be accurate, feasible and sub-optimal.

 

3. and 4.

How come we cannot set absolute and relative tolerances?

Why aren't tolerances "rescaled/preprocessed" the way the problem is so that we don't run into unscaled infeasibilities?

 

I've run the resolution on the Cplex Interactive solver with different parameter settings (always relative mipgap=0.001) and the results exhibit numerical issues but I don't know what "remedy" to apply.

 

Here are the problem statistics (they seem ok):

Variables            :   20969  [Nneg: 7146,  Box: 679,  Free: 1536,
                                 Binary: 11608]
Objective nonzeros   :    4616
Linear constraints   :   46278  [Less: 39017,  Equal: 7261]
  Nonzeros           :  119983
  RHS nonzeros       :   14862

Variables            : Min LB: 0.000000         Max UB: 1.000000       
Objective nonzeros   : Min   : 0.04270000       Max   : 97.78840       
Linear constraints   :
  Nonzeros           : Min   : 0.1000004        Max   : 1800.000       
  RHS nonzeros       : Min   : 1.000000         Max   : 3.153900e+08 

 

Here are the condition number of the root node basis:

Condition number of scaled basis = 3.4e+04

 

Default run:

issue = MILP x bound error > 1e-6

MIP - Integer optimal, tolerance (0.001/1e-06):  Objective =  2.0220935298e+06
Current MIP best bound =  2.0239436374e+06 (gap = 1850.11, 0.09%)
Solution time =  185.53 sec.  Iterations = 528381  Nodes = 15772 (4025)
Deterministic time = 67473.64 ticks  (363.69 ticks/sec)

Incumbent solution:
MILP objective                                 2.0220935298e+06
MILP solution norm |x| (Total, Max)            1.88242e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.61434e-08  1.62981e-09
MILP x bound error (Total, Max)                3.06930e-06  1.67385e-06
MILP x integrality error (Total, Max)          7.65813e-07  1.09402e-07
MILP slack bound error (Total, Max)            2.09104e-06  2.75671e-07

Branch-and-cut subproblem optimization:
Max condition number:                    1.3078e+12
Percentage (number) of stable bases:     100.00%   (65940874011)
Percentage (number) of suspicious bases:  0.00%   (144)
Percentage (number) of unstable bases:    0.00%   (27)
Percentage (number) of ill-posed bases:   0.00%   (0)

 

simplex feasibility tolerance 1e-7:

issue = MILP x bound error > 1e-7 and explicit numerical difficulties warning

MIP - Integer optimal, tolerance (0.001/1e-06):  Objective =  2.0219196004e+06
Current MIP best bound =  2.0239246585e+06 (gap = 2005.06, 0.10%)
Solution time =  166.23 sec.  Iterations = 526200  Nodes = 15146 (2986)
Deterministic time = 60335.05 ticks  (362.96 ticks/sec)

Incumbent solution:
MILP objective                                 2.0219196004e+06
MILP solution norm |x| (Total, Max)            1.88088e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.77496e-08  1.62981e-09
MILP x bound error (Total, Max)                2.31245e-06  9.46309e-07
MILP x integrality error (Total, Max)          3.11065e-07  6.18503e-08
MILP slack bound error (Total, Max)            1.50099e-06  2.32365e-07

Branch-and-cut subproblem optimization:
Max condition number:                    2.8959e+12
Percentage (number) of stable bases:     100.00%   (69678780804)
Percentage (number) of suspicious bases:  0.00%   (3888)
Percentage (number) of unstable bases:    0.00%   (2177298)
Percentage (number) of ill-posed bases:   0.00%   (0)
Attention level:                         0.000009
CPLEX encountered numerical difficulties while solving this model.

 

simplex feasibility tolerance 1e-7, numerical emphasis 1:

issue = MILP x bound error > 1e-7, explicit numerical difficulties warning, dramatic increase in resolution time

MIP - Aborted, integer feasible:  Objective =  2.0189020529e+06
Current MIP best bound =  2.0238987533e+06 (gap = 4996.7, 0.25%)
Solution time = 1260.78 sec.  Iterations = 846278  Nodes = 47785 (36466)
Deterministic time = 611338.63 ticks  (484.89 ticks/sec)

Incumbent solution:
MILP objective                                 2.0189020529e+06
MILP solution norm |x| (Total, Max)            1.88230e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        6.26478e-08  1.62981e-09
MILP x bound error (Total, Max)                4.00553e-06  1.21983e-06
MILP x integrality error (Total, Max)          6.47647e-07  7.97276e-08
MILP slack bound error (Total, Max)            1.75866e-06  2.65893e-07

Branch-and-cut subproblem optimization:
Max condition number:                    4.6866e+12
Percentage (number) of stable bases:     99.97%   (5667911624)
Percentage (number) of suspicious bases:  0.00%   (896)
Percentage (number) of unstable bases:    0.03%   (1507971)
Percentage (number) of ill-posed bases:   0.00%   (0)
Attention level:                         0.000080
CPLEX encountered numerical difficulties while solving this model.

 

simplex feasibility tolerance 1e-7, scaling 1 (aggressive):

issue = dramatic increase in resolution time

MIP - Aborted, integer feasible:  Objective =  2.0039138217e+06
Current MIP best bound =  2.0238748412e+06 (gap = 19961, 1.00%)
Solution time = 1864.81 sec.  Iterations = 2174711  Nodes = 144736 (135950)
Deterministic time = 690492.28 ticks  (370.27 ticks/sec)

Incumbent solution:
MILP objective                                 2.0039138217e+06
MILP solution norm |x| (Total, Max)            1.88137e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.96949e-08  1.62981e-09
MILP x bound error (Total, Max)                1.93613e-08  9.06981e-09
MILP x integrality error (Total, Max)          3.51803e-06  3.49989e-06
MILP slack bound error (Total, Max)            6.54068e-07  6.26314e-08

Branch-and-cut subproblem optimization:
Max condition number:                    7.5554e+07
Percentage (number) of stable bases:     100.00%   (8943978177)
Percentage (number) of suspicious bases:  0.00%   (1729)
Percentage (number) of unstable bases:    0.00%   (0)
Percentage (number) of ill-posed bases:   0.00%   (0)

 

simplex feasibility tolerance 1e-7, scaling -1 (off):

issue = MILP x bound error > 1e-7, explicit numerical difficulties warning, all bases are unstable

MIP - Integer optimal, tolerance (0.001/1e-06):  Objective =  2.0222121038e+06
Current MIP best bound =  2.0237949478e+06 (gap = 1582.84, 0.08%)
Solution time =  479.70 sec.  Iterations = 770412  Nodes = 29088 (15346)
Deterministic time = 196744.81 ticks  (410.14 ticks/sec)

Incumbent solution:
MILP objective                                 2.0222121038e+06
MILP solution norm |x| (Total, Max)            1.88149e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.72130e-08  1.57888e-09
MILP x bound error (Total, Max)                2.54407e-06  1.02891e-06
MILP x integrality error (Total, Max)          4.70744e-07  6.72492e-08
MILP slack bound error (Total, Max)            1.50136e-06  2.38419e-07

Branch-and-cut subproblem optimization:
Max condition number:                    9.0802e+17
Percentage (number) of stable bases:      0.00%   (0)
Percentage (number) of suspicious bases:  0.00%   (0)
Percentage (number) of unstable bases:   100.00%   (185932502640)
Percentage (number) of ill-posed bases:   0.00%   (5229360)
Attention level:                         0.300020
CPLEX encountered numerical difficulties while solving this model.

 

simplex feasibility tolerance 1e-7, no presolve

issue = dramatic increase in resolution, explicit numerical difficulties warning, all bases are suspicious

MIP - Aborted, integer feasible:  Objective =  2.0133835588e+06
Current MIP best bound =  2.0237508649e+06 (gap = 10367.3, 0.51%)
Solution time = 2098.49 sec.  Iterations = 14876944  Nodes = 196669 (183708)
Deterministic time = 455076.56 ticks  (216.86 ticks/sec)

Incumbent solution:
MILP objective                                 2.0133835588e+06
MILP solution norm |x| (Total, Max)            1.88248e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.30054e-08  1.42427e-09
MILP x bound error (Total, Max)                2.34245e-08  1.01684e-08
MILP x integrality error (Total, Max)          4.87181e-07  6.81600e-08
MILP slack bound error (Total, Max)            5.39528e-07  6.81600e-08

Branch-and-cut subproblem optimization:
Max condition number:                    1.9134e+15
Percentage (number) of stable bases:      0.00%   (0)
Percentage (number) of suspicious bases: 98.83%   (251947)
Percentage (number) of unstable bases:    1.17%   (2978)
Percentage (number) of ill-posed bases:   0.00%   (6)
Attention level:                         0.013411
CPLEX encountered numerical difficulties while solving this model.

 

simplex feasibility tolerance 1e-7, no cuts

issue = MILP x bound error > 1e-7, no integer solution/dramatic increase in resolution, explicit numerical difficulties warning

MIP - Aborted, no integer solution.
Current MIP best bound =  2.0245965599e+06 (gap is infinite)
Solution time = 1942.39 sec.  Iterations = 3509967  Nodes = 232857 (220926)
Deterministic time = 583172.80 ticks  (300.23 ticks/sec)

Branch-and-cut subproblem optimization:
Max condition number:                    6.9965e+10
Percentage (number) of stable bases:     100.00%   (189704259256)
Percentage (number) of suspicious bases:  0.00%   (1)
Percentage (number) of unstable bases:    0.00%   (8128513)
Percentage (number) of ill-posed bases:   0.00%   (0)
Attention level:                         0.000013
CPLEX encountered numerical difficulties while solving this model.

 

simplex feasibility tolerance 1e-7, no Gomory cuts

issue = MILP x bound error > 1e-7

MIP - Integer optimal, tolerance (0.001/1e-06):  Objective =  2.0225295573e+06
Current MIP best bound =  2.0245509146e+06 (gap = 2021.36, 0.10%)
Solution time =  366.64 sec.  Iterations = 686685  Nodes = 31975 (13204)
Deterministic time = 131267.17 ticks  (358.02 ticks/sec)

Incumbent solution:
MILP objective                                 2.0225295573e+06
MILP solution norm |x| (Total, Max)            1.88150e+10  1.60515e+08
MILP solution error (Ax=b) (Total, Max)        5.92491e-08  1.42427e-09
MILP x bound error (Total, Max)                2.41664e-06  7.29835e-07
MILP x integrality error (Total, Max)          4.06632e-07  4.77011e-08
MILP slack bound error (Total, Max)            1.41010e-06  2.73343e-07

Branch-and-cut subproblem optimization:
Max condition number:                    2.2369e+12
Percentage (number) of stable bases:     100.00%   (1402446936441065501)
Percentage (number) of suspicious bases:  0.00%   (325140480)
Percentage (number) of unstable bases:    0.00%   (655808348160)
Percentage (number) of ill-posed bases:   0.00%   (0)

 

Thank you in advance for your help,

Cheers

#CPLEXOptimizers
#DecisionOptimization

1.

By identifying a particular culprit, you mean a constraint that shows tolerance violations?

If one or more constraints exhibit signs of excessive rounding error (and I can't reformulate, or solve it by turning on numerical emphasis), I may fiddle with EpRHS. If the problem manifests in variables that slightly violate their bounds, same fix. I can't recall what symptom has in the past made me think to try relaxing the integrality restriction (EpInt), but that has helped at least once. There's also the Markowitz tolerance (EpMrk), which does not relate directly to constraint feasibility or integrality, but can force CPLEX to choose pivots that lead to less rounding error in some cases. (I'm not sure, but turning on the numerical emphasis switch may cause CPLEX to tweak the Markowitz tolerance, possibly among other things.)

Usually what makes me think to play with the tolerances (rather than just turn on numerical emphasis and/or smack the monitor a couple of times) is fixing a known feasible solution (usually by setting lower bound = upper bound = desired value on each variable) and having CPLEX tell me that the known feasible solution is not feasible, then using the conflict refiner to find out specifically what is looking infeasible to CPLEX.

3. and 4.

How come we cannot set absolute and relative tolerances?

Why aren't tolerances "rescaled/preprocessed" the way the problem is so that we don't run into unscaled infeasibilities?

I think what you are asking does not make sense mathematically. Suppose that, as part of the preprocessing, the original vector x of variables is linearly transformed into new variables y = Tx, where T is nonsingular. CPLEX solves the model, finds a solution y* that, among other things, appears to satisfy all bounds (to within some precision p), and then reverses the transformation to get x* = Tinverse y*. If T and Tinverse have poor condition number, then bound errors may be substantially inflated during the return transformation from y* to x*. To achieve the desired precision in x*, you may need a prohibitively tight precision in y*, something that simply can't be achieved.

Various printouts:

Sorry, my eyes stopped focusing around the fourth one. You said "most" of the variables were binary. Are there divisible (or general integer) variables as well? You might want to try solving with numerical emphasis on, capturing an allegedly feasible if not optimal solution, fixing the bounds of all the integer variables to match that solution (in the original model), then solving the reduced model as an LP, looking at solution quality, percent stable bases etc.

Bottom line, though, I think you might want to look for a reformulation. Often, though not always, mixing either variables or constraints whose coefficients differ by several orders of magnitude contributes to the problem, even if the diagnostics suggest that the scaling is not too horrible. If you have symmetry reduction on, you might want to toggle it off for a trial. I can't recall which version of CPLEX it was, but symmetry reduction actually caused me to get an incorrect solution once.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JohannaH

Thank you again Paul.

 

1.

OK

 

3. 4.

I think we agree, it mathematically makes sense to consider the condition number of the inverse of the presolve transformation... but it may be impractical.

 

Results and logs:

Sorry for the lack of legibility.

Rechecking feasibility and reformulating accordingly are the remedies then.

Subsidiary question: is there a way to fix variables of previous solution with the Interactive Optimizer?

 

Thank you

#CPLEXOptimizers
#DecisionOptimization

Subsidiary question: is there a way to fix variables of previous solution with the Interactive Optimizer?

The only way I know to fix individual variables is to set both their bounds at the target value:

ch(ange) bo(unds) <variable name> b(oth) <new value>

If you solve a MILP and want to fix all the integer variables at their current values (leaving the divisible variables alone), you can do that with

ch(ange) pr(oblem) fixed_milp

- Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: JohannaH

Thank you very much for the tip; let's hope cplex trully fixes the integer variables and does not let them to their possible rounded values...

Actually, regarding the absolute/relative precision, wouldn't it make sense to distinguish the two as the "floating-point scale" is denser close to zero and scarcer when you get close to the highest representable number?

Thank you once again

#CPLEXOptimizers
#DecisionOptimization

They do have both absolute and relative precisions for the optimality criterion. As for why they do not have both for constraint tolerances, you'd have to ask a developer. Possibly they're trying to encourage us to scale our constraints so that the RHS values are neither overly large nor overly small. :-)

#CPLEXOptimizers
#DecisionOptimization