Detailed Description

product expression handler

Author: Stefan Vigerske; Benjamin Mueller; Felipe Serrano; Ksenia Bestuzheva

#include <string.h>
#include "scip/pub_expr.h"
#include "scip/expr_product.h"
#include "scip/expr_sum.h"
#include "scip/expr_pow.h"
#include "scip/expr_value.h"
#include "scip/expr_exp.h"
#include "scip/expr_abs.h"
#include "scip/expr_entropy.h"
#include "scip/cons_nonlinear.h"
#include "scip/pub_misc.h"
#include "scip/nlhdlr_bilinear.h"

Go to the source code of this file.

Data Structures
struct	exprnode

Macros
#define	EXPRHDLR_NAME "prod"

#define	EXPRHDLR_DESC "product expression"

#define	EXPRHDLR_PRECEDENCE 50000

#define	EXPRHDLR_HASHKEY SCIPcalcFibHash(54949.0)

#define	debugSimplify while( FALSE ) printf

Typedefs
typedef struct exprnode	EXPRNODE

Functions
static	SCIP_DECL_VERTEXPOLYFUN (prodfunction)

static SCIP_RETCODE	buildSimplifiedProduct (SCIP scip, SCIP_Real simplifiedcoef, EXPRNODE simplifiedfactors, SCIP_Bool changed, SCIP_EXPR simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static void	insertFirstList (EXPRNODE newnode, EXPRNODE *list)

static EXPRNODE *	listPopFirst (EXPRNODE **list)

static int	listLength (EXPRNODE *list)

static SCIP_RETCODE	createExprNode (SCIP scip, SCIP_EXPR expr, EXPRNODE **newnode)

static SCIP_RETCODE	createExprlistFromExprs (SCIP scip, SCIP_EXPR exprs, int nexprs, EXPRNODE *list)

static SCIP_RETCODE	freeExprNode (SCIP scip, EXPRNODE *node)

static SCIP_RETCODE	freeExprlist (SCIP scip, EXPRNODE *exprlist)

static SCIP_RETCODE	createExprProductFromExprlist (SCIP scip, EXPRNODE exprlist, SCIP_Real coef, SCIP_EXPR *expr, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static SCIP_RETCODE	simplifyFactor (SCIP scip, SCIP_EXPR factor, SCIP_Real simplifiedcoef, EXPRNODE simplifiedfactor, SCIP_Bool changed)

static SCIP_RETCODE	mergeProductExprlist (SCIP scip, EXPRNODE tomerge, EXPRNODE finalchildren, EXPRNODE unsimplifiedchildren, SCIP_Bool changed, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static SCIP_RETCODE	simplifyMultiplyChildren (SCIP scip, SCIP_EXPR exprs, int nexprs, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_Bool changed, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void ownercreatedata)

static SCIP_RETCODE	enforceSP10 (SCIP scip, SCIP_Real simplifiedcoef, EXPRNODE finalchildren, SCIP_EXPR *simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static SCIP_RETCODE	enforceSP11 (SCIP scip, SCIP_Real simplifiedcoef, EXPRNODE finalchildren, SCIP_EXPR *simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static SCIP_RETCODE	enforceSP12 (SCIP scip, SCIP_Real simplifiedcoef, EXPRNODE finalchildren, SCIP_EXPR *simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

static SCIP_RETCODE	estimateVertexPolyhedralProduct (SCIP scip, SCIP_CONSHDLR conshdlr, int nfactors, SCIP_INTERVAL bounds, SCIP_Real constantfactor, SCIP_Real refpoint, SCIP_Bool overestimate, SCIP_Real targetvalue, SCIP_Real coefs, SCIP_Real constant, SCIP_Bool *success)

static	SCIP_DECL_EXPRSIMPLIFY (simplifyProduct)

static	SCIP_DECL_EXPRCOMPARE (compareProduct)

static	SCIP_DECL_EXPRCOPYHDLR (copyhdlrProduct)

static	SCIP_DECL_EXPRFREEHDLR (freehdlrProduct)

static	SCIP_DECL_EXPRCOPYDATA (copydataProduct)

static	SCIP_DECL_EXPRFREEDATA (freedataProduct)

static	SCIP_DECL_EXPRPRINT (printProduct)

static	SCIP_DECL_EXPRHASH (hashProduct)

static	SCIP_DECL_EXPREVAL (evalProduct)

static	SCIP_DECL_EXPRFWDIFF (fwdiffProduct)

static	SCIP_DECL_EXPRBWFWDIFF (bwfwdiffProduct)

static	SCIP_DECL_EXPRBWDIFF (bwdiffProduct)

static	SCIP_DECL_EXPRINTEVAL (intevalProduct)

static	SCIP_DECL_EXPRESTIMATE (estimateProduct)

static	SCIP_DECL_EXPRINITESTIMATES (initestimatesProduct)

static	SCIP_DECL_EXPRREVERSEPROP (reversepropProduct)

static	SCIP_DECL_EXPRCURVATURE (curvatureProduct)

static	SCIP_DECL_EXPRMONOTONICITY (monotonicityProduct)

static	SCIP_DECL_EXPRINTEGRALITY (integralityProduct)

SCIP_RETCODE	SCIPincludeExprhdlrProduct (SCIP *scip)

SCIP_RETCODE	SCIPcreateExprProduct (SCIP scip, SCIP_EXPR expr, int nchildren, SCIP_EXPR children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((ownercreate)), void *ownercreatedata)

SCIP_Real	SCIPgetCoefExprProduct (SCIP_EXPR *expr)

Macro Definition Documentation

◆ EXPRHDLR_NAME

#define EXPRHDLR_NAME "prod"

Definition at line 41 of file expr_product.c.

Referenced by SCIP_DECL_EXPRESTIMATE(), SCIP_DECL_EXPRINITESTIMATES(), and SCIPincludeExprhdlrProduct().

◆ EXPRHDLR_DESC

#define EXPRHDLR_DESC "product expression"

Definition at line 42 of file expr_product.c.

Referenced by SCIPincludeExprhdlrProduct().

◆ EXPRHDLR_PRECEDENCE

#define EXPRHDLR_PRECEDENCE 50000

Definition at line 43 of file expr_product.c.

Referenced by SCIP_DECL_EXPRPRINT(), and SCIPincludeExprhdlrProduct().

◆ EXPRHDLR_HASHKEY

#define EXPRHDLR_HASHKEY SCIPcalcFibHash(54949.0)

Definition at line 44 of file expr_product.c.

Referenced by SCIP_DECL_EXPRHASH().

◆ debugSimplify

#define debugSimplify while( FALSE ) printf

macro to activate/deactivate debugging information of simplify method

Definition at line 53 of file expr_product.c.

Referenced by buildSimplifiedProduct(), createExprlistFromExprs(), enforceSP12(), SCIP_DECL_EXPRSIMPLIFY(), simplifyFactor(), and simplifyMultiplyChildren().

Typedef Documentation

◆ EXPRNODE

typedef struct exprnode EXPRNODE

Definition at line 81 of file expr_product.c.

Function Documentation

◆ SCIP_DECL_VERTEXPOLYFUN()

static SCIP_DECL_VERTEXPOLYFUN ( prodfunction )

static

evaluation callback for (vertex-polyhedral) functions used as input for facet computation of its envelopes

Definition at line 89 of file expr_product.c.

References buildSimplifiedProduct(), SCIP_Bool, SCIP_DECL_EXPR_OWNERCREATE, and SCIP_Real.

◆ buildSimplifiedProduct()

static SCIP_RETCODE buildSimplifiedProduct	(	SCIP *	scip,
		SCIP_Real	simplifiedcoef,
		EXPRNODE **	simplifiedfactors,
		SCIP_Bool	changed,
		SCIP_EXPR **	simplifiedexpr,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

builds a simplified product from simplifiedfactors

Note: this function also releases simplifiedfactors

Parameters

scip	SCIP data structure
simplifiedcoef	simplified product should be simplifiedcoef * PI simplifiedfactors
simplifiedfactors	factors of simplified product
changed	indicates whether some of the simplified factors was changed
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

Definition at line 1087 of file expr_product.c.

References createExprProductFromExprlist(), debugSimplify, enforceSP10(), enforceSP11(), enforceSP12(), freeExprlist(), listLength(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateExprSum(), and SCIPreleaseExpr().

Referenced by enforceSP12(), SCIP_DECL_EXPRSIMPLIFY(), and SCIP_DECL_VERTEXPOLYFUN().

◆ insertFirstList()

static void insertFirstList	(	EXPRNODE *	newnode,
		EXPRNODE **	list
	)

static

inserts newnode at beginning of list

Parameters

newnode	node to insert
list	list

Definition at line 116 of file expr_product.c.

References exprnode::next, and NULL.

Referenced by createExprlistFromExprs(), and mergeProductExprlist().

◆ listPopFirst()

static EXPRNODE* listPopFirst ( EXPRNODE ** list )

static

removes first element of list and returns it

Parameters

list list

Definition at line 130 of file expr_product.c.

References exprnode::next, and NULL.

Referenced by mergeProductExprlist(), and simplifyMultiplyChildren().

◆ listLength()

static int listLength ( EXPRNODE * list )

static

returns length of list

Parameters

list list

Definition at line 150 of file expr_product.c.

References exprnode::next, and NULL.

Referenced by buildSimplifiedProduct(), and createExprProductFromExprlist().

◆ createExprNode()

static SCIP_RETCODE createExprNode	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		EXPRNODE **	newnode
	)

static

creates expression node and captures expression

Parameters

scip	SCIP data structure
expr	expression stored at node
newnode	pointer to store node

Definition at line 168 of file expr_product.c.

References exprnode::expr, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), and SCIPcaptureExpr().

Referenced by createExprlistFromExprs(), and simplifyFactor().

◆ createExprlistFromExprs()

static SCIP_RETCODE createExprlistFromExprs	(	SCIP *	scip,
		SCIP_EXPR **	exprs,
		int	nexprs,
		EXPRNODE **	list
	)

static

creates expression list from expressions

Parameters

scip	SCIP data structure
exprs	expressions stored in list
nexprs	number of expressions
list	pointer to store list

Definition at line 185 of file expr_product.c.

References createExprNode(), debugSimplify, insertFirstList(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by simplifyFactor(), and simplifyMultiplyChildren().

◆ freeExprNode()

static SCIP_RETCODE freeExprNode	(	SCIP *	scip,
		EXPRNODE **	node
	)

static

frees expression node and releases expressions

Parameters

scip	SCIP data structure
node	node to be freed

Definition at line 212 of file expr_product.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPreleaseExpr().

Referenced by freeExprlist(), and mergeProductExprlist().

◆ freeExprlist()

static SCIP_RETCODE freeExprlist	(	SCIP *	scip,
		EXPRNODE **	exprlist
	)

static

frees an expression list

Parameters

scip	SCIP data structure
exprlist	list

Definition at line 227 of file expr_product.c.

References freeExprNode(), exprnode::next, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by buildSimplifiedProduct(), and simplifyMultiplyChildren().

◆ createExprProductFromExprlist()

static SCIP_RETCODE createExprProductFromExprlist	(	SCIP *	scip,
		EXPRNODE *	exprlist,
		SCIP_Real	coef,
		SCIP_EXPR **	expr,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

creates a product expression with the elements of exprlist as its children

Parameters

scip	SCIP data structure
exprlist	list containing the children of expr
coef	coef of expr
expr	pointer to store the product expression
ownercreatedata	data to pass to ownercreate

Definition at line 256 of file expr_product.c.

References exprnode::expr, listLength(), exprnode::next, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateExprProduct(), and SCIPfreeBufferArray.

Referenced by buildSimplifiedProduct().

◆ simplifyFactor()

static SCIP_RETCODE simplifyFactor	(	SCIP *	scip,
		SCIP_EXPR *	factor,
		SCIP_Real *	simplifiedcoef,
		EXPRNODE **	simplifiedfactor,
		SCIP_Bool *	changed
	)

static

simplifies a factor of a product expression: base, so that it is a valid children of a simplified product expr

Note: In contrast to other simplify methods, this does not return a simplified expression. Instead, the method is intended to be called only when simplifying a product expression. Since in general, base is not a simplified child of a product expression, this method returns a list of expressions L, such that (prod L) = baset and each expression in L is a valid child of a simplified product expression.

Parameters

scip	SCIP data structure
factor	expression to be simplified
simplifiedcoef	coefficient of parent product expression
simplifiedfactor	pointer to store the resulting expression node/list of nodes
changed	pointer to store if some term actually got simplified

Definition at line 299 of file expr_product.c.

References createExprlistFromExprs(), createExprNode(), debugSimplify, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetValueExprValue(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprValue(), and TRUE.

Referenced by simplifyMultiplyChildren().

◆ mergeProductExprlist()

static SCIP_RETCODE mergeProductExprlist	(	SCIP *	scip,
		EXPRNODE *	tomerge,
		EXPRNODE **	finalchildren,
		EXPRNODE **	unsimplifiedchildren,
		SCIP_Bool *	changed,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

merges tomerge into finalchildren

Both, tomerge and finalchildren contain expressions that could be the children of a simplified product (except for SP8 and SP10 which are enforced later). However, the concatenation of both lists will not in general yield a simplified product expression, because SP4, SP5 and SP14 could be violated. So the purpose of this method is to enforce SP4, SP5 and SP14. In the process of enforcing SP4, it could happen that SP2 is violated. Since enforcing SP2 could generate further violations, we remove the affected children from finalchildren and include them in unsimplifiedchildren for further processing.

Note: if tomerge has more than one element, then they are the children of a simplified product expression

Parameters

scip	SCIP data structure
tomerge	list to merge
finalchildren	pointer to store the result of merge between tomerge and *finalchildren
unsimplifiedchildren	the list of children that should go to the product expression; they are unsimplified when seen as children of a simplified product
changed	pointer to store if some term actually got simplified
ownercreatedata	data to pass to ownercreate

Definition at line 370 of file expr_product.c.

References EPSISINT, exprnode::expr, FALSE, freeExprNode(), insertFirstList(), listPopFirst(), exprnode::next, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPappendExprSumExpr(), SCIPcompareExpr(), SCIPcreateExprAbs(), SCIPcreateExprExp(), SCIPcreateExprPow(), SCIPcreateExprSignpower(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPgetExponentExprPow(), SCIPisExprExp(), SCIPisExprPower(), SCIPisExprSignpower(), SCIPisExprValue(), SCIPreleaseExpr(), and TRUE.

Referenced by simplifyMultiplyChildren().

◆ simplifyMultiplyChildren()

static SCIP_RETCODE simplifyMultiplyChildren	(	SCIP *	scip,
		SCIP_EXPR **	exprs,
		int	nexprs,
		SCIP_Real *	simplifiedcoef,
		EXPRNODE **	finalchildren,
		SCIP_Bool *	changed,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

simplifies the given (simplified) exprs so that they can be factors of a simplified product

in particular, it will sort and multiply factors whose product leads to new expressions

Parameters

scip	SCIP data structure
exprs	factors to be simplified
nexprs	number of factors
simplifiedcoef	buffer to store coefficient of PI exprs; do not initialize
finalchildren	expr node list to store the simplified factors
changed	buffer to store whether some factor changed
ownercreatedata	data to pass to ownercreate

Definition at line 701 of file expr_product.c.

References createExprlistFromExprs(), debugSimplify, exprnode::expr, FALSE, freeExprlist(), listPopFirst(), mergeProductExprlist(), NULL, SCIP_CALL, SCIP_OKAY, SCIPinfoMessage(), SCIPprintExpr(), simplifyFactor(), and TRUE.

Referenced by enforceSP12(), and SCIP_DECL_EXPRSIMPLIFY().

◆ enforceSP10()

static SCIP_RETCODE enforceSP10	(	SCIP *	scip,
		SCIP_Real	simplifiedcoef,
		EXPRNODE *	finalchildren,
		SCIP_EXPR **	simplifiedexpr,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

Parameters

scip	SCIP data structure
simplifiedcoef	simplified product should be simplifiedcoef * PI simplifiedfactors
finalchildren	factors of simplified product
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

Definition at line 767 of file expr_product.c.

References exprnode::expr, exprnode::next, NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPcreateExprSum(), SCIPcreateExprValue(), and SCIPreleaseExpr().

Referenced by buildSimplifiedProduct().

◆ enforceSP11()

static SCIP_RETCODE enforceSP11	(	SCIP *	scip,
		SCIP_Real	simplifiedcoef,
		EXPRNODE *	finalchildren,
		SCIP_EXPR **	simplifiedexpr,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

checks if it is entropy expression

Parameters

scip	SCIP data structure
simplifiedcoef	simplified product should be simplifiedcoef * PI simplifiedfactors
finalchildren	factors of simplified product
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

Definition at line 811 of file expr_product.c.

References exprnode::expr, exprnode::next, NULL, SCIP_CALL, SCIP_OKAY, SCIPcompareExpr(), SCIPcreateExprEntropy(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), and SCIPreleaseExpr().

Referenced by buildSimplifiedProduct().

◆ enforceSP12()

static SCIP_RETCODE enforceSP12	(	SCIP *	scip,
		SCIP_Real	simplifiedcoef,
		EXPRNODE *	finalchildren,
		SCIP_EXPR **	simplifiedexpr,
		SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))	,
		void *	ownercreatedata
	)

static

Parameters

scip	SCIP data structure
simplifiedcoef	simplified product should be simplifiedcoef * PI simplifiedfactors
finalchildren	factors of simplified product
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

Definition at line 872 of file expr_product.c.

References buildSimplifiedProduct(), debugSimplify, exprnode::expr, exprnode::next, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexprGetNUses(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPinfoMessage(), SCIPisExprSum(), SCIPprintExpr(), SCIPreleaseExpr(), simplifyMultiplyChildren(), and TRUE.

Referenced by buildSimplifiedProduct().

◆ estimateVertexPolyhedralProduct()

static SCIP_RETCODE estimateVertexPolyhedralProduct	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		int	nfactors,
		SCIP_INTERVAL *	bounds,
		SCIP_Real	constantfactor,
		SCIP_Real *	refpoint,
		SCIP_Bool	overestimate,
		SCIP_Real	targetvalue,
		SCIP_Real *	coefs,
		SCIP_Real *	constant,
		SCIP_Bool *	success
	)

static

computes an estimator for a product as a vertex polyhedral function

Since the product is multilinear, its convex and concave envelopes are piecewise linear.

Parameters

scip	SCIP data structure
conshdlr	nonlinear constraint handler
nfactors	number of factors
bounds	bound for each factor
constantfactor	another constant factor
refpoint	reference point where to estimate, or NULL if called from initestimates
overestimate	should estimator overestimate expr (TRUE) or underestimate (FALSE)
targetvalue	no need to compute facet if value in xstar would be worse than target value
coefs	array to store cut coefficients
constant	pointer to store cut constant
success	pointer to store whether estimation was successful

Definition at line 1152 of file expr_product.c.

References FALSE, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_MAXVERTEXPOLYDIM, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcomputeFacetVertexPolyhedralNonlinear(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPintervalIsEmpty(), SCIPisInfinity(), SCIPisRelEQ(), and SCIP_Interval::sup.

Referenced by SCIP_DECL_EXPRESTIMATE(), and SCIP_DECL_EXPRINITESTIMATES().

◆ SCIP_DECL_EXPRSIMPLIFY()

static SCIP_DECL_EXPRSIMPLIFY ( simplifyProduct )

static

simplifies a product expression

Summary: we first build a list of expressions (called finalchildren) which will be the children of the simplified product and then we process this list in order to enforce SP8 and SP10.

Description: In order to build finalchildren, we first build a list of unsimplified children (called unsimplifiedchildren) with the children of the product. Each node of the list is manipulated (see simplifyFactor) in order to satisfy SP2 and SP7 as follows:

SP7: if the node's expression is a value, multiply the value to the products's coef
SP2: if the node's expression is a product, then build a list with the child's children

Then, we merge the built list (or the simplified node) into finalchildren. While merging, nodes from finalchildren can go back to unsimplifiedchildren for further processing (see mergeProductExprlist() for more details). After building finalchildren, we create the simplified product out of it, taking care that SP8 and SP10 are satisfied

Definition at line 1236 of file expr_product.c.

References buildSimplifiedProduct(), debugSimplify, exprnode::expr, exprnode::next, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcaptureExpr(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPinfoMessage(), SCIPprintExpr(), and simplifyMultiplyChildren().

◆ SCIP_DECL_EXPRCOMPARE()

static SCIP_DECL_EXPRCOMPARE ( compareProduct )

static

compare two product expressions

The order of two product expressions, u and v, is a lexicographical order on the factors.

Starting from the last, we find the first child where they differ, say, the i-th. Then u < v <=> u_i < v_i. If there is no such children and they have different number of children, then u < v <=> nchildren(u) < nchildren(v). If all children are the same and they have the same number of children, then u < v <=> coeff(u) < coeff(v). Otherwise, they are the same.

Note: we are assuming expression are simplified, so within u, we have u_1 < u_2, etc.

Example: y * z < x * y * z

Definition at line 1309 of file expr_product.c.

References SCIPcompareExpr(), SCIPexprGetChildren(), SCIPexprGetNChildren(), and SCIPgetCoefExprProduct().

◆ SCIP_DECL_EXPRCOPYHDLR()

static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrProduct )

static

expression handler copy callback

Definition at line 1359 of file expr_product.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrProduct().

◆ SCIP_DECL_EXPRFREEHDLR()

static SCIP_DECL_EXPRFREEHDLR ( freehdlrProduct )

static

expression handler free callback

Definition at line 1368 of file expr_product.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

◆ SCIP_DECL_EXPRCOPYDATA()

static SCIP_DECL_EXPRCOPYDATA ( copydataProduct )

static

expression data copy callback

Definition at line 1383 of file expr_product.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPduplicateBlockMemory, and SCIPexprGetData().

◆ SCIP_DECL_EXPRFREEDATA()

static SCIP_DECL_EXPRFREEDATA ( freedataProduct )

static

expression data free callback

Definition at line 1400 of file expr_product.c.

References NULL, SCIP_OKAY, SCIPexprGetData(), SCIPexprSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_EXPRPRINT()

static SCIP_DECL_EXPRPRINT ( printProduct )

static

expression print callback

Definition at line 1418 of file expr_product.c.

References EXPRHDLR_PRECEDENCE, NULL, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_EXPRITER_VISITEDCHILD, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIPABORT, SCIPexprGetData(), and SCIPinfoMessage().

◆ SCIP_DECL_EXPRHASH()

static SCIP_DECL_EXPRHASH ( hashProduct )

static

product hash callback

Definition at line 1487 of file expr_product.c.

References EXPRHDLR_HASHKEY, NULL, SCIP_OKAY, SCIPcalcFibHash(), SCIPexprGetData(), and SCIPexprGetNChildren().

◆ SCIP_DECL_EXPREVAL()

static SCIP_DECL_EXPREVAL ( evalProduct )

static

expression point evaluation callback

Definition at line 1511 of file expr_product.c.

References NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetEvalValue(), and SCIPexprGetNChildren().

◆ SCIP_DECL_EXPRFWDIFF()

static SCIP_DECL_EXPRFWDIFF ( fwdiffProduct )

static

derivative evaluation callback computing <gradient, children.dot>

If expr is \(\prod_i x_i\), then computes \(\sum_j \prod_{i\neq j} x_i x^{\text{dot}}_j\).

! [SnippetExprFwdiffProduct]

Definition at line 1539 of file expr_product.c.

References NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetDot(), SCIPexprGetEvalValue(), and SCIPexprGetNChildren().

◆ SCIP_DECL_EXPRBWFWDIFF()

static SCIP_DECL_EXPRBWFWDIFF ( bwfwdiffProduct )

static

expression backward forward derivative evaluation callback

Computes \(\frac{\partial}{\partial \text{childidx}} ( \langle \text{gradient}, \text{children.dot}\rangle )\).

If expr is \(\prod_i x_i\), and childidx is \(k\) then computes \(\partial_k \sum_j \prod_{i \neq j} x_i x^{\text{dot}}_j = \sum_{j \neq k} \prod_{i \neq j, k} x_i x^{\text{dot}}_j\)

! [SnippetExprBwfwdiffProduct]

Definition at line 1596 of file expr_product.c.

References NULL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetDot(), SCIPexprGetEvalValue(), SCIPexprGetNChildren(), and SCIPisExprValue().

◆ SCIP_DECL_EXPRBWDIFF()

static SCIP_DECL_EXPRBWDIFF ( bwdiffProduct )

static

expression derivative evaluation callback

! [SnippetExprBwdiffProduct]

Definition at line 1655 of file expr_product.c.

References NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetEvalValue(), SCIPexprGetNChildren(), SCIPisExprValue(), and SCIPisZero().

◆ SCIP_DECL_EXPRINTEVAL()

static SCIP_DECL_EXPRINTEVAL ( intevalProduct )

static

expression interval evaluation callback

! [SnippetExprIntevalProduct]

Definition at line 1695 of file expr_product.c.

References SCIP_Interval::inf, NULL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetNChildren(), SCIPintervalIsEmpty(), SCIPintervalMul(), SCIPintervalSet(), SCIPintervalSetEmpty(), and SCIP_Interval::sup.

◆ SCIP_DECL_EXPRESTIMATE()

static SCIP_DECL_EXPRESTIMATE ( estimateProduct )

static

estimates a multilinear function of the form \( f(x) := a \prod_{i = 1}^n x_i \)

\( x_i \) are the auxiliary variables of the children. If !overestimate, then we look for an affine underestimator of \( f(x) \) which has a value above targetvalue at \( x^* \), i.e., \( g(x) := \alpha^T x + \beta \le f(x)\) for all \( x \) in the domain, such that \( \alpha x^* + \beta > \text{targetvalue}\).

Since \( f(x) \) is componentwise linear, its convex envelope is piecewise linear and its value can be computed by finding the largest affine underestimator. This is done either explicitly (if n=2) or by solving an LP, see SCIPcomputeFacetVertexPolyhedralNonlinear().

Definition at line 1743 of file expr_product.c.

References estimateVertexPolyhedralProduct(), EXPRHDLR_NAME, FALSE, SCIP_Interval::inf, MAX, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPaddBilinMcCormick(), SCIPdebugMsg, SCIPdismantleExpr(), SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetData(), SCIPexprhdlrGetName(), SCIPintervalIsEmpty(), SCIPisInfinity(), SCIP_Interval::sup, and TRUE.

◆ SCIP_DECL_EXPRINITESTIMATES()

static SCIP_DECL_EXPRINITESTIMATES ( initestimatesProduct )

static

initial estimators callback

Definition at line 1840 of file expr_product.c.

References estimateVertexPolyhedralProduct(), EXPRHDLR_NAME, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddBilinMcCormick(), SCIPdebugMsg, SCIPexprGetData(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetData(), SCIPexprhdlrGetName(), SCIPinfinity(), SCIP_Interval::sup, and TRUE.

◆ SCIP_DECL_EXPRREVERSEPROP()

static SCIP_DECL_EXPRREVERSEPROP ( reversepropProduct )

static

expression reverse propagation callback

! [SnippetExprReversepropProduct]

Definition at line 1896 of file expr_product.c.

References FALSE, SCIP_Interval::inf, NULL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPdebugMsg, SCIPexprGetData(), SCIPexprGetNChildren(), SCIPintervalIntersect(), SCIPintervalIsEmpty(), SCIPintervalIsEntire(), SCIPintervalMul(), SCIPintervalSet(), SCIPintervalSolveUnivariateQuadExpression(), SCIP_Interval::sup, and TRUE.

◆ SCIP_DECL_EXPRCURVATURE()

static SCIP_DECL_EXPRCURVATURE ( curvatureProduct )

static

expression curvature detection callback

Definition at line 1981 of file expr_product.c.

References FALSE, NULL, SCIP_OKAY, SCIPexprcurvMultiply(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), and TRUE.

◆ SCIP_DECL_EXPRMONOTONICITY()

static SCIP_DECL_EXPRMONOTONICITY ( monotonicityProduct )

static

expression monotonicity detection callback

Definition at line 2003 of file expr_product.c.

References NULL, SCIP_CALL, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_MONOTONE_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPevalExprActivity(), SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPintervalGetInf(), and SCIPintervalGetSup().

◆ SCIP_DECL_EXPRINTEGRALITY()

static SCIP_DECL_EXPRINTEGRALITY ( integralityProduct )

static

expression integrality detection callback

Definition at line 2053 of file expr_product.c.

References EPSISINT, NULL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetNChildren(), and SCIPexprIsIntegral().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ EXPRHDLR_NAME

◆ EXPRHDLR_DESC

◆ EXPRHDLR_PRECEDENCE

◆ EXPRHDLR_HASHKEY

◆ debugSimplify

Typedef Documentation

◆ EXPRNODE

Function Documentation

◆ SCIP_DECL_VERTEXPOLYFUN()

◆ buildSimplifiedProduct()

◆ insertFirstList()

◆ listPopFirst()

◆ listLength()

◆ createExprNode()

◆ createExprlistFromExprs()

◆ freeExprNode()

◆ freeExprlist()

◆ createExprProductFromExprlist()

◆ simplifyFactor()

◆ mergeProductExprlist()

◆ simplifyMultiplyChildren()

◆ enforceSP10()

◆ enforceSP11()

◆ enforceSP12()

◆ estimateVertexPolyhedralProduct()

◆ SCIP_DECL_EXPRSIMPLIFY()

◆ SCIP_DECL_EXPRCOMPARE()

◆ SCIP_DECL_EXPRCOPYHDLR()

◆ SCIP_DECL_EXPRFREEHDLR()

◆ SCIP_DECL_EXPRCOPYDATA()

◆ SCIP_DECL_EXPRFREEDATA()

◆ SCIP_DECL_EXPRPRINT()

◆ SCIP_DECL_EXPRHASH()

◆ SCIP_DECL_EXPREVAL()

◆ SCIP_DECL_EXPRFWDIFF()

◆ SCIP_DECL_EXPRBWFWDIFF()

◆ SCIP_DECL_EXPRBWDIFF()

◆ SCIP_DECL_EXPRINTEVAL()

◆ SCIP_DECL_EXPRESTIMATE()

◆ SCIP_DECL_EXPRINITESTIMATES()

◆ SCIP_DECL_EXPRREVERSEPROP()

◆ SCIP_DECL_EXPRCURVATURE()

◆ SCIP_DECL_EXPRMONOTONICITY()

◆ SCIP_DECL_EXPRINTEGRALITY()