public functions to work with algebraic expressions
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 | |
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:
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:
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.
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) |