Scippy

SCIP

Solving Constraint Integer Programs

pub_expr.h File Reference

Detailed Description

public functions to work with algebraic expressions

Author
Ksenia Bestuzheva
Benjamin Mueller
Felipe Serrano
Stefan Vigerske

Definition in file pub_expr.h.

#include "scip/def.h"
#include "scip/type_expr.h"
#include "scip/type_misc.h"

Go to the source code of this file.

Functions

void SCIPexprhdlrSetCopyFreeHdlr (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
 
void SCIPexprhdlrSetCopyFreeData (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
 
void SCIPexprhdlrSetPrint (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPRINT((*print)))
 
void SCIPexprhdlrSetParse (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
 
void SCIPexprhdlrSetCurvature (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
 
void SCIPexprhdlrSetMonotonicity (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
 
void SCIPexprhdlrSetIntegrality (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
 
void SCIPexprhdlrSetHash (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
 
void SCIPexprhdlrSetCompare (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOMPARE((*compare)))
 
void SCIPexprhdlrSetDiff (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
 
void SCIPexprhdlrSetIntEval (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
 
void SCIPexprhdlrSetSimplify (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
 
void SCIPexprhdlrSetReverseProp (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
 
void SCIPexprhdlrSetEstimate (SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
 
const char * SCIPexprhdlrGetName (SCIP_EXPRHDLR *exprhdlr)
 
const char * SCIPexprhdlrGetDescription (SCIP_EXPRHDLR *exprhdlr)
 
unsigned int SCIPexprhdlrGetPrecedence (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_EXPRHDLRDATASCIPexprhdlrGetData (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasPrint (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasBwdiff (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasFwdiff (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasIntEval (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasEstimate (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasInitEstimates (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasSimplify (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasCurvature (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasMonotonicity (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Bool SCIPexprhdlrHasReverseProp (SCIP_EXPRHDLR *exprhdlr)
 
 SCIP_DECL_SORTPTRCOMP (SCIPexprhdlrComp)
 
Expression Handler Statistics
unsigned int SCIPexprhdlrGetNCreated (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNIntevalCalls (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Real SCIPexprhdlrGetIntevalTime (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNReversepropCalls (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Real SCIPexprhdlrGetReversepropTime (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNCutoffs (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNDomainReductions (SCIP_EXPRHDLR *exprhdlr)
 
void SCIPexprhdlrIncrementNDomainReductions (SCIP_EXPRHDLR *exprhdlr, int nreductions)
 
SCIP_Longint SCIPexprhdlrGetNEstimateCalls (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Real SCIPexprhdlrGetEstimateTime (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNBranchings (SCIP_EXPRHDLR *exprhdlr)
 
void SCIPexprhdlrIncrementNBranchings (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNSimplifyCalls (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Real SCIPexprhdlrGetSimplifyTime (SCIP_EXPRHDLR *exprhdlr)
 
SCIP_Longint SCIPexprhdlrGetNSimplifications (SCIP_EXPRHDLR *exprhdlr)
 
Expressions
int SCIPexprGetNUses (SCIP_EXPR *expr)
 
int SCIPexprGetNChildren (SCIP_EXPR *expr)
 
SCIP_EXPR ** SCIPexprGetChildren (SCIP_EXPR *expr)
 
SCIP_EXPRHDLRSCIPexprGetHdlr (SCIP_EXPR *expr)
 
SCIP_EXPRDATASCIPexprGetData (SCIP_EXPR *expr)
 
void SCIPexprSetData (SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
 
SCIP_EXPR_OWNERDATASCIPexprGetOwnerData (SCIP_EXPR *expr)
 
SCIP_Real SCIPexprGetEvalValue (SCIP_EXPR *expr)
 
SCIP_Longint SCIPexprGetEvalTag (SCIP_EXPR *expr)
 
SCIP_Real SCIPexprGetDerivative (SCIP_EXPR *expr)
 
SCIP_Real SCIPexprGetDot (SCIP_EXPR *expr)
 
SCIP_Real SCIPexprGetBardot (SCIP_EXPR *expr)
 
SCIP_Longint SCIPexprGetDiffTag (SCIP_EXPR *expr)
 
SCIP_INTERVAL SCIPexprGetActivity (SCIP_EXPR *expr)
 
SCIP_Longint SCIPexprGetActivityTag (SCIP_EXPR *expr)
 
void SCIPexprSetActivity (SCIP_EXPR *expr, SCIP_INTERVAL activity, SCIP_Longint activitytag)
 
SCIP_EXPRCURV SCIPexprGetCurvature (SCIP_EXPR *expr)
 
void SCIPexprSetCurvature (SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
 
SCIP_Bool SCIPexprIsIntegral (SCIP_EXPR *expr)
 
void SCIPexprSetIntegrality (SCIP_EXPR *expr, SCIP_Bool isintegral)
 
Quadratic Expressions
void SCIPexprGetQuadraticData (SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
 
void SCIPexprGetQuadraticQuadTerm (SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
 
void SCIPexprGetQuadraticBilinTerm (SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
 
SCIP_Bool SCIPexprAreQuadraticExprsVariables (SCIP_EXPR *expr)
 
Core Expression Handlers
SCIP_VARSCIPgetVarExprVar (SCIP_EXPR *expr)
 
SCIP_Real SCIPgetValueExprValue (SCIP_EXPR *expr)
 
SCIP_RealSCIPgetCoefsExprSum (SCIP_EXPR *expr)
 
SCIP_Real SCIPgetConstantExprSum (SCIP_EXPR *expr)
 
SCIP_Real SCIPgetCoefExprProduct (SCIP_EXPR *expr)
 
SCIP_Real SCIPgetExponentExprPow (SCIP_EXPR *expr)
 
Expression Iterator

More details on the DFS mode: Many algorithms over expression trees need to traverse the tree in depth-first manner and a natural way of implementing these algorithms is by using recursion. In general, a function which traverses the tree in depth-first looks like

fun( expr )
   enterexpr()
   continue skip or abort
      for( child in expr->children )
         visitingchild()
         continue skip or abort
         fun(child, data, proceed)
         visitedchild()
         continue skip or abort
   leaveexpr()

Given that some expressions might be quite deep we provide this functionality in an iterative fashion.

Consider an expression (x*y) + z + log(x-y). The corresponding expression graph is

          [+]
      /    |   \
   [*]     |    [log]
   / \     |      |
  /   \    |     [-]
  |   |    |     / \
 [x] [y]  [z]  [x] [y]

(where [x] and [y] are actually the same expression).

If a pointer to the [+] expression is given as root to this expression, it will iterate the graph in a depth-first manner and stop at various stages.

Thus, for the above expression, the expression are visited in the following order and stages:

  • enterexpr([+])
  • visitingchild([+]), currentchild = 0
  • enterexpr([*])
  • visitingchild([*]), currentchild = 0
  • enterexpr([x])
  • leaveexpr([x])
  • visitedchild([*]), currentchild = 0
  • visitingchild([*]), currentchild = 1
  • enterexpr([y])
  • leaveexpr([y])
  • visitedchild([*]), currentchild = 1
  • leaveexpr([*])
  • visitedchild([+]), currentchild = 0
  • visitingchild([+]), currentchild = 1
  • enterexpr([z])
  • leaveexpr([z])
  • visitedchild([+]), currentchild = 1
  • visitingchild([+]), currentchild = 2
  • enterexpr([log])
  • visitingchild([log]), currentchild = 0
  • enterexpr([-])
  • visitingchild([-]), currentchild = 0
  • enterexpr([x])
  • leaveexpr([x])
  • visitedchild([-]), currentchild = 0
  • visitingchild([-]), currentchild = 1
  • enterexpr([y])
  • leaveexpr([y])
  • visitedchild([-]), currentchild = 1
  • leaveexpr([-])
  • visitedchild([log]), currentchild = 0
  • leaveexpr([log])
  • visitedchild([+]) currentchild = 2
  • leaveexpr([+])

The caller can direct the iterator to skip parts of the tree:

  • If calling SCIPexpriterSkipDFS() in SCIP_EXPRITER_ENTEREXPR stage, all children of that expression will be skipped. The SCIP_EXPRITER_LEAVEEXPR stage will still be next.
  • If calling SCIPexpriterSkipDFS() in SCIP_EXPRITER_VISITINGCHILD stage, visiting the current child will be skipped.
  • If calling SCIPexpriterSkipDFS() in SCIP_EXPRITER_VISITEDCHILD child, visiting the remaining children will be skipped.
SCIP_Bool SCIPexpriterIsInit (SCIP_EXPRITER *iterator)
 
SCIP_RETCODE SCIPexpriterInit (SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
 
SCIP_EXPRSCIPexpriterRestartDFS (SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
 
void SCIPexpriterSetStagesDFS (SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
 
SCIP_EXPRSCIPexpriterGetCurrent (SCIP_EXPRITER *iterator)
 
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS (SCIP_EXPRITER *iterator)
 
int SCIPexpriterGetChildIdxDFS (SCIP_EXPRITER *iterator)
 
SCIP_EXPRSCIPexpriterGetChildExprDFS (SCIP_EXPRITER *iterator)
 
SCIP_EXPRSCIPexpriterGetParentDFS (SCIP_EXPRITER *iterator)
 
SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData (SCIP_EXPRITER *iterator)
 
SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS (SCIP_EXPRITER *iterator)
 
SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData (SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
 
void SCIPexpriterSetCurrentUserData (SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
 
void SCIPexpriterSetExprUserData (SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_USERDATA userdata)
 
void SCIPexpriterSetChildUserData (SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
 
SCIP_EXPRSCIPexpriterGetNext (SCIP_EXPRITER *iterator)
 
SCIP_EXPRSCIPexpriterSkipDFS (SCIP_EXPRITER *iterator)
 
SCIP_Bool SCIPexpriterIsEnd (SCIP_EXPRITER *iterator)
 
Function Curvature
SCIP_EXPRCURV SCIPexprcurvAdd (SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2)
 
SCIP_EXPRCURV SCIPexprcurvNegate (SCIP_EXPRCURV curvature)
 
SCIP_EXPRCURV SCIPexprcurvMultiply (SCIP_Real factor, SCIP_EXPRCURV curvature)
 
SCIP_EXPRCURV SCIPexprcurvPower (SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent)
 
SCIP_EXPRCURV SCIPexprcurvPowerInv (SCIP_INTERVAL basebounds, SCIP_Real exponent, SCIP_EXPRCURV powercurv)
 
SCIP_EXPRCURV SCIPexprcurvMonomial (int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds)
 
SCIP_Bool SCIPexprcurvMonomialInv (SCIP_EXPRCURV monomialcurv, int nfactors, SCIP_Real *exponents, SCIP_INTERVAL *factorbounds, SCIP_EXPRCURV *factorcurv)
 
const char * SCIPexprcurvGetName (SCIP_EXPRCURV curv)