Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

public functions to work with algebraic expressions

Author
Ksenia Bestuzheva
Benjamin Mueller
Felipe Serrano
Stefan Vigerske

Definition in file scip_expr.c.

#include <string.h>
#include <ctype.h>
#include "scip/scip_expr.h"
#include "scip/expr.h"
#include "scip/set.h"
#include "scip/misc.h"
#include "scip/scip_copy.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_prob.h"
#include "scip/scip_var.h"
#include "scip/scip_sol.h"
#include "scip/pub_var.h"
#include "scip/struct_scip.h"
#include "scip/struct_mem.h"
#include "scip/struct_stat.h"
#include "scip/expr_value.h"
#include "scip/expr_var.h"
#include "scip/expr_sum.h"
#include "scip/expr_product.h"
#include "scip/expr_pow.h"

Go to the source code of this file.

Data Structures

struct  COPY_MAPEXPR_DATA
 
struct  COMMONSUBEXPR_HASH_DATA
 

Functions

static SCIP_DECL_EXPR_MAPEXPR (copyVarExpr)
 
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_EXPRHDLRSCIPfindExprhdlr (SCIP *scip, const char *name)
 
SCIP_EXPRHDLRSCIPgetExprhdlrVar (SCIP *scip)
 
SCIP_EXPRHDLRSCIPgetExprhdlrValue (SCIP *scip)
 
SCIP_EXPRHDLRSCIPgetExprhdlrSum (SCIP *scip)
 
SCIP_EXPRHDLRSCIPgetExprhdlrProduct (SCIP *scip)
 
SCIP_EXPRHDLRSCIPgetExprhdlrPower (SCIP *scip)
 
Simplify methods (internal)
static SCIP_RETCODE findEqualExpr (SCIP_SET *set, SCIP_EXPR *expr, SCIP_MULTIHASH *key2expr, SCIP_EXPR **newexpr)
 
static SCIP_DECL_HASHGETKEY (hashCommonSubexprGetKey)
 
static SCIP_DECL_HASHKEYEQ (hashCommonSubexprEq)
 
static SCIP_DECL_HASHKEYVAL (hashCommonSubexprKeyval)
 
static SCIP_RETCODE hashExpr (SCIP_SET *set, BMS_BUFMEM *bufmem, SCIP_EXPR *expr, SCIP_EXPRITER *hashiterator, int *nvisitedexprs)
 
Expression Methods
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 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)
 
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)
 
 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 Methods
SCIP_RETCODE SCIPcreateExpriter (SCIP *scip, SCIP_EXPRITER **iterator)
 
void SCIPfreeExpriter (SCIP_EXPRITER **iterator)
 
Quadratic expression functions
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)
 

Parsing methods (internal)

Here is an attempt at defining the grammar of an expression. We use upper case names for variables (in the grammar sense) and terminals are between "". Loosely speaking, a Base will be any "block", a Factor is a Base to a power, a Term is a product of Factors and an Expression is a sum of terms. The actual definition:

Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
Term       -> Factor { ("*" | "/" ) Factor }
Factor     -> Base [ "^" "number" | "^(" "number" ")" ]
Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")

where [a|b] means a or b or none, (a|b) means a or b, {a} means 0 or more a.

Note that Op and OpExpression are undefined. Op corresponds to the name of an expression handler and OpExpression to whatever string the expression handler accepts (through its parse method).

parse(Expr|Term|Base) returns an SCIP_EXPR

 Term       -> Factor { ("*" | "/" | "^") Factor } 
#define debugParse   while( FALSE ) printf
 
static SCIP_RETCODE parseExpr (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **exprtree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
static SCIP_RETCODE parseBase (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **basetree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
static SCIP_RETCODE parseFactor (SCIP *scip, SCIP_Bool isdenominator, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **factortree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 
static SCIP_RETCODE parseTerm (SCIP *scip, SCIP_HASHMAP *vartoexprvarmap, const char *expr, const char **newpos, SCIP_EXPR **termtree, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
 

Macro Definition Documentation

◆ debugParse

#define debugParse   while( FALSE ) printf

Definition at line 144 of file scip_expr.c.

Referenced by parseBase(), parseExpr(), parseFactor(), and parseTerm().

Function Documentation

◆ SCIP_DECL_EXPR_MAPEXPR()

static SCIP_DECL_EXPR_MAPEXPR ( copyVarExpr  )
static

variable expression mapping callback to call when copying expressions (within same or different SCIPs)

Definition at line 81 of file scip_expr.c.

References COPY_MAPEXPR_DATA::consmap, FALSE, COPY_MAPEXPR_DATA::global, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateExprVar(), SCIPgetVarCopy(), SCIPgetVarExprVar(), SCIPisExprVar(), COPY_MAPEXPR_DATA::valid, and COPY_MAPEXPR_DATA::varmap.

◆ parseExpr()

static SCIP_RETCODE parseExpr ( SCIP scip,
SCIP_HASHMAP vartoexprvarmap,
const char *  expr,
const char **  newpos,
SCIP_EXPR **  exprtree,
SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))  ,
void *  ownercreatedata 
)
static

parses an expression and builds a sum-expression with children

Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
Parameters
scipSCIP data structure
vartoexprvarmaphashmap to map between scip vars and var expressions
exprexpr that we are parsing
newposbuffer to store the position of expr where we finished reading
exprtreebuffer to store the expr parsed by Expr
ownercreatedatadata to pass to ownercreate

Definition at line 521 of file scip_expr.c.

References debugParse, NULL, parseTerm(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPexprIsValue(), SCIPgetValueExprValue(), SCIPreleaseExpr(), SCIPstrToRealValue(), and Scip::set.

Referenced by parseBase(), and SCIPparseExpr().

◆ parseBase()

static SCIP_RETCODE parseBase ( SCIP scip,
SCIP_HASHMAP vartoexprvarmap,
const char *  expr,
const char **  newpos,
SCIP_EXPR **  basetree,
SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))  ,
void *  ownercreatedata 
)
static

Parses base to build a value, variable, sum, or function-like ("func(...)") expression.

Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
Parameters
scipSCIP data structure
vartoexprvarmaphashmap to map between SCIP vars and var expressions
exprexpr that we are parsing
newposbuffer to store the position of expr where we finished reading
basetreebuffer to store the expr parsed by Base
ownercreatedatadata to pass to ownercreate

Definition at line 165 of file scip_expr.c.

References debugParse, NULL, parseExpr(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprValue(), SCIPcreateExprVar(), SCIPerrorMessage, SCIPexprCapture(), SCIPexprhdlrParseExpr(), SCIPfindExprhdlr(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPparseVarName(), SCIPreleaseExpr(), SCIPstrToRealValue(), SCIPvarGetName(), and Scip::set.

Referenced by parseFactor().

◆ parseFactor()

static SCIP_RETCODE parseFactor ( SCIP scip,
SCIP_Bool  isdenominator,
SCIP_HASHMAP vartoexprvarmap,
const char *  expr,
const char **  newpos,
SCIP_EXPR **  factortree,
SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))  ,
void *  ownercreatedata 
)
static

Parses a factor and builds a product-expression if there is an exponent, otherwise returns the base expression.

Factor -> Base [ "^" "number" | "^(" "number" ")" ]
Parameters
scipSCIP data structure
isdenominatorwhether factor is in the denominator
vartoexprvarmaphashmap to map between scip vars and var expressions
exprexpr that we are parsing
newposbuffer to store the position of expr where we finished reading
factortreebuffer to store the expr parsed by Factor
ownercreatedatadata to pass to ownercreate

Definition at line 315 of file scip_expr.c.

References debugParse, parseBase(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprPow(), SCIPerrorMessage, SCIPreleaseExpr(), and SCIPstrToRealValue().

Referenced by parseTerm().

◆ parseTerm()

static SCIP_RETCODE parseTerm ( SCIP scip,
SCIP_HASHMAP vartoexprvarmap,
const char *  expr,
const char **  newpos,
SCIP_EXPR **  termtree,
SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))  ,
void *  ownercreatedata 
)
static

Parses a term and builds a product-expression, where each factor is a child.

Term -> Factor { ("*" | "/" ) Factor }
Parameters
scipSCIP data structure
vartoexprvarmaphashmap to map between scip vars and var expressions
exprexpr that we are parsing
newposbuffer to store the position of expr where we finished reading
termtreebuffer to store the expr parsed by Term
ownercreatedatadata to pass to ownercreate

Definition at line 439 of file scip_expr.c.

References debugParse, FALSE, parseFactor(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPappendExprChild(), SCIPcreateExprProduct(), SCIPreleaseExpr(), and TRUE.

Referenced by parseExpr().

◆ findEqualExpr()

static SCIP_RETCODE findEqualExpr ( SCIP_SET set,
SCIP_EXPR expr,
SCIP_MULTIHASH key2expr,
SCIP_EXPR **  newexpr 
)
static

returns an equivalent expression for a given expression if possible

it adds the expression to key2expr if the map does not contain the key

Parameters
setglobal SCIP settings
exprexpression to replace
key2exprmapping of hashes to expressions
newexprpointer to store an equivalent expression (NULL if there is none)

Definition at line 655 of file scip_expr.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPexprCompare(), SCIPmultihashInsert(), SCIPmultihashRetrieveNext(), and TRUE.

Referenced by SCIPreplaceCommonSubexpressions().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashCommonSubexprGetKey  )
static

get key of hash element

Definition at line 709 of file scip_expr.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashCommonSubexprEq  )
static

checks if two expressions are structurally the same

Definition at line 716 of file scip_expr.c.

References NULL, SCIPexprCompare(), and COMMONSUBEXPR_HASH_DATA::set.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashCommonSubexprKeyval  )
static

get value of hash element when comparing with another expression

Definition at line 735 of file scip_expr.c.

References COMMONSUBEXPR_HASH_DATA::hashiterator, NULL, SCIPexpriterGetExprUserData(), and SCIP_EXPRITER_USERDATA::uintval.

◆ hashExpr()

static SCIP_RETCODE hashExpr ( SCIP_SET set,
BMS_BUFMEM bufmem,
SCIP_EXPR expr,
SCIP_EXPRITER hashiterator,
int *  nvisitedexprs 
)
static

hashes an expression using an already existing iterator

The iterator must by of type DFS with allowrevisit=FALSE and only the leaveexpr stage enabled. The hashes of all visited expressions will be stored in the iterators expression data.

Parameters
setglobal SCIP settings
bufmembuffer memory
exprexpression to hash
hashiteratoriterator to use for hashing
nvisitedexprscounter to increment by the number of expressions visited, or NULL

Definition at line 755 of file scip_expr.c.

References BMSallocBufferMemoryArray, BMSfreeBufferMemoryArray, BMSreallocBufferMemoryArray, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_EXPRITER_LEAVEEXPR, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrHashExpr(), SCIPexpriterGetExprUserData(), SCIPexpriterGetNext(), SCIPexpriterGetStageDFS(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetCurrentUserData(), SCIPsetCalcMemGrowSize(), and SCIP_EXPRITER_USERDATA::uintval.

Referenced by SCIPhashExpr(), and SCIPreplaceCommonSubexpressions().