scip_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 scip_expr.h.

#include "scip/type_scip.h"
#include "scip/type_expr.h"
#include "scip/type_misc.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	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: f->derivative = 1.0 s->derivative = \(\partial_s f \,\cdot\) f->derivative = \(\partial_s f\) 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: f->derivative = 1.0, x->derivative = 0.0, y->derivative = 0.0 s->derivative = \(\partial_s f \,\cdot\) f->derivative = \(\partial_s f\) x->derivative += \(\partial_x s \,\cdot\) s->derivative = \(\partial_x s \cdot \partial_s f\) y->derivative += \(\partial_y s \,\cdot\) s->derivative = \(\partial_y s \cdot \partial_s f\) t->derivative = \(\partial_t f \,\cdot\) f->derivative = \(\partial_t f\) x->derivative += \(\partial_x t \,\cdot\) t->derivative = \(\partial_x t \cdot \partial_t f\) 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)
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)