Scippy

SCIP

Solving Constraint Integer Programs

Functions
scip_expr.h File Reference
Public API of SCIP » Core API

Detailed Description

public functions to work with algebraic expressions

Author
Ksenia Bestuzheva
Benjamin Mueller
Felipe Serrano
Stefan Vigerske

Definition in file scip_expr.h.

#include "scip/type_scip.h"
#include "scip/type_expr.h"
#include "scip/type_misc.h"
#include "scip/type_message.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeExprhdlr (SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
 
SCIP_EXPRHDLR ** SCIPgetExprhdlrs (SCIP *scip)
 
int SCIPgetNExprhdlrs (SCIP *scip)
 
SCIP_EXPRHDLR * SCIPfindExprhdlr (SCIP *scip, const char *name)
 
SCIP_EXPRHDLR * SCIPgetExprhdlrVar (SCIP *scip)
 
SCIP_EXPRHDLR * SCIPgetExprhdlrValue (SCIP *scip)
 
SCIP_EXPRHDLR * SCIPgetExprhdlrSum (SCIP *scip)
 
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct (SCIP *scip)
 
SCIP_EXPRHDLR * SCIPgetExprhdlrPower (SCIP *scip)
 
Expressions
SCIP_RETCODE SCIPcreateExpr (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPcreateExpr2 (SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, SCIP_EXPR *child1, SCIP_EXPR *child2, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPcreateExprQuadratic (SCIP *scip, SCIP_EXPR **expr, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPcreateExprMonomial (SCIP *scip, SCIP_EXPR **expr, int nfactors, SCIP_VAR **vars, SCIP_Real *exponents, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPappendExprChild (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
 
SCIP_RETCODE SCIPreplaceExprChild (SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
 
SCIP_RETCODE SCIPremoveExprChildren (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPduplicateExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), void *mapexprdata, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPduplicateExprShallow (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPcopyExpr (SCIP *sourcescip, SCIP *targetscip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *valid)
 
SCIP_RETCODE SCIPparseExpr (SCIP *scip, SCIP_EXPR **expr, const char *exprstr, const char **finalpos, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
void SCIPcaptureExpr (SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPreleaseExpr (SCIP *scip, SCIP_EXPR **expr)
 
SCIP_Bool SCIPisExprVar (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_Bool SCIPisExprValue (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_Bool SCIPisExprSum (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_Bool SCIPisExprProduct (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_Bool SCIPisExprPower (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPprintExpr (SCIP *scip, SCIP_EXPR *expr, FILE *file)
 
SCIP_RETCODE SCIPprintExprDotInit (SCIP *scip, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
 
SCIP_RETCODE SCIPprintExprDotInit2 (SCIP *scip, SCIP_EXPRPRINTDATA **printdata, const char *filename, SCIP_EXPRPRINT_WHAT whattoprint)
 
SCIP_RETCODE SCIPprintExprDot (SCIP *scip, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPprintExprDotFinal (SCIP *scip, SCIP_EXPRPRINTDATA **printdata)
 
SCIP_RETCODE SCIPshowExpr (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPdismantleExpr (SCIP *scip, FILE *file, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPevalExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
 
SCIP_Longint SCIPgetExprNewSoltag (SCIP *scip)
 
SCIP_RETCODE SCIPevalExprActivity (SCIP *scip, SCIP_EXPR *expr)
 
int SCIPcompareExpr (SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
 
SCIP_RETCODE SCIPhashExpr (SCIP *scip, SCIP_EXPR *expr, unsigned int *hashval)
 
SCIP_RETCODE SCIPsimplifyExpr (SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
SCIP_RETCODE SCIPgetSymDataExpr (SCIP *scip, SCIP_EXPR *expr, SYM_EXPRDATA **symdata)
 
SCIP_RETCODE SCIPreplaceCommonSubexpressions (SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Bool *replacedroot)
 
SCIP_RETCODE SCIPcomputeExprCurvature (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPcomputeExprIntegrality (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPgetExprNVars (SCIP *scip, SCIP_EXPR *expr, int *nvars)
 
SCIP_RETCODE SCIPgetExprVarExprs (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **varexprs, int *nvarexprs)
 
Differentiation

Gradients (Automatic differentiation Backward mode)

Given a function, say, \(f(s(x,y),t(x,y))\) there is a common mnemonic technique to compute its partial derivatives, using a tree diagram. Suppose we want to compute the partial derivative of \(f\) w.r.t. \(x\). Write the function as a tree: 

f
|-----|
s     t
|--|  |--|
x  y  x  y

The weight of an edge between two nodes represents the partial derivative of the parent w.r.t. the children, e.g., 

f
|
s

is \( \partial_sf \). The weight of a path is the product of the weight of the edges in the path. The partial derivative of \(f\) w.r.t. \(x\) is then the sum of the weights of all paths connecting \(f\) with \(x\):

\[ \frac{\partial f}{\partial x} = \partial_s f \cdot \partial_x s + \partial_t f \cdot \partial_x t. \]

We follow this method in order to compute the gradient of an expression (root) at a given point (point). Note that an expression is a DAG representation of a function, but there is a 1-1 correspondence between paths in the DAG and path in a tree diagram of a function. Initially, we set root->derivative to 1.0. Then, traversing the tree in Depth First (see SCIPexpriterInit), for every expr that has children, we store in its i-th child, child[i]->derivative, the derivative of expr w.r.t. child evaluated at point multiplied with expr->derivative.

For example:

  1. f->derivative = 1.0
  2. s->derivative = \(\partial_s f \,\cdot\) f->derivative = \(\partial_s f\)
  3. x->derivative = \(\partial_x s \,\cdot\) s->derivative = \(\partial_x s \cdot \partial_s f\)

However, when the child is a variable expressions, we actually need to initialize child->derivative to 0.0 and afterwards add, instead of overwrite the computed value. The complete example would then be:

  1. f->derivative = 1.0, x->derivative = 0.0, y->derivative = 0.0
  2. s->derivative = \(\partial_s f \,\cdot\) f->derivative = \(\partial_s f\)
  3. x->derivative += \(\partial_x s \,\cdot\) s->derivative = \(\partial_x s \cdot \partial_s f\)
  4. y->derivative += \(\partial_y s \,\cdot\) s->derivative = \(\partial_y s \cdot \partial_s f\)
  5. t->derivative = \(\partial_t f \,\cdot\) f->derivative = \(\partial_t f\)
  6. x->derivative += \(\partial_x t \,\cdot\) t->derivative = \(\partial_x t \cdot \partial_t f\)
  7. y->derivative += \(\partial_y t \,\cdot\) t->derivative = \(\partial_y t \cdot \partial_t f\)

Note that, to compute this, we only need to know, for each expression, its partial derivatives w.r.t a given child at a point. This is what the callback SCIP_DECL_EXPRBWDIFF should return. Indeed, from "derivative of expr w.r.t. child evaluated at point multiplied with expr->derivative", note that at the moment of processing a child, we already know expr->derivative, so the only missing piece of information is "the derivative of expr w.r.t. child evaluated at point".

An equivalent way of interpreting the procedure is that expr->derivative stores the derivative of the root w.r.t. expr. This way, x->derivative and y->derivative will contain the partial derivatives of root w.r.t. the variable, that is, the gradient. Note, however, that this analogy is only correct for leave expressions, since the derivative value of an intermediate expression gets overwritten.

Hessian (Automatic differentiation Backward on Forward mode)

Computing the Hessian is more complicated since it is the derivative of the gradient, which is a function with more than one output. We compute the Hessian by computing "directions" of the Hessian, that is \(H\cdot u\) for different \(u\). This is easy in general, since it is the gradient of the scalar function \(\nabla f u\), that is, the directional derivative of \(f\) in the direction \(u\): \(D_u f\).

This is easily computed via the so called forward mode. Just as expr->derivative stores the partial derivative of the root w.r.t. expr, expr->dot stores the directional derivative of expr in the direction \(u\). Then, by the chain rule, expr->dot = \(\sum_{c:\text{children}} \partial_c \text{expr} \,\cdot\) c->dot.

Starting with x[i]->dot = \(u_i\), we can compute expr->dot for every expression at the same time we evaluate expr. Computing expr->dot is the purpose of the callback SCIP_DECL_EXPRFWDIFF. Obviously, when this callback is called, the "dots" of all children are known (just like evaluation, where the value of all children are known).

Once we have this information, we compute the gradient of this function, following the same idea as before. We define expr->bardot to be the directional derivative in direction \(u\) of the partial derivative of the root w.r.t expr, that is \(D_u (\partial_{\text{expr}} f) = D_u\) (expr->derivative).

This way, x[i]->bardot = \(D_u (\partial_{x_i} f) = e_i^T H_f u\). Hence vars->bardot contain \(H_f u\). By the chain rule, product rule, and definition we have

\begin{eqnarray*} \texttt{expr->bardot} & = & D_u (\partial_{\text{expr}} f) \\ & = & D_u ( \partial_{\text{parent}} f \cdot \partial_{\text{expr}} \text{parent} ) \\ & = & D_u ( \texttt{parent->derivative} \cdot \partial_{\text{expr}} \text{parent} ) \\ & = & \partial_{\text{expr}} \text{parent} \cdot D_u (\texttt{parent->derivative}) + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) \\ & = & \texttt{parent->bardot} \cdot \partial_{\text{expr}} \text{parent} + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) \end{eqnarray*}

Note that we have computed parent->bardot and parent->derivative at this point, while \(\partial_{\text{expr}} \text{parent}\) is the return of SCIP_DECL_EXPRBWDIFF. Hence the only information we need to compute is \(D_u (\partial_{\text{expr}} \text{parent})\). This is the purpose of the callback SCIP_DECL_EXPRBWFWDIFF.

SCIP_RETCODE SCIPevalExprGradient (SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
 
SCIP_RETCODE SCIPevalExprHessianDir (SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag, SCIP_SOL *direction)
 
Expression Handler Callbacks
 SCIP_DECL_EXPRPRINT (SCIPcallExprPrint)
 
 SCIP_DECL_EXPRCURVATURE (SCIPcallExprCurvature)
 
 SCIP_DECL_EXPRMONOTONICITY (SCIPcallExprMonotonicity)
 
SCIP_RETCODE SCIPcallExprEval (SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
 
SCIP_RETCODE SCIPcallExprEvalFwdiff (SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *direction, SCIP_Real *val, SCIP_Real *dot)
 
 SCIP_DECL_EXPRINTEVAL (SCIPcallExprInteval)
 
 SCIP_DECL_EXPRESTIMATE (SCIPcallExprEstimate)
 
 SCIP_DECL_EXPRINITESTIMATES (SCIPcallExprInitestimates)
 
 SCIP_DECL_EXPRSIMPLIFY (SCIPcallExprSimplify)
 
 SCIP_DECL_EXPRREVERSEPROP (SCIPcallExprReverseprop)
 
 SCIP_DECL_EXPRGETSYMDATA (SCIPcallExprGetSymData)
 
Expression Iterator
SCIP_RETCODE SCIPcreateExpriter (SCIP *scip, SCIP_EXPRITER **iterator)
 
void SCIPfreeExpriter (SCIP_EXPRITER **iterator)
 
Quadratic Expressions
SCIP_RETCODE SCIPcheckExprQuadratic (SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
 
void SCIPfreeExprQuadratic (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_Real SCIPevalExprQuadratic (SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol)
 
SCIP_RETCODE SCIPprintExprQuadratic (SCIP *scip, SCIP_EXPR *expr)
 
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
 
Monomial Expressions
SCIP_RETCODE SCIPgetExprMonomialData (SCIP *scip, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)