SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

power expression handler

Author
Benjamin Mueller
Ksenia Bestuzheva

Definition in file expr_pow.c.

#include <string.h>
#include "scip/expr_pow.h"
#include "scip/pub_expr.h"
#include "scip/expr_value.h"
#include "scip/expr_product.h"
#include "scip/expr_sum.h"
#include "scip/expr_exp.h"
#include "scip/expr_abs.h"
#include "symmetry/struct_symmetry.h"

Go to the source code of this file.

Macros

#define POWEXPRHDLR_NAME   "pow"
#define POWEXPRHDLR_DESC   "power expression"
#define POWEXPRHDLR_PRECEDENCE   55000
#define POWEXPRHDLR_HASHKEY   SCIPcalcFibHash(21163.0)
#define SIGNPOWEXPRHDLR_NAME   "signpower"
#define SIGNPOWEXPRHDLR_DESC   "signed power expression"
#define SIGNPOWEXPRHDLR_PRECEDENCE   56000
#define SIGNPOWEXPRHDLR_HASHKEY   SCIPcalcFibHash(21163.1)
#define INITLPMAXPOWVAL   1e+06
#define SIGN(x)
#define SIGNPOW_ROOTS_KNOWN   10

Functions

static SCIP_RETCODE computeSignpowerRoot (SCIP *scip, SCIP_Real *root, SCIP_Real exponent)
static SCIP_RETCODE computeHyperbolaRoot (SCIP *scip, SCIP_Real *root, SCIP_Real exponent)
static SCIP_RETCODE createData (SCIP *scip, SCIP_EXPRDATA **exprdata, SCIP_Real exponent)
static void computeTangent (SCIP *scip, SCIP_Bool signpower, SCIP_Real exponent, SCIP_Real xref, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *success)
static void computeSecant (SCIP *scip, SCIP_Bool signpower, SCIP_Real exponent, SCIP_Real xlb, SCIP_Real xub, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *success)
static void estimateParabola (SCIP *scip, SCIP_Real exponent, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *success)
static void estimateSignedpower (SCIP *scip, SCIP_Real exponent, SCIP_Real root, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real xlbglobal, SCIP_Real xubglobal, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *branchcand, SCIP_Bool *success)
static void estimateHyperbolaPositive (SCIP *scip, SCIP_Real exponent, SCIP_Real root, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real xlbglobal, SCIP_Real xubglobal, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *branchcand, SCIP_Bool *success)
static void estimateHyperbolaMixed (SCIP *scip, SCIP_Real exponent, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real xlbglobal, SCIP_Real xubglobal, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *branchcand, SCIP_Bool *success)
static SCIP_RETCODE buildPowEstimator (SCIP *scip, SCIP_EXPRDATA *exprdata, SCIP_Bool overestimate, SCIP_Real childlb, SCIP_Real childub, SCIP_Real childglb, SCIP_Real childgub, SCIP_Bool childintegral, SCIP_Real refpoint, SCIP_Real exponent, SCIP_Real *coef, SCIP_Real *constant, SCIP_Bool *success, SCIP_Bool *islocal, SCIP_Bool *branchcand)
static void addTangentRefpoints (SCIP *scip, SCIP_Real exponent, SCIP_Real lb, SCIP_Real ub, SCIP_Real *refpoints)
static SCIP_RETCODE addSignpowerRefpoints (SCIP *scip, SCIP_EXPRDATA *exprdata, SCIP_Real lb, SCIP_Real ub, SCIP_Real exponent, SCIP_Bool underestimate, SCIP_Real *refpoints)
static SCIP_RETCODE chooseRefpointsPow (SCIP *scip, SCIP_EXPRDATA *exprdata, SCIP_Real lb, SCIP_Real ub, SCIP_Real *refpointsunder, SCIP_Real *refpointsover, SCIP_Bool underestimate, SCIP_Bool overestimate)
static SCIP_DECL_EXPRCOMPARE (comparePow)
static SCIP_DECL_EXPRSIMPLIFY (simplifyPow)
static SCIP_DECL_EXPRGETSYMDATA (getSymDataPow)
static SCIP_DECL_EXPRCOPYHDLR (copyhdlrPow)
static SCIP_DECL_EXPRFREEHDLR (freehdlrPow)
static SCIP_DECL_EXPRCOPYDATA (copydataPow)
static SCIP_DECL_EXPRFREEDATA (freedataPow)
static SCIP_DECL_EXPRPRINT (printPow)
static SCIP_DECL_EXPREVAL (evalPow)
static SCIP_DECL_EXPRFWDIFF (fwdiffPow)
static SCIP_DECL_EXPRBWFWDIFF (bwfwdiffPow)
static SCIP_DECL_EXPRBWDIFF (bwdiffPow)
static SCIP_DECL_EXPRINTEVAL (intevalPow)
static SCIP_DECL_EXPRESTIMATE (estimatePow)
static SCIP_DECL_EXPRREVERSEPROP (reversepropPow)
static SCIP_DECL_EXPRINITESTIMATES (initestimatesPow)
static SCIP_DECL_EXPRHASH (hashPow)
static SCIP_DECL_EXPRCURVATURE (curvaturePow)
static SCIP_DECL_EXPRMONOTONICITY (monotonicityPow)
static SCIP_DECL_EXPRINTEGRALITY (integralityPow)
static SCIP_DECL_EXPRSIMPLIFY (simplifySignpower)
static SCIP_DECL_EXPRCOPYHDLR (copyhdlrSignpower)
static SCIP_DECL_EXPRPRINT (printSignpower)
static SCIP_DECL_EXPRPARSE (parseSignpower)
static SCIP_DECL_EXPREVAL (evalSignpower)
static SCIP_DECL_EXPRBWDIFF (bwdiffSignpower)
static SCIP_DECL_EXPRINTEVAL (intevalSignpower)
static SCIP_DECL_EXPRESTIMATE (estimateSignpower)
static SCIP_DECL_EXPRINITESTIMATES (initestimatesSignpower)
static SCIP_DECL_EXPRREVERSEPROP (reversepropSignpower)
static SCIP_DECL_EXPRHASH (hashSignpower)
static SCIP_DECL_EXPRCURVATURE (curvatureSignpower)
static SCIP_DECL_EXPRMONOTONICITY (monotonicitySignpower)
SCIP_RETCODE SCIPincludeExprhdlrPow (SCIP *scip)
SCIP_RETCODE SCIPincludeExprhdlrSignpower (SCIP *scip)
SCIP_RETCODE SCIPcreateExprPow (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_RETCODE SCIPcreateExprSignpower (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_Bool SCIPisExprSignpower (SCIP *scip, SCIP_EXPR *expr)
void SCIPaddSquareLinearization (SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
void SCIPaddSquareSecant (SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
void SCIPestimateRoot (SCIP *scip, SCIP_Real exponent, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *success)
SCIP_Real SCIPgetExponentExprPow (SCIP_EXPR *expr)

Variables

static SCIP_Real signpow_roots [SIGNPOW_ROOTS_KNOWN+1]

Macro Definition Documentation

◆ POWEXPRHDLR_NAME

#define POWEXPRHDLR_NAME   "pow"

◆ POWEXPRHDLR_DESC

#define POWEXPRHDLR_DESC   "power expression"

Definition at line 51 of file expr_pow.c.

Referenced by SCIPincludeExprhdlrPow().

◆ POWEXPRHDLR_PRECEDENCE

#define POWEXPRHDLR_PRECEDENCE   55000

Definition at line 52 of file expr_pow.c.

Referenced by SCIPincludeExprhdlrPow().

◆ POWEXPRHDLR_HASHKEY

#define POWEXPRHDLR_HASHKEY   SCIPcalcFibHash(21163.0)

Definition at line 53 of file expr_pow.c.

Referenced by SCIP_DECL_EXPRHASH().

◆ SIGNPOWEXPRHDLR_NAME

#define SIGNPOWEXPRHDLR_NAME   "signpower"

◆ SIGNPOWEXPRHDLR_DESC

#define SIGNPOWEXPRHDLR_DESC   "signed power expression"

Definition at line 56 of file expr_pow.c.

Referenced by SCIPincludeExprhdlrSignpower().

◆ SIGNPOWEXPRHDLR_PRECEDENCE

#define SIGNPOWEXPRHDLR_PRECEDENCE   56000

Definition at line 57 of file expr_pow.c.

Referenced by SCIPincludeExprhdlrSignpower().

◆ SIGNPOWEXPRHDLR_HASHKEY

#define SIGNPOWEXPRHDLR_HASHKEY   SCIPcalcFibHash(21163.1)

Definition at line 58 of file expr_pow.c.

Referenced by SCIP_DECL_EXPRHASH().

◆ INITLPMAXPOWVAL

#define INITLPMAXPOWVAL   1e+06

maximal allowed absolute value of power expression at bound, used for adjusting bounds in the convex case in initestimates

Definition at line 60 of file expr_pow.c.

Referenced by addTangentRefpoints().

◆ SIGN

#define SIGN ( x)
Value:
((x) >= 0.0 ? 1.0 : -1.0)
SCIP_VAR ** x

sign of a value (-1 or +1)

0.0 has sign +1 here (shouldn't matter, though)

Definition at line 71 of file expr_pow.c.

Referenced by computeSecant(), SCIP_DECL_EXPRESTIMATE(), SCIP_DECL_EXPREVAL(), and SCIP_DECL_EXPRSIMPLIFY().

◆ SIGNPOW_ROOTS_KNOWN

#define SIGNPOW_ROOTS_KNOWN   10

up to which (integer) exponents precomputed roots have been stored

Definition at line 73 of file expr_pow.c.

Referenced by computeSignpowerRoot().

Function Documentation

◆ computeSignpowerRoot()

SCIP_RETCODE computeSignpowerRoot ( SCIP * scip,
SCIP_Real * root,
SCIP_Real exponent )
static

computes positive root of the polynomial (n-1) y^n + n y^(n-1) - 1 for n > 1

Parameters
scipSCIP data structure
rootbuffer where to store computed root
exponentexponent n

Definition at line 117 of file expr_pow.c.

References assert(), NULL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPerrorMessage, SCIPfloor(), SCIPisEQ(), SCIPisIntegral(), SCIPisZero(), signpow_roots, and SIGNPOW_ROOTS_KNOWN.

Referenced by addSignpowerRefpoints(), buildPowEstimator(), SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRINITESTIMATES().

◆ computeHyperbolaRoot()

SCIP_RETCODE computeHyperbolaRoot ( SCIP * scip,
SCIP_Real * root,
SCIP_Real exponent )
static

computes negative root of the polynomial (n-1) y^n - n y^(n-1) + 1 for n < -1

Parameters
scipSCIP data structure
rootbuffer where to store computed root
exponentexponent n

Definition at line 185 of file expr_pow.c.

References assert(), NULL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPerrorMessage, and SCIPisZero().

Referenced by buildPowEstimator().

◆ createData()

SCIP_RETCODE createData ( SCIP * scip,
SCIP_EXPRDATA ** exprdata,
SCIP_Real exponent )
static

creates expression data

Parameters
scipSCIP data structure
exprdatapointer where to store expression data
exponentexponent of the power expression

Definition at line 231 of file expr_pow.c.

References assert(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, and SCIPallocBlockMemory.

Referenced by SCIP_DECL_EXPRCOPYDATA(), SCIPcreateExprPow(), and SCIPcreateExprSignpower().

◆ computeTangent()

void computeTangent ( SCIP * scip,
SCIP_Bool signpower,
SCIP_Real exponent,
SCIP_Real xref,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * success )
static

computes a tangent at a reference point by linearization

for a normal power, linearization in xref is xref^exponent + exponent * xref^(exponent-1) (x - xref) = (1-exponent) * xref^exponent + exponent * xref^(exponent-1) * x

for a signpower, linearization is the same if xref is positive for xref negative it is -(-xref)^exponent + exponent * (-xref)^(exponent-1) (x-xref) = (1-exponent) * (-xref)^(exponent-1) * xref + exponent * (-xref)^(exponent-1) * x

Parameters
scipSCIP data structure
signpowerare we signpower or normal power
exponentexponent
xrefreference point where to linearize
constantbuffer to store constant term of secant
slopebuffer to store slope of secant
successbuffer to store whether secant could be computed

Definition at line 257 of file expr_pow.c.

References assert(), EPSISINT, FALSE, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPisFinite, SCIPisNegative(), and TRUE.

Referenced by estimateHyperbolaMixed(), estimateHyperbolaPositive(), estimateParabola(), estimateSignedpower(), and SCIPestimateRoot().

◆ computeSecant()

void computeSecant ( SCIP * scip,
SCIP_Bool signpower,
SCIP_Real exponent,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * success )
static

computes a secant between lower and upper bound

secant is xlb^exponent + (xub^exponent - xlb^exponent) / (xub - xlb) * (x - xlb) = xlb^exponent - slope * xlb + slope * x with slope = (xub^exponent - xlb^exponent) / (xub - xlb) same if signpower

Parameters
scipSCIP data structure
signpowerare we signpower or normal power
exponentexponent
xlblower bound on x
xubupper bound on x
constantbuffer to store constant term of secant
slopebuffer to store slope of secant
successbuffer to store whether secant could be computed

Definition at line 306 of file expr_pow.c.

References assert(), EPSISINT, FALSE, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFinite, SCIPisInfinity(), SIGN, and TRUE.

Referenced by estimateHyperbolaMixed(), estimateHyperbolaPositive(), estimateParabola(), estimateSignedpower(), and SCIPestimateRoot().

◆ estimateParabola()

void estimateParabola ( SCIP * scip,
SCIP_Real exponent,
SCIP_Bool overestimate,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real xref,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * islocal,
SCIP_Bool * success )
static

Separation for parabola

  • even positive powers: x^2, x^4, x^6 with x arbitrary, or
  • positive powers > 1: x^1.5, x^2.5 with x >= 0
     100 +--------------------------------------------------------------------+
         |*               +                 +                +               *|
      90 |**                                                     x**2 ********|
         |  *                                                              *  |
      80 |-+*                                                              *+-|
         |   **                                                          **   |
      70 |-+   *                                                        *   +-|
         |     **                                                      **     |
      60 |-+     *                                                    *     +-|
         |       **                                                  **       |
      50 |-+       *                                                *       +-|
         |          **                                            **          |
      40 |-+          *                                          *          +-|
         |             **                                      **             |
      30 |-+            **                                    **            +-|
         |                **                                **                |
      20 |-+                **                            **                +-|
         |                   ***                        ***                   |
      10 |-+                   ***                    ***                   +-|
         |                +       *****     +    *****       +                |
       0 +--------------------------------------------------------------------+
        -10              -5                 0                5                10
    
Parameters
scipSCIP data structure
exponentexponent
overestimateshould the power be overestimated?
xlblower bound on x
xubupper bound on x
xrefreference point (where to linearize)
constantbuffer to store constant term of estimator
slopebuffer to store slope of estimator
islocalbuffer to store whether estimator only locally valid, that is, it depends on given bounds
successbuffer to store whether estimator could be computed

Definition at line 486 of file expr_pow.c.

References assert(), computeSecant(), computeTangent(), EPSISINT, FALSE, NULL, SCIP_Bool, SCIP_Real, and TRUE.

Referenced by buildPowEstimator(), SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRINITESTIMATES().

◆ estimateSignedpower()

void estimateSignedpower ( SCIP * scip,
SCIP_Real exponent,
SCIP_Real root,
SCIP_Bool overestimate,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real xref,
SCIP_Real xlbglobal,
SCIP_Real xubglobal,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * islocal,
SCIP_Bool * branchcand,
SCIP_Bool * success )
static

Separation for signpower

  • odd positive powers, x^3, x^5, x^7
  • sign(x)|x|^n for n > 1
  • lower bound on x is negative (otherwise one should use separation for parabola)
     100 +--------------------------------------------------------------------+
         |                +                 +                +              **|
         |                                                   x*abs(x) ******* |
         |                                                              **    |
         |                                                            **      |
      50 |-+                                                       ***      +-|
         |                                                      ***           |
         |                                                   ***              |
         |                                               *****                |
         |                                          *****                     |
       0 |-+                        ****************                        +-|
         |                     *****                                          |
         |                *****                                               |
         |              ***                                                   |
         |           ***                                                      |
     -50 |-+      ***                                                       +-|
         |      **                                                            |
         |    **                                                              |
         |  **                                                                |
         |**              +                 +                +                |
    -100 +--------------------------------------------------------------------+
        -10              -5                 0                5                10
    
Parameters
scipSCIP data structure
exponentexponent
rootpositive root of the polynomial (n-1) y^n + n y^(n-1) - 1, if xubglobal > 0
overestimateshould the power be overestimated?
xlblower bound on x, assumed to be non-positive
xubupper bound on x
xrefreference point (where to linearize)
xlbglobalglobal lower bound on x
xubglobalglobal upper bound on x
constantbuffer to store constant term of estimator
slopebuffer to store slope of estimator
islocalbuffer to store whether estimator only locally valid, that is, it depends on given bounds
branchcandbuffer to indicate whether estimator would improve by branching on it
successbuffer to store whether estimator could be computed

Definition at line 552 of file expr_pow.c.

References assert(), c, computeSecant(), computeTangent(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisPositive(), and TRUE.

Referenced by buildPowEstimator(), SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRINITESTIMATES().

◆ estimateHyperbolaPositive()

void estimateHyperbolaPositive ( SCIP * scip,
SCIP_Real exponent,
SCIP_Real root,
SCIP_Bool overestimate,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real xref,
SCIP_Real xlbglobal,
SCIP_Real xubglobal,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * islocal,
SCIP_Bool * branchcand,
SCIP_Bool * success )
static

Separation for positive hyperbola

  • x^-2, x^-4 with x arbitrary
  • x^-0.5, x^-1, x^-1.5, x^-3, x^-5 with x >= 0
     5 +----------------------------------------------------------------------+
       |                 +               * +*               +                 |
       |                                 *  *                 x**(-2) ******* |
     4 |-+                               *  *                               +-|
       |                                 *  *                                 |
       |                                 *  *                                 |
       |                                 *  *                                 |
     3 |-+                               *   *                              +-|
       |                                *    *                                |
       |                                *    *                                |
     2 |-+                              *    *                              +-|
       |                                *    *                                |
       |                               *      *                               |
     1 |-+                             *      *                             +-|
       |                               *      *                               |
       |                             **        **                             |
       |                   **********            **********                   |
     0 |*******************                                *******************|
       |                                                                      |
       |                 +                 +                +                 |
    -1 +----------------------------------------------------------------------+
      -10               -5                 0                5                 10
    
Parameters
scipSCIP data structure
exponentexponent
rootnegative root of the polynomial (n-1) y^n - n y^(n-1) + 1, if x has mixed sign (w.r.t. global bounds?) and underestimating
overestimateshould the power be overestimated?
xlblower bound on x
xubupper bound on x
xrefreference point (where to linearize)
xlbglobalglobal lower bound on x
xubglobalglobal upper bound on x
constantbuffer to store constant term of estimator
slopebuffer to store slope of estimator
islocalbuffer to store whether estimator only locally valid, that is, it depends on given bounds
branchcandbuffer to indicate whether estimator would improve by branching on it
successbuffer to store whether estimator could be computed

Definition at line 700 of file expr_pow.c.

References assert(), computeSecant(), computeTangent(), EPSISINT, estimateHyperbolaPositive(), FALSE, MIN, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by buildPowEstimator(), and estimateHyperbolaPositive().

◆ estimateHyperbolaMixed()

void estimateHyperbolaMixed ( SCIP * scip,
SCIP_Real exponent,
SCIP_Bool overestimate,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real xref,
SCIP_Real xlbglobal,
SCIP_Real xubglobal,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * islocal,
SCIP_Bool * branchcand,
SCIP_Bool * success )
static

Separation for mixed-sign hyperbola

  • x^-1, x^-3, x^-5 without x >= 0 (either x arbitrary or x negative)
       +----------------------------------------------------------------------+
       |                 +                 *                +                 |
     4 |-+                                  *                 x**(-1) *******-|
       |                                    *                                 |
       |                                    *                                 |
       |                                    *                                 |
     2 |-+                                  *                               +-|
       |                                     *                                |
       |                                      **                              |
       |                                        *********                     |
     0 |*********************                            *********************|
       |                     *********                                        |
       |                              **                                      |
       |                                *                                     |
    -2 |-+                               *                                  +-|
       |                                 *                                    |
       |                                 *                                    |
       |                                 *                                    |
    -4 |-+                               *                                  +-|
       |                 +                *+                +                 |
       +----------------------------------------------------------------------+
      -10               -5                 0                5                 10
    
Parameters
scipSCIP data structure
exponentexponent
overestimateshould the power be overestimated?
xlblower bound on x
xubupper bound on x
xrefreference point (where to linearize)
xlbglobalglobal lower bound on x
xubglobalglobal upper bound on x
constantbuffer to store constant term of estimator
slopebuffer to store slope of estimator
islocalbuffer to store whether estimator only locally valid, that is, it depends on given bounds
branchcandbuffer to indicate whether estimator would improve by branching on it
successbuffer to store whether estimator could be computed

Definition at line 913 of file expr_pow.c.

References assert(), computeSecant(), computeTangent(), EPSISINT, FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by buildPowEstimator().

◆ buildPowEstimator()

SCIP_RETCODE buildPowEstimator ( SCIP * scip,
SCIP_EXPRDATA * exprdata,
SCIP_Bool overestimate,
SCIP_Real childlb,
SCIP_Real childub,
SCIP_Real childglb,
SCIP_Real childgub,
SCIP_Bool childintegral,
SCIP_Real refpoint,
SCIP_Real exponent,
SCIP_Real * coef,
SCIP_Real * constant,
SCIP_Bool * success,
SCIP_Bool * islocal,
SCIP_Bool * branchcand )
static

builds an estimator for a power function

Parameters
scipSCIP data structure
exprdataexpression data
overestimateis this an overestimator?
childlblocal lower bound on the child
childublocal upper bound on the child
childglbglobal lower bound on the child
childgubglobal upper bound on the child
childintegralwhether child is integral
refpointreference point
exponentesponent
coefpointer to store the coefficient of the estimator
constantpointer to store the constant of the estimator
successpointer to store whether the estimator was built successfully
islocalpointer to store whether the estimator is valid w.r.t. local bounds only
branchcandpointer to indicate whether to consider child for branching (initialized to TRUE)

Definition at line 991 of file expr_pow.c.

References assert(), computeHyperbolaRoot(), computeSignpowerRoot(), EPSISINT, estimateHyperbolaMixed(), estimateHyperbolaPositive(), estimateParabola(), estimateSignedpower(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddSquareLinearization(), SCIPaddSquareSecant(), SCIPestimateRoot(), SCIPisInfinity(), and TRUE.

Referenced by SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRINITESTIMATES().

◆ addTangentRefpoints()

void addTangentRefpoints ( SCIP * scip,
SCIP_Real exponent,
SCIP_Real lb,
SCIP_Real ub,
SCIP_Real * refpoints )
static

fills an array of reference points for estimating on the convex side

Parameters
scipSCIP data structure
exponentexponent of the power expression
lblower bound on the child variable
ubupper bound on the child variable
refpointsarray to store the reference points

Definition at line 1124 of file expr_pow.c.

References assert(), INITLPMAXPOWVAL, MAX, MIN, NULL, REALABS, SCIP_Real, and SCIPisInfinity().

Referenced by chooseRefpointsPow(), and SCIP_DECL_EXPRINITESTIMATES().

◆ addSignpowerRefpoints()

SCIP_RETCODE addSignpowerRefpoints ( SCIP * scip,
SCIP_EXPRDATA * exprdata,
SCIP_Real lb,
SCIP_Real ub,
SCIP_Real exponent,
SCIP_Bool underestimate,
SCIP_Real * refpoints )
static

fills an array of reference points for sign(x)*abs(x)^n or x^n (n odd), where x has mixed signs

The reference points are: the lower and upper bounds (one for secant and one for tangent); and for the second tangent, the point on the convex part of the function between the point deciding between tangent and secant, and the corresponding bound

Parameters
scipSCIP data structure
exprdataexpression data
lblower bound on the child variable
ubupper bound on the child variable
exponentexponent
underestimateare the refpoints for an underestimator
refpointsarray to store the reference points

Definition at line 1162 of file expr_pow.c.

References assert(), computeSignpowerRoot(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, and SCIPisInfinity().

Referenced by chooseRefpointsPow(), and SCIP_DECL_EXPRINITESTIMATES().

◆ chooseRefpointsPow()

SCIP_RETCODE chooseRefpointsPow ( SCIP * scip,
SCIP_EXPRDATA * exprdata,
SCIP_Real lb,
SCIP_Real ub,
SCIP_Real * refpointsunder,
SCIP_Real * refpointsover,
SCIP_Bool underestimate,
SCIP_Bool overestimate )
static

choose reference points for adding initestimates cuts for a power expression

Parameters
scipSCIP data structure
exprdataexpression data
lblower bound on the child variable
ubupper bound on the child variable
refpointsunderarray to store reference points for underestimators
refpointsoverarray to store reference points for overestimators
underestimatewhether refpoints for underestimation are needed
overestimatewhether refpoints for overestimation are needed

Definition at line 1217 of file expr_pow.c.

References addSignpowerRefpoints(), addTangentRefpoints(), assert(), EPSISINT, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), and TRUE.

Referenced by SCIP_DECL_EXPRINITESTIMATES().

◆ SCIP_DECL_EXPRCOMPARE()

SCIP_DECL_EXPRCOMPARE ( comparePow )
static

compares two power expressions

the order of two power (normal or signed) is base_1^expo_1 < base_2^expo_2 if and only if base_1 < base2 or, base_1 = base_2 and expo_1 < expo_2

! [SnippetExprComparePow]

! [SnippetExprComparePow]

Definition at line 1305 of file expr_pow.c.

References SCIP_Real, SCIPcompareExpr(), SCIPexprGetChildren(), and SCIPgetExponentExprPow().

◆ SCIP_DECL_EXPRSIMPLIFY() [1/2]

◆ SCIP_DECL_EXPRGETSYMDATA()

SCIP_DECL_EXPRGETSYMDATA ( getSymDataPow )
static

expression callback to get information for symmetry detection

Definition at line 1764 of file expr_pow.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPexprGetData().

◆ SCIP_DECL_EXPRCOPYHDLR() [1/2]

SCIP_DECL_EXPRCOPYHDLR ( copyhdlrPow )
static

expression handler copy callback

Definition at line 1787 of file expr_pow.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrPow().

◆ SCIP_DECL_EXPRFREEHDLR()

SCIP_DECL_EXPRFREEHDLR ( freehdlrPow )
static

expression handler free callback

Definition at line 1796 of file expr_pow.c.

References assert(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_EXPRCOPYDATA()

SCIP_DECL_EXPRCOPYDATA ( copydataPow )
static

expression data copy callback

Definition at line 1808 of file expr_pow.c.

References assert(), createData(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPexprGetData().

◆ SCIP_DECL_EXPRFREEDATA()

SCIP_DECL_EXPRFREEDATA ( freedataPow )
static

expression data free callback

Definition at line 1827 of file expr_pow.c.

References assert(), NULL, SCIP_OKAY, SCIPexprGetData(), SCIPexprSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_EXPRPRINT() [1/2]

SCIP_DECL_EXPRPRINT ( printPow )
static

expression print callback

! [SnippetExprPrintPow]

! [SnippetExprPrintPow]

Definition at line 1845 of file expr_pow.c.

References assert(), NULL, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_EXPRITER_VISITEDCHILD, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIP_Real, SCIPgetExponentExprPow(), and SCIPinfoMessage().

◆ SCIP_DECL_EXPREVAL() [1/2]

SCIP_DECL_EXPREVAL ( evalPow )
static

◆ SCIP_DECL_EXPRFWDIFF()

SCIP_DECL_EXPRFWDIFF ( fwdiffPow )
static

derivative evaluation callback

computes <gradient, children.dot> if expr is child^p, then computes p child^(p-1) dot(child)

Definition at line 1919 of file expr_pow.c.

References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetDot(), SCIPexprGetEvalValue(), SCIPgetExponentExprPow(), and SCIPisExprValue().

◆ SCIP_DECL_EXPRBWFWDIFF()

SCIP_DECL_EXPRBWFWDIFF ( bwfwdiffPow )
static

expression backward forward derivative evaluation callback

computes partial/partial child ( <gradient, children.dot> ) if expr is child^n, then computes n * (n - 1) child^(n-2) dot(child)

Definition at line 1952 of file expr_pow.c.

References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetDot(), SCIPexprGetEvalValue(), SCIPgetExponentExprPow(), and SCIPisExprValue().

◆ SCIP_DECL_EXPRBWDIFF() [1/2]

SCIP_DECL_EXPRBWDIFF ( bwdiffPow )
static

expression derivative evaluation callback

Definition at line 1981 of file expr_pow.c.

References assert(), NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetEvalValue(), SCIPgetExponentExprPow(), and SCIPisExprValue().

◆ SCIP_DECL_EXPRINTEVAL() [1/2]

◆ SCIP_DECL_EXPRESTIMATE() [1/2]

◆ SCIP_DECL_EXPRREVERSEPROP() [1/2]

◆ SCIP_DECL_EXPRINITESTIMATES() [1/2]

SCIP_DECL_EXPRINITESTIMATES ( initestimatesPow )
static

◆ SCIP_DECL_EXPRHASH() [1/2]

SCIP_DECL_EXPRHASH ( hashPow )
static

expression hash callback

Definition at line 2340 of file expr_pow.c.

References assert(), NULL, POWEXPRHDLR_HASHKEY, SCIP_OKAY, and SCIPexprGetNChildren().

◆ SCIP_DECL_EXPRCURVATURE() [1/2]

SCIP_DECL_EXPRCURVATURE ( curvaturePow )
static

◆ SCIP_DECL_EXPRMONOTONICITY() [1/2]

◆ SCIP_DECL_EXPRINTEGRALITY()

SCIP_DECL_EXPRINTEGRALITY ( integralityPow )
static

expression integrality detection callback

Definition at line 2449 of file expr_pow.c.

References assert(), EPSISINT, FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexprIsIntegral(), and SCIPgetExponentExprPow().

◆ SCIP_DECL_EXPRSIMPLIFY() [2/2]

◆ SCIP_DECL_EXPRCOPYHDLR() [2/2]

SCIP_DECL_EXPRCOPYHDLR ( copyhdlrSignpower )
static

expression handler copy callback

Definition at line 2658 of file expr_pow.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrSignpower().

◆ SCIP_DECL_EXPRPRINT() [2/2]

SCIP_DECL_EXPRPRINT ( printSignpower )
static

◆ SCIP_DECL_EXPRPARSE()

SCIP_DECL_EXPRPARSE ( parseSignpower )
static

expression parse callback

! [SnippetExprParseSignpower]

! [SnippetExprParseSignpower]

Definition at line 2701 of file expr_pow.c.

References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprSignpower(), SCIPerrorMessage, SCIPisInfinity(), SCIPparseExpr(), SCIPparseReal(), SCIPreleaseExpr(), and TRUE.

◆ SCIP_DECL_EXPREVAL() [2/2]

SCIP_DECL_EXPREVAL ( evalSignpower )
static

◆ SCIP_DECL_EXPRBWDIFF() [2/2]

SCIP_DECL_EXPRBWDIFF ( bwdiffSignpower )
static

◆ SCIP_DECL_EXPRINTEVAL() [2/2]

SCIP_DECL_EXPRINTEVAL ( intevalSignpower )
static

◆ SCIP_DECL_EXPRESTIMATE() [2/2]

◆ SCIP_DECL_EXPRINITESTIMATES() [2/2]

◆ SCIP_DECL_EXPRREVERSEPROP() [2/2]

◆ SCIP_DECL_EXPRHASH() [2/2]

SCIP_DECL_EXPRHASH ( hashSignpower )
static

expression hash callback

Definition at line 3053 of file expr_pow.c.

References assert(), NULL, SCIP_OKAY, SCIPexprGetNChildren(), and SIGNPOWEXPRHDLR_HASHKEY.

◆ SCIP_DECL_EXPRCURVATURE() [2/2]

SCIP_DECL_EXPRCURVATURE ( curvatureSignpower )
static

◆ SCIP_DECL_EXPRMONOTONICITY() [2/2]

SCIP_DECL_EXPRMONOTONICITY ( monotonicitySignpower )
static

expression monotonicity detection callback

Definition at line 3108 of file expr_pow.c.

References assert(), NULL, result, SCIP_MONOTONE_INC, and SCIP_OKAY.

◆ SCIPaddSquareLinearization()

void SCIPaddSquareLinearization ( SCIP * scip,
SCIP_Real sqrcoef,
SCIP_Real refpoint,
SCIP_Bool isint,
SCIP_Real * lincoef,
SCIP_Real * linconstant,
SCIP_Bool * success )

computes coefficients of linearization of a square term in a reference point

Parameters
scipSCIP data structure
sqrcoefcoefficient of square term
refpointpoint where to linearize
isintwhether corresponding variable is a discrete variable, and thus linearization could be moved
lincoefbuffer to add coefficient of linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 3253 of file expr_pow.c.

References assert(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPfloor(), SCIPisInfinity(), and SCIPisIntegral().

Referenced by addBilinearTermToCut(), addRltTerm(), and buildPowEstimator().

◆ SCIPaddSquareSecant()

void SCIPaddSquareSecant ( SCIP * scip,
SCIP_Real sqrcoef,
SCIP_Real lb,
SCIP_Real ub,
SCIP_Real * lincoef,
SCIP_Real * linconstant,
SCIP_Bool * success )

computes coefficients of secant of a square term

Parameters
scipSCIP data structure
sqrcoefcoefficient of square term
lblower bound on variable
ubupper bound on variable
lincoefbuffer to add coefficient of secant
linconstantbuffer to add constant of secant
successbuffer to set to FALSE if secant has failed due to large numbers or unboundedness

Definition at line 3321 of file expr_pow.c.

References assert(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPisInfinity(), and SCIPisLE().

Referenced by addBilinearTermToCut(), addRltTerm(), and buildPowEstimator().

◆ SCIPestimateRoot()

void SCIPestimateRoot ( SCIP * scip,
SCIP_Real exponent,
SCIP_Bool overestimate,
SCIP_Real xlb,
SCIP_Real xub,
SCIP_Real xref,
SCIP_Real * constant,
SCIP_Real * slope,
SCIP_Bool * islocal,
SCIP_Bool * success )

Separation for roots with exponent in [0,1]

  • x^0.5 with x >= 0
     8 +----------------------------------------------------------------------+
       |             +             +              +             +             |
     7 |-+                                                     x**0.5 ********|
       |                                                             *********|
       |                                                      ********        |
     6 |-+                                             ********             +-|
       |                                         ******                       |
     5 |-+                                 ******                           +-|
       |                             ******                                   |
       |                        *****                                         |
     4 |-+                  ****                                            +-|
       |               *****                                                  |
     3 |-+          ****                                                    +-|
       |         ***                                                          |
       |      ***                                                             |
     2 |-+  **                                                              +-|
       |  **                                                                  |
     1 |**                                                                  +-|
       |*                                                                     |
       |*            +             +              +             +             |
     0 +----------------------------------------------------------------------+
       0             10            20             30            40            50
    
Parameters
scipSCIP data structure
exponentexponent
overestimateshould the power be overestimated?
xlblower bound on x
xubupper bound on x
xrefreference point (where to linearize)
constantbuffer to store constant term of estimator
slopebuffer to store slope of estimator
islocalbuffer to store whether estimator only locally valid, that is, it depends on given bounds
successbuffer to store whether estimator could be computed

Definition at line 3395 of file expr_pow.c.

References assert(), computeSecant(), computeTangent(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPisZero(), and TRUE.

Referenced by buildPowEstimator(), and estimateSpecialPower().

Variable Documentation

◆ signpow_roots

SCIP_Real signpow_roots[SIGNPOW_ROOTS_KNOWN+1]
static
Initial value:
= {
-1.0,
-1.0,
0.41421356237309504880,
0.5,
0.56042566045031785945,
0.60582958618826802099,
0.64146546982884663257,
0.67033204760309682774,
0.69428385661425826738,
0.71453772716733489700,
0.73192937842370733350
}

The positive root of the polynomial (n-1) y^n + n y^(n-1) - 1 is needed in separation. Here we store these roots for small integer values of n.

Definition at line 79 of file expr_pow.c.

Referenced by computeSignpowerRoot().