Scippy

SCIP

Solving Constraint Integer Programs

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 EXPRNODElistPopFirst (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.

◆ EXPRHDLR_DESC

#define EXPRHDLR_DESC   "product expression"

Definition at line 52 of file expr_product.c.

◆ EXPRHDLR_PRECEDENCE

#define EXPRHDLR_PRECEDENCE   50000

Definition at line 53 of file expr_product.c.

◆ EXPRHDLR_HASHKEY

#define EXPRHDLR_HASHKEY   SCIPcalcFibHash(54949.0)

Definition at line 54 of file expr_product.c.

◆ debugSimplify

#define debugSimplify   while( FALSE ) printf

macro to activate/deactivate debugging information of simplify method

Definition at line 63 of file expr_product.c.

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 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
scipSCIP data structure
simplifiedcoefsimplified product should be simplifiedcoef * PI simplifiedfactors
simplifiedfactorsfactors of simplified product
expandalwayswhether to expand products of a sum and several factors in simplify (SP12b)
changedindicates whether some of the simplified factors was changed
simplifiedexprbuffer to store the simplified expression
ownercreatedatadata 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(), and SCIP_DECL_EXPRSIMPLIFY().

◆ insertFirstList()

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

inserts newnode at beginning of list

Parameters
newnodenode to insert
listlist

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
listlist

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
listlist

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
scipSCIP data structure
exprexpression stored at node
newnodepointer 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
scipSCIP data structure
exprsexpressions stored in list
nexprsnumber of expressions
listpointer 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
scipSCIP data structure
nodenode 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
scipSCIP data structure
exprlistlist

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
scipSCIP data structure
exprlistlist containing the children of expr
coefcoef of expr
exprpointer to store the product expression
ownercreatedatadata 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
scipSCIP data structure
factorexpression to be simplified
simplifiedcoefcoefficient of parent product expression
simplifiedfactorpointer to store the resulting expression node/list of nodes
changedpointer 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
scipSCIP data structure
tomergelist to merge
finalchildrenpointer to store the result of merge between tomerge and *finalchildren
unsimplifiedchildrenthe list of children that should go to the product expression; they are unsimplified when seen as children of a simplified product
changedpointer to store if some term actually got simplified
ownercreatedatadata 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
scipSCIP data structure
exprsfactors to be simplified
nexprsnumber of factors
simplifiedcoefbuffer to store coefficient of PI exprs; needs to be initialized
finalchildrenexpr node list to store the simplified factors
changedbuffer to store whether some factor changed
ownercreatedatadata 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
scipSCIP data structure
simplifiedcoefsimplified product should be simplifiedcoef * PI simplifiedfactors
finalchildrenfactors of simplified product
simplifiedexprbuffer to store the simplified expression
ownercreatedatadata 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
scipSCIP data structure
simplifiedcoefsimplified product should be simplifiedcoef * PI simplifiedfactors
finalchildrenfactors of simplified product
simplifiedexprbuffer to store the simplified expression
ownercreatedatadata 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
scipSCIP data structure
simplifiedcoefsimplified product should be simplifiedcoef * PI simplifiedfactors
finalchildrenfactors of simplified product
expandalwayswhether to expand products of a sum and several factors in simplify (SP12b)
simplifiedexprbuffer to store the simplified expression
ownercreatedatadata 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
scipSCIP data structure
simplifiedcoefsimplified product should be simplifiedcoef * prod simplifiedfactors
finalchildrenfactors of simplified product
simplifiedexprbuffer to store the simplified expression
ownercreatedatadata 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
scipSCIP data structure
conshdlrnonlinear constraint handler
nfactorsnumber of factors
boundsbound for each factor
constantfactoranother constant factor
refpointreference point where to estimate, or NULL if called from initestimates
overestimateshould estimator overestimate expr (TRUE) or underestimate (FALSE)
targetvalueno need to compute facet if value in xstar would be worse than target value
coefsarray to store cut coefficients
constantpointer to store cut constant
successpointer 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 exprnode::expr, NULL, SCIP_OKAY, SCIPexprGetData(), SCIPexprSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_EXPRPRINT()

static SCIP_DECL_EXPRPRINT ( printProduct  )
static

◆ SCIP_DECL_EXPRHASH()

static SCIP_DECL_EXPRHASH ( hashProduct  )
static

product hash callback

Definition at line 1627 of file expr_product.c.

References exprnode::expr, 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 exprnode::expr, 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 exprnode::expr, 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 exprnode::expr, 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 exprnode::expr, NULL, SCIP_INVALID, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetEvalValue(), SCIPexprGetNChildren(), SCIPisExprValue(), and SCIPisZero().

◆ SCIP_DECL_EXPRINTEVAL()

static SCIP_DECL_EXPRINTEVAL ( intevalProduct  )
static

◆ 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(), exprnode::expr, 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()

◆ SCIP_DECL_EXPRREVERSEPROP()

static SCIP_DECL_EXPRREVERSEPROP ( reversepropProduct  )
static

◆ SCIP_DECL_EXPRCURVATURE()

static SCIP_DECL_EXPRCURVATURE ( curvatureProduct  )
static

expression curvature detection callback

Definition at line 2121 of file expr_product.c.

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

◆ SCIP_DECL_EXPRMONOTONICITY()

static SCIP_DECL_EXPRMONOTONICITY ( monotonicityProduct  )
static

◆ SCIP_DECL_EXPRINTEGRALITY()

static SCIP_DECL_EXPRINTEGRALITY ( integralityProduct  )
static

expression integrality detection callback

Definition at line 2193 of file expr_product.c.

References EPSISINT, exprnode::expr, 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 exprnode::expr, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPgetCoefExprProduct().