Detailed Description

commonly used numerical methods

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

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 numerator, SCIP_Longint denominator)

SCIP_Bool	SCIPrealIsExactlyIntegral (SCIP_Real val)

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_RETCODE	SCIPcalcIntegralScalarExact (BMS_BUFMEM buffer, SCIP_RATIONAL vals, int nvals, SCIP_Real maxscale, SCIP_RATIONAL intscalar, SCIP_Bool *success)

SCIP_Bool	SCIPfindSimpleRational (SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom, SCIP_Longint numerator, 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)

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 9174 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

from	value from which the next representable value should be returned
to	direction in which the next representable value should be returned

Definition at line 9440 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

val1	first value of greatest common devisor calculation
val2	second value of greatest common devisor calculation

Definition at line 9197 of file misc.c.

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

◆ SCIPcalcSmaComMul()

SCIP_Longint SCIPcalcSmaComMul	(	SCIP_Longint	val1,
		SCIP_Longint	val2
	)

calculates the smallest common multiple of the two given values

Parameters

val1	first value of smallest common multiple calculation
val2	second value of smallest common multiple calculation

Definition at line 9449 of file misc.c.

References SCIP_Longint, and SCIPcalcGreComDiv().

Referenced by normalizeCons(), tryAggregateIntVars(), and tryAggregateIntVarsExact().

◆ 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

n	number of different elements
m	number to choose out of the above

Definition at line 10387 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

v	number to hash

Definition at line 10462 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 *	numerator,
		SCIP_Longint *	denominator
	)

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

Parameters

val	real value r to convert into rational number
mindelta	minimal allowed difference r - q of real r and rational q = n/d
maxdelta	maximal allowed difference r - q of real r and rational q = n/d
maxdnom	maximal denominator allowed
numerator	pointer to store the numerator n of the rational number
denominator	pointer to store the denominator d of the rational number

Definition at line 9470 of file misc.c.

References a, b, scip::denominator(), EPSFLOOR, EPSGT, FALSE, MIN, NULL, scip::numerator(), REALABS, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_Real, simplednoms, and TRUE.

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

◆ SCIPrealIsExactlyIntegral()

SCIP_Bool SCIPrealIsExactlyIntegral ( SCIP_Real val )

checks, if value is integral without any tolerances

Parameters

val	value to process

Definition at line 9604 of file misc.c.

Referenced by certificatePrintMirSplit(), cutsSubstituteMIRSafely(), rowAddCoef(), rowChgCoefPos(), rowMerge(), rowScale(), and SCIPaggrRowSumRows().

◆ 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

vals	values to scale
nvals	number of values to scale
mindelta	minimal relative allowed difference of scaled coefficient s*c and integral i
maxdelta	maximal relative allowed difference of scaled coefficient s*c and integral i
maxdnom	maximal denominator allowed in rational numbers
maxscale	maximal allowed scalar
intscalar	pointer to store scalar that would make the coefficients integral, or NULL
success	stores whether returned value is valid

Definition at line 9641 of file misc.c.

References ABS, scip::denominator(), EPSEQ, FALSE, isIntegralScalar(), MIN, nscalars, NULL, scip::numerator(), 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(), cutTightenCoefsSafely(), SCIPcutGenerationHeuristicCMIR(), SCIPprobScaleObj(), SCIPseparateRelaxedKnapsack(), and transformNonIntegralRow().

◆ SCIPcalcIntegralScalarExact()

SCIP_RETCODE SCIPcalcIntegralScalarExact	(	BMS_BUFMEM *	buffer,
		SCIP_RATIONAL **	vals,
		int	nvals,
		SCIP_Real	maxscale,
		SCIP_RATIONAL *	intscalar,
		SCIP_Bool *	success
	)

tries to find a value, such that all given values, if scaled with this value become integral

Parameters

buffer	buffer memory
vals	values to scale
nvals	number of values to scale
maxscale	maximal allowed scalar
intscalar	pointer to store scalar that would make the coefficients integral
success	stores whether returned value is valid

Definition at line 9842 of file misc.c.

References ABS, scip::denominator(), FALSE, NULL, scip::numerator(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIPcalcGreComDiv(), SCIPdebugMessage, SCIPrationalCanonicalize(), SCIPrationalCreateBuffer(), SCIPrationalDenominator(), SCIPrationalFreeBuffer(), SCIPrationalIsZero(), SCIPrationalMult(), SCIPrationalNumerator(), SCIPrationalSetFraction(), and TRUE.

Referenced by probScaleObjExact().

◆ SCIPfindSimpleRational()

SCIP_Bool SCIPfindSimpleRational	(	SCIP_Real	lb,
		SCIP_Real	ub,
		SCIP_Longint	maxdnom,
		SCIP_Longint *	numerator,
		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

lb	lower bound of the interval
ub	upper bound of the interval
maxdnom	maximal denominator allowed for resulting rational number
numerator	pointer to store the numerator n of the rational number
denominator	pointer to store the denominator d of the rational number

Definition at line 9994 of file misc.c.

References scip::denominator(), scip::numerator(), 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

lb	lower bound of the interval
ub	upper bound of the interval
maxdnom	maximal denominator allowed for resulting rational number

Definition at line 10041 of file misc.c.

References scip::denominator(), MAX, scip::numerator(), 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

params	parameters needed for function (can be NULL)
nparams	number of parameters (can be 0)
x	starting point
eps	tolerance
k	iteration limit

Definition at line 10082 of file misc.c.

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

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

◆ SCIPrelDiff()

SCIP_Real SCIPrelDiff	(	SCIP_Real	val1,
		SCIP_Real	val2
	)

returns the relative difference: (val1-val2)/max(|val1|,|val2|,1.0)

Parameters

val1	first value to be compared
val2	second value to be compared

Definition at line 11162 of file misc.c.

References MAX3, REALABS, and SCIP_Real.

Referenced by checkCons(), checkCumulativeCondition(), checkOrigPbCons(), checkSolOrig(), createGenVBound(), getIntegralScalar(), getScaledDualWeight(), isConsViolated(), isIntegralScalar(), priceAndCutLoop(), SCIP_DECL_CONSCHECK(), SCIPbendersSubproblemIsOptimal(), SCIPbranchExecExtern(), SCIPbranchGetBranchingPoint(), SCIPconcsolverSync(), SCIPcutGenerationHeuristicCMIR(), SCIPintervalAreDisjointEps(), SCIPintervalIntersectEps(), SCIPsolCheckOrig(), SCIPtreeBranchVar(), SCIPtreeBranchVarNary(), SCIPvalidateSolve(), solveBendersSubproblems(), and updateBestCandidate().

◆ 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

eps	the value treated as zero
inf	the value treated as infinity
primalbound	the primal bound
dualbound	the dual bound

Definition at line 11180 of file misc.c.

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

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

SCIP

Detailed Description

Modules

Functions

Function Documentation

◆ SCIPcalcMachineEpsilon()

◆ SCIPnextafter()

◆ SCIPcalcGreComDiv()

◆ SCIPcalcSmaComMul()

◆ SCIPcalcBinomCoef()

◆ SCIPcalcFibHash()

◆ SCIPrealToRational()

◆ SCIPrealIsExactlyIntegral()

◆ SCIPcalcIntegralScalar()

◆ SCIPcalcIntegralScalarExact()

◆ SCIPfindSimpleRational()

◆ SCIPselectSimpleValue()

◆ SCIPcalcRootNewton()

◆ SCIPrelDiff()

◆ SCIPcomputeGap()