[Cgl] Numerical precision in generators
fmargot at andrew.cmu.edu
fmargot at andrew.cmu.edu
Sat Jul 22 11:12:14 EDT 2006
Regarding numerical treatment of coefficients, the generators currently have
wildly different behaviors. As far as I know, the generators paying most
attention to this are CglGomory and CglRedSplit, implementing a similar
treatment. I will describe what CglRedSplit does, but CglGomory works
similarly. There are five values used for numerical accuracy:
LUB: Value considered large for the absolute value of a lower or
upper bound on a variable. Default value: 1000.
EPS: Precision of double computations. Default value: 1e-7.
EPS_COEFF: Precision for deciding if a coefficient of a generated cut is
zero. Default value: 1e-8.
EPS_COEFF_LUB: Precision for deciding if a coefficient of a generated cut is
zero when the corresponding variable has a lower or upper bound larger
than LUB in absolute value. Default value: 1e-13.
EPS_RELAX: Value used to relax slightly the right hand side of each
generated cut. Default value: 1e-8.
EPS is used when comparing two double. EPS_COEFF and EPS_COEFF_LUB are
used with the final cut, to decide which small entries should be
considered as 0.
This is a reasonable scheme, but we could ask for more: Should the cuts
be scaled to get the coefficient between two values? Should cuts where
the ratio between the largest and smallest non zero absolute values of a
coefficient is very large be discarded? If yes, should this be the
default?
These issues do not arise when combinatorial cuts (i.e. cuts with small
integers as coefficients) are generated. Should
these generators nevertheless carry the parameters used for numerical
issues. Should the numerical parameters be implemented in the base class
or in each generator?
Are there other numerical issues that should be taken into consideration?
Is there a better way to deal with numerical issues?
Francois
More information about the Cgl
mailing list