Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

commonly used numerical methods

Modules

 Computations With Tolerances
 methods used by the majority of operations involving floating-point computations in SCIP
 

Macros

#define SCIPisFinite(x)   ((x) == (x))
 

Functions

SCIP_Real SCIPcalcMachineEpsilon (void)
 
SCIP_Real SCIPnextafter (SCIP_Real from, SCIP_Real to)
 
SCIP_Longint SCIPcalcGreComDiv (SCIP_Longint val1, SCIP_Longint val2)
 
SCIP_Longint SCIPcalcSmaComMul (SCIP_Longint val1, SCIP_Longint val2)
 
SCIP_Longint SCIPcalcBinomCoef (int n, int m)
 
unsigned int SCIPcalcFibHash (SCIP_Real v)
 
SCIP_Bool SCIPrealToRational (SCIP_Real val, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
 
SCIP_RETCODE SCIPcalcIntegralScalar (SCIP_Real *vals, int nvals, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Real *intscalar, SCIP_Bool *success)
 
SCIP_Bool SCIPfindSimpleRational (SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom, SCIP_Longint *nominator, SCIP_Longint *denominator)
 
SCIP_Real SCIPselectSimpleValue (SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
 
SCIP_Real SCIPcalcRootNewton (SCIP_DECL_NEWTONEVAL((*function)), SCIP_DECL_NEWTONEVAL((*derivative)), SCIP_Real *params, int nparams, SCIP_Real x, SCIP_Real eps, int k)
 
SCIP_Real SCIPrelDiff (SCIP_Real val1, SCIP_Real val2)
 
SCIP_Real SCIPcomputeGap (SCIP_Real eps, SCIP_Real inf, SCIP_Real primalbound, SCIP_Real dualbound)
 

Macro Definition Documentation

◆ SCIPisFinite

#define SCIPisFinite (   x)    ((x) == (x))

Definition at line 1933 of file pub_misc.h.

Function Documentation

◆ SCIPcalcMachineEpsilon()

SCIP_Real SCIPcalcMachineEpsilon ( void  )

returns the machine epsilon: the smallest number eps > 0, for which 1.0 + eps > 1.0

Definition at line 9098 of file misc.c.

References eps, and SCIP_Real.

◆ SCIPnextafter()

SCIP_Real SCIPnextafter ( SCIP_Real  from,
SCIP_Real  to 
)

returns the next representable value of from in the direction of to

Parameters
fromvalue from which the next representable value should be returned
todirection in which the next representable value should be returned

Definition at line 9364 of file misc.c.

Referenced by computeMaxForBilinearProp(), initSolve(), SCIPintervalCos(), SCIPintervalEntropy(), SCIPintervalExp(), SCIPintervalLog(), SCIPintervalPowerScalar(), SCIPintervalPowerScalarScalar(), SCIPintervalSignPowerScalar(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), and SCIPintervalSquareRoot().

◆ SCIPcalcGreComDiv()

SCIP_Longint SCIPcalcGreComDiv ( SCIP_Longint  val1,
SCIP_Longint  val2 
)

calculates the greatest common divisor of the two given values

Parameters
val1first value of greatest common devisor calculation
val2second value of greatest common devisor calculation

Definition at line 9121 of file misc.c.

Referenced by deleteRedundantVars(), normalizeCons(), normalizeCumulativeCondition(), normalizeWeights(), rangedRowPropagation(), SCIPcalcIntegralScalar(), SCIPcalcSmaComMul(), SCIPprobScaleObj(), SCIProwCalcIntegralScalar(), SCIPsolveKnapsackExactly(), simplifyInequalities(), and tryAggregateIntVars().

◆ SCIPcalcSmaComMul()

SCIP_Longint SCIPcalcSmaComMul ( SCIP_Longint  val1,
SCIP_Longint  val2 
)

calculates the smallest common multiple of the two given values

Parameters
val1first value of smallest common multiple calculation
val2second value of smallest common multiple calculation

Definition at line 9373 of file misc.c.

References SCIP_Longint, and SCIPcalcGreComDiv().

Referenced by normalizeCons(), and tryAggregateIntVars().

◆ SCIPcalcBinomCoef()

SCIP_Longint SCIPcalcBinomCoef ( int  n,
int  m 
)

calculates a binomial coefficient n over m, choose m elements out of n, maximal value will be 33 over 16 (because the n=33 is the last line in the Pascal's triangle where each entry fits in a 4 byte value), an error occurs due to big numbers or an negative value m (and m < n) and -1 will be returned

Parameters
nnumber of different elements
mnumber to choose out of the above

Definition at line 10272 of file misc.c.

References SCIP_Longint, SCIP_LONGINT_MAX, and SCIP_Real.

◆ SCIPcalcFibHash()

unsigned int SCIPcalcFibHash ( SCIP_Real  v)

calculates hash for floating-point number by using Fibonacci hashing

Parameters
vnumber to hash

Definition at line 10347 of file misc.c.

Referenced by SCIP_DECL_EXPRHASH(), and SCIPexprhdlrHashExpr().

◆ SCIPrealToRational()

SCIP_Bool SCIPrealToRational ( SCIP_Real  val,
SCIP_Real  mindelta,
SCIP_Real  maxdelta,
SCIP_Longint  maxdnom,
SCIP_Longint nominator,
SCIP_Longint denominator 
)

converts a real number into a (approximate) rational representation, and returns TRUE iff the conversion was successful

Parameters
valreal value r to convert into rational number
mindeltaminimal allowed difference r - q of real r and rational q = n/d
maxdeltamaximal allowed difference r - q of real r and rational q = n/d
maxdnommaximal denominator allowed
nominatorpointer to store the nominator n of the rational number
denominatorpointer to store the denominator d of the rational number

Definition at line 9394 of file misc.c.

References a, b, EPSFLOOR, EPSGT, FALSE, MIN, NULL, REALABS, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_Real, simplednoms, and TRUE.

Referenced by normalizeCons(), prettifyConss(), SCIPcalcIntegralScalar(), SCIPfindSimpleRational(), SCIProwCalcIntegralScalar(), and tryAggregateIntVars().

◆ SCIPcalcIntegralScalar()

SCIP_RETCODE SCIPcalcIntegralScalar ( SCIP_Real vals,
int  nvals,
SCIP_Real  mindelta,
SCIP_Real  maxdelta,
SCIP_Longint  maxdnom,
SCIP_Real  maxscale,
SCIP_Real intscalar,
SCIP_Bool success 
)

tries to find a value, such that all given values, if scaled with this value become integral in relative allowed difference in between mindelta and maxdelta

Parameters
valsvalues to scale
nvalsnumber of values to scale
mindeltaminimal relative allowed difference of scaled coefficient s*c and integral i
maxdeltamaximal relative allowed difference of scaled coefficient s*c and integral i
maxdnommaximal denominator allowed in rational numbers
maxscalemaximal allowed scalar
intscalarpointer to store scalar that would make the coefficients integral, or NULL
successstores whether returned value is valid

Definition at line 9557 of file misc.c.

References ABS, EPSEQ, FALSE, isIntegralScalar(), MIN, nscalars, NULL, REALABS, scalars, SCIP_Bool, SCIP_DEFAULT_EPSILON, SCIP_INVALID, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPcalcGreComDiv(), SCIPdebugMessage, SCIPrealToRational(), and TRUE.

Referenced by calculateScalingValue(), cutTightenCoefs(), cutTightenCoefsQuad(), SCIPcutGenerationHeuristicCMIR(), SCIPprobScaleObj(), SCIPseparateRelaxedKnapsack(), and transformNonIntegralRow().

◆ SCIPfindSimpleRational()

SCIP_Bool SCIPfindSimpleRational ( SCIP_Real  lb,
SCIP_Real  ub,
SCIP_Longint  maxdnom,
SCIP_Longint nominator,
SCIP_Longint denominator 
)

given a (usually very small) interval, tries to find a rational number with simple denominator (i.e. a small number, probably multiplied with powers of 10) out of this interval; returns TRUE iff a valid rational number inside the interval was found

Parameters
lblower bound of the interval
ubupper bound of the interval
maxdnommaximal denominator allowed for resulting rational number
nominatorpointer to store the nominator n of the rational number
denominatorpointer to store the denominator d of the rational number

Definition at line 9777 of file misc.c.

References SCIP_Real, SCIPintervalGetRoundingMode(), SCIPintervalHasRoundingControl(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), and SCIPrealToRational().

Referenced by SCIPselectSimpleValue().

◆ SCIPselectSimpleValue()

SCIP_Real SCIPselectSimpleValue ( SCIP_Real  lb,
SCIP_Real  ub,
SCIP_Longint  maxdnom 
)

given a (usually very small) interval, selects a value inside this interval; it is tried to select a rational number with simple denominator (i.e. a small number, probably multiplied with powers of 10); if no valid rational number inside the interval was found, selects the central value of the interval

Parameters
lblower bound of the interval
ubupper bound of the interval
maxdnommaximal denominator allowed for resulting rational number

Definition at line 9824 of file misc.c.

References MAX, SCIP_Bool, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_Real, SCIPdebugMessage, SCIPdebugPrintf, and SCIPfindSimpleRational().

Referenced by convertUnaryEquality(), fixVariables(), SCIP_DECL_PRESOLEXEC(), and SCIPanalyzeDeductionsProbing().

◆ SCIPcalcRootNewton()

SCIP_Real SCIPcalcRootNewton ( SCIP_DECL_NEWTONEVAL((*function))  ,
SCIP_DECL_NEWTONEVAL((*derivative))  ,
SCIP_Real params,
int  nparams,
SCIP_Real  x,
SCIP_Real  eps,
int  k 
)

Performs the Newton Procedure from a given starting point to compute a root of the given function with specified precision and maximum number of iterations. If the procedure fails, SCIP_INVALID is returned.

Parameters
paramsparameters needed for function (can be NULL)
nparamsnumber of parameters (can be 0)
xstarting point
epstolerance
kiteration limit

Definition at line 9865 of file misc.c.

References eps, NULL, REALABS, SCIP_INVALID, SCIP_Real, and x.

Referenced by computeLeftSecantSin(), computeRightSecantSin(), and computeSolTangentSin().

◆ SCIPrelDiff()

◆ SCIPcomputeGap()

SCIP_Real SCIPcomputeGap ( SCIP_Real  eps,
SCIP_Real  inf,
SCIP_Real  primalbound,
SCIP_Real  dualbound 
)

computes the gap from the primal and the dual bound

Parameters
epsthe value treated as zero
infthe value treated as infinity
primalboundthe primal bound
dualboundthe dual bound

Definition at line 11202 of file misc.c.

References eps, EPSEQ, EPSZ, MIN, REALABS, and SCIP_Real.

Referenced by SCIPgetConcurrentGap(), SCIPgetGap(), SCIPgetTransGap(), and SCIPstoreSolutionGap().