Scippy

SCIP

Solving Constraint Integer Programs

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)   ((x) >= 0.0 ? 1.0 : -1.0)
 
#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)    ((x) >= 0.0 ? 1.0 : -1.0)

sign of a value (-1 or +1)

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

Definition at line 72 of file expr_pow.c.

Referenced by computeSecant(), posintpower(), 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 74 of file expr_pow.c.

Referenced by computeSignpowerRoot().

Function Documentation

◆ computeSignpowerRoot()

static 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 118 of file expr_pow.c.

References computeHyperbolaRoot(), 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()

static 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 186 of file expr_pow.c.

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

Referenced by buildPowEstimator(), and computeSignpowerRoot().

◆ createData()

static 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 232 of file expr_pow.c.

References computeTangent(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, and SCIPallocBlockMemory.

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

◆ computeTangent()

static 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 258 of file expr_pow.c.

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

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

◆ computeSecant()

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

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 307 of file expr_pow.c.

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

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

◆ estimateParabola()

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

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 487 of file expr_pow.c.

References computeSecant(), computeTangent(), EPSISINT, estimateSignedpower(), FALSE, NULL, and TRUE.

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

◆ estimateSignedpower()

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

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 553 of file expr_pow.c.

References computeSecant(), computeTangent(), estimateHyperbolaPositive(), FALSE, NULL, SCIP_Real, SCIPisPositive(), and TRUE.

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

◆ estimateHyperbolaPositive()

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

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 701 of file expr_pow.c.

References computeSecant(), computeTangent(), EPSISINT, estimateHyperbolaMixed(), FALSE, MIN, NULL, SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by buildPowEstimator(), and estimateSignedpower().

◆ estimateHyperbolaMixed()

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

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 914 of file expr_pow.c.

References buildPowEstimator(), computeSecant(), computeTangent(), EPSISINT, FALSE, NULL, SCIPisInfinity(), SCIPisZero(), and TRUE.

Referenced by buildPowEstimator(), and estimateHyperbolaPositive().

◆ buildPowEstimator()

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

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 992 of file expr_pow.c.

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

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

◆ addTangentRefpoints()

static 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 1125 of file expr_pow.c.

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

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

◆ addSignpowerRefpoints()

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

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 1163 of file expr_pow.c.

References chooseRefpointsPow(), computeSignpowerRoot(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, and SCIPisInfinity().

Referenced by addTangentRefpoints(), chooseRefpointsPow(), and SCIP_DECL_EXPRINITESTIMATES().

◆ chooseRefpointsPow()

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

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 1218 of file expr_pow.c.

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

Referenced by addSignpowerRefpoints(), and SCIP_DECL_EXPRINITESTIMATES().

◆ SCIP_DECL_EXPRCOMPARE()

static 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 1306 of file expr_pow.c.

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

Referenced by chooseRefpointsPow().

◆ SCIP_DECL_EXPRSIMPLIFY() [1/2]

◆ SCIP_DECL_EXPRGETSYMDATA()

static SCIP_DECL_EXPRGETSYMDATA ( getSymDataPow  )
static

expression callback to get information for symmetry detection

Definition at line 1765 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRSIMPLIFY().

◆ SCIP_DECL_EXPRCOPYHDLR() [1/2]

static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrPow  )
static

expression handler copy callback

Definition at line 1788 of file expr_pow.c.

References SCIP_CALL, SCIP_DECL_EXPRFREEHDLR(), SCIP_OKAY, and SCIPincludeExprhdlrPow().

Referenced by SCIP_DECL_EXPRGETSYMDATA(), and SCIP_DECL_EXPRSIMPLIFY().

◆ SCIP_DECL_EXPRFREEHDLR()

static SCIP_DECL_EXPRFREEHDLR ( freehdlrPow  )
static

expression handler free callback

Definition at line 1797 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRCOPYHDLR().

◆ SCIP_DECL_EXPRCOPYDATA()

static SCIP_DECL_EXPRCOPYDATA ( copydataPow  )
static

expression data copy callback

Definition at line 1809 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRFREEHDLR().

◆ SCIP_DECL_EXPRFREEDATA()

static SCIP_DECL_EXPRFREEDATA ( freedataPow  )
static

expression data free callback

Definition at line 1828 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRCOPYDATA().

◆ SCIP_DECL_EXPRPRINT() [1/2]

static SCIP_DECL_EXPRPRINT ( printPow  )
static

◆ SCIP_DECL_EXPREVAL() [1/2]

static SCIP_DECL_EXPREVAL ( evalPow  )
static

◆ SCIP_DECL_EXPRFWDIFF()

static 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 1920 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPREVAL().

◆ SCIP_DECL_EXPRBWFWDIFF()

static 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 1953 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRFWDIFF().

◆ SCIP_DECL_EXPRBWDIFF() [1/2]

static SCIP_DECL_EXPRBWDIFF ( bwdiffPow  )
static

◆ SCIP_DECL_EXPRINTEVAL() [1/2]

◆ SCIP_DECL_EXPRESTIMATE() [1/2]

◆ SCIP_DECL_EXPRREVERSEPROP() [1/2]

◆ SCIP_DECL_EXPRINITESTIMATES() [1/2]

static SCIP_DECL_EXPRINITESTIMATES ( initestimatesPow  )
static

◆ SCIP_DECL_EXPRHASH() [1/2]

static SCIP_DECL_EXPRHASH ( hashPow  )
static

expression hash callback

Definition at line 2341 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRINITESTIMATES(), and SCIP_DECL_EXPRREVERSEPROP().

◆ SCIP_DECL_EXPRCURVATURE() [1/2]

static SCIP_DECL_EXPRCURVATURE ( curvaturePow  )
static

◆ SCIP_DECL_EXPRMONOTONICITY() [1/2]

◆ SCIP_DECL_EXPRINTEGRALITY()

static SCIP_DECL_EXPRINTEGRALITY ( integralityPow  )
static

◆ SCIP_DECL_EXPRSIMPLIFY() [2/2]

◆ SCIP_DECL_EXPRCOPYHDLR() [2/2]

static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrSignpower  )
static

expression handler copy callback

Definition at line 2659 of file expr_pow.c.

References SCIP_CALL, SCIP_DECL_EXPRPRINT(), SCIP_OKAY, and SCIPincludeExprhdlrSignpower().

◆ SCIP_DECL_EXPRPRINT() [2/2]

static SCIP_DECL_EXPRPRINT ( printSignpower  )
static

◆ SCIP_DECL_EXPRPARSE()

static SCIP_DECL_EXPRPARSE ( parseSignpower  )
static

expression parse callback

! [SnippetExprParseSignpower]

! [SnippetExprParseSignpower]

Definition at line 2702 of file expr_pow.c.

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

Referenced by SCIP_DECL_EXPRPRINT().

◆ SCIP_DECL_EXPREVAL() [2/2]

static SCIP_DECL_EXPREVAL ( evalSignpower  )
static

◆ SCIP_DECL_EXPRBWDIFF() [2/2]

static SCIP_DECL_EXPRBWDIFF ( bwdiffSignpower  )
static

◆ SCIP_DECL_EXPRINTEVAL() [2/2]

static 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]

static SCIP_DECL_EXPRHASH ( hashSignpower  )
static

expression hash callback

Definition at line 3054 of file expr_pow.c.

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

◆ SCIP_DECL_EXPRCURVATURE() [2/2]

static SCIP_DECL_EXPRCURVATURE ( curvatureSignpower  )
static

◆ SCIP_DECL_EXPRMONOTONICITY() [2/2]

static SCIP_DECL_EXPRMONOTONICITY ( monotonicitySignpower  )
static

expression monotonicity detection callback

Definition at line 3109 of file expr_pow.c.

References NULL, SCIP_MONOTONE_INC, SCIP_OKAY, and SCIPincludeExprhdlrPow().

◆ 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 3254 of file expr_pow.c.

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

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

◆ 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 3322 of file expr_pow.c.

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

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

◆ 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 3396 of file expr_pow.c.

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

Referenced by buildPowEstimator(), estimateSpecialPower(), and SCIPaddSquareSecant().

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 80 of file expr_pow.c.

Referenced by computeSignpowerRoot().