expr_product.c File Reference

Detailed Description

product expression handler

Author

Stefan Vigerske

Benjamin Mueller

Felipe Serrano

Ksenia Bestuzheva

Definition in file expr_product.c.

#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"
#include "symmetry/struct_symmetry.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 expandalways, 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_Bool expandalways, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE	enforceSP12b (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)
static	SCIP_DECL_EXPRGETSYMDATA (getSymDataProduct)
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 51 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 52 of file expr_product.c.

Referenced by SCIPincludeExprhdlrProduct().

EXPRHDLR_PRECEDENCE

#define EXPRHDLR_PRECEDENCE   50000

Definition at line 53 of file expr_product.c.

Referenced by SCIP_DECL_EXPRPRINT(), and SCIPincludeExprhdlrProduct().

EXPRHDLR_HASHKEY

#define EXPRHDLR_HASHKEY   SCIPcalcFibHash(54949.0)

Definition at line 54 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 63 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 93 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 101 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  expandalways, 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
expandalways	whether to expand products of a sum and several factors in simplify (SP12b)
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 1219 of file expr_product.c.

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

Referenced by enforceSP12(), enforceSP12b(), 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 129 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 143 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 163 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 181 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 198 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 225 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 240 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 269 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 312 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 392 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; needs to be initialized
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 723 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(), enforceSP12b(), 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 789 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 833 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_Bool  expandalways, 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
expandalways	whether to expand products of a sum and several factors in simplify (SP12b)
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

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

enforceSP12b()

static SCIP_RETCODE enforceSP12b ( 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 * prod simplifiedfactors
finalchildren	factors of simplified product
simplifiedexpr	buffer to store the simplified expression
ownercreatedata	data to pass to ownercreate

Definition at line 1111 of file expr_product.c.

References buildSimplifiedProduct(), exprnode::expr, exprnode::next, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPappendExprSumExpr(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPisExprSum(), 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 1292 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 1376 of file expr_product.c.

References buildSimplifiedProduct(), debugSimplify, exprnode::expr, exprnode::next, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcaptureExpr(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetData(), 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 1449 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 1499 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 1508 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 1523 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 1540 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 1558 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 1627 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 1651 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]

! [SnippetExprFwdiffProduct]

Definition at line 1679 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]

! [SnippetExprBwfwdiffProduct]

Definition at line 1736 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]

! [SnippetExprBwdiffProduct]

Definition at line 1795 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]

! [SnippetExprIntevalProduct]

Definition at line 1835 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 1883 of file expr_product.c.

References estimateVertexPolyhedralProduct(), EXPRHDLR_NAME, FALSE, SCIP_Interval::inf, MAX, MIN, 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 1980 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]

! [SnippetExprReversepropProduct]

Definition at line 2036 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 2121 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 2143 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 2193 of file expr_product.c.

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

SCIP_DECL_EXPRGETSYMDATA()

static SCIP_DECL_EXPRGETSYMDATA ( getSymDataProduct  )

static

expression callback to get information for symmetry detection

Definition at line 2220 of file expr_product.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPgetCoefExprProduct().