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_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)

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

scip	SCIP data structure
vartoexprvarmap	hashmap to map between scip vars and var expressions
expr	expr that we are parsing
newpos	buffer to store the position of expr where we finished reading
exprtree	buffer to store the expr parsed by Expr
ownercreatedata	data to pass to ownercreate

Definition at line 517 of file scip_expr.c.

References debugParse, NULL, parseTerm(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPexprIsValue(), SCIPgetValueExprValue(), SCIPreleaseExpr(), SCIPskipSpace(), 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

scip	SCIP data structure
vartoexprvarmap	hashmap to map between SCIP vars and var expressions
expr	expr that we are parsing
newpos	buffer to store the position of expr where we finished reading
basetree	buffer to store the expr parsed by Base
ownercreatedata	data 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, SCIP_SPACECONTROL, SCIPcreateExprValue(), SCIPcreateExprVar(), SCIPerrorMessage, SCIPexprCapture(), SCIPexprhdlrParseExpr(), SCIPfindExprhdlr(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPparseVarName(), SCIPreleaseExpr(), SCIPskipSpace(), 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

scip	SCIP data structure
isdenominator	whether factor is in the denominator
vartoexprvarmap	hashmap to map between scip vars and var expressions
expr	expr that we are parsing
newpos	buffer to store the position of expr where we finished reading
factortree	buffer to store the expr parsed by Factor
ownercreatedata	data to pass to ownercreate

Definition at line 317 of file scip_expr.c.

References debugParse, parseBase(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPcreateExprPow(), SCIPerrorMessage, SCIPreleaseExpr(), SCIPskipSpace(), 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

scip	SCIP data structure
vartoexprvarmap	hashmap to map between scip vars and var expressions
expr	expr that we are parsing
newpos	buffer to store the position of expr where we finished reading
termtree	buffer to store the expr parsed by Term
ownercreatedata	data to pass to ownercreate

Definition at line 438 of file scip_expr.c.

References debugParse, FALSE, parseFactor(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPappendExprChild(), SCIPcreateExprProduct(), SCIPreleaseExpr(), SCIPskipSpace(), 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

set	global SCIP settings
expr	expression to replace
key2expr	mapping of hashes to expressions
newexpr	pointer to store an equivalent expression (NULL if there is none)

Definition at line 646 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 700 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 707 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 726 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

set	global SCIP settings
bufmem	buffer memory
expr	expression to hash
hashiterator	iterator to use for hashing
nvisitedexprs	counter to increment by the number of expressions visited, or NULL

Definition at line 746 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().

SCIP

Detailed Description

Data Structures

Functions

Parsing methods (internal)

Macro Definition Documentation

◆ debugParse

Function Documentation

◆ SCIP_DECL_EXPR_MAPEXPR()

◆ parseExpr()

◆ parseBase()

◆ parseFactor()

◆ parseTerm()

◆ findEqualExpr()

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ hashExpr()