expr_sum.c File Reference

Detailed Description

sum expression handler

Author

Stefan Vigerske

Benjamin Mueller

Felipe Serrano

Definition in file expr_sum.c.

#include <string.h>
#include <stddef.h>
#include "scip/expr_sum.h"
#include "scip/expr_value.h"
#include "scip/expr_product.h"
#include "scip/expr_exp.h"
#include "scip/expr_pow.h"
#include "symmetry/struct_symmetry.h"

Go to the source code of this file.

Data Structures
struct	SORTEXPRDATA

Macros
#define	EXPRHDLR_NAME   "sum"
#define	EXPRHDLR_DESC   "summation with coefficients and a constant"
#define	EXPRHDLR_PRECEDENCE   40000
#define	EXPRHDLR_HASHKEY   SCIPcalcFibHash(47161.0)
#define	debugSimplify   while( FALSE ) printf

Functions
static SCIP_RETCODE	createData (SCIP *scip, SCIP_EXPRDATA **exprdata, int ncoefficients, SCIP_Real *coefficients, SCIP_Real constant)
static SCIP_RETCODE	simplifyTerm (SCIP *scip, SCIP_EXPR *duplicate, int idx, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static	SCIP_DECL_SORTINDCOMP (sortExprComp)
static	SCIP_DECL_EXPRSIMPLIFY (simplifySum)
static	SCIP_DECL_EXPRGETSYMDATA (getSymDataSum)
static	SCIP_DECL_EXPRCOMPARE (compareSum)
static	SCIP_DECL_EXPRCOPYHDLR (copyhdlrSum)
static	SCIP_DECL_EXPRCOPYDATA (copydataSum)
static	SCIP_DECL_EXPRFREEDATA (freedataSum)
static	SCIP_DECL_EXPRPRINT (printSum)
static	SCIP_DECL_EXPREVAL (evalSum)
static	SCIP_DECL_EXPRFWDIFF (fwdiffSum)
static	SCIP_DECL_EXPRBWDIFF (bwdiffSum)
static	SCIP_DECL_EXPRBWFWDIFF (bwfwdiffSum)
static	SCIP_DECL_EXPRINTEVAL (intevalSum)
static	SCIP_DECL_EXPRINITESTIMATES (initEstimatesSum)
static	SCIP_DECL_EXPRESTIMATE (estimateSum)
static	SCIP_DECL_EXPRREVERSEPROP (reversepropSum)
static	SCIP_DECL_EXPRHASH (hashSum)
static	SCIP_DECL_EXPRCURVATURE (curvatureSum)
static	SCIP_DECL_EXPRMONOTONICITY (monotonicitySum)
static	SCIP_DECL_EXPRINTEGRALITY (integralitySum)
SCIP_RETCODE	SCIPincludeExprhdlrSum (SCIP *scip)
SCIP_RETCODE	SCIPcreateExprSum (SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefficients, SCIP_Real constant, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
void	SCIPsetConstantExprSum (SCIP_EXPR *expr, SCIP_Real constant)
SCIP_RETCODE	SCIPappendExprSumExpr (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child, SCIP_Real childcoef)
void	SCIPmultiplyByConstantExprSum (SCIP_EXPR *expr, SCIP_Real constant)
SCIP_RETCODE	SCIPmultiplyBySumExprSum (SCIP *scip, SCIP_EXPR **product, SCIP_EXPR *factor1, SCIP_EXPR *factor2, SCIP_Bool simplify, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_RETCODE	SCIPpowerExprSum (SCIP *scip, SCIP_EXPR **result, SCIP_EXPR *base, int exponent, SCIP_Bool simplify, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
SCIP_Real *	SCIPgetCoefsExprSum (SCIP_EXPR *expr)
SCIP_Real	SCIPgetConstantExprSum (SCIP_EXPR *expr)

Macro Definition Documentation

EXPRHDLR_NAME

#define EXPRHDLR_NAME   "sum"

Definition at line 45 of file expr_sum.c.

EXPRHDLR_DESC

#define EXPRHDLR_DESC   "summation with coefficients and a constant"

Definition at line 46 of file expr_sum.c.

EXPRHDLR_PRECEDENCE

#define EXPRHDLR_PRECEDENCE   40000

Definition at line 47 of file expr_sum.c.

EXPRHDLR_HASHKEY

#define EXPRHDLR_HASHKEY   SCIPcalcFibHash(47161.0)

Definition at line 48 of file expr_sum.c.

debugSimplify

#define debugSimplify   while( FALSE ) printf

macro to activate/deactivate debugging information of simplify method

Definition at line 55 of file expr_sum.c.

Function Documentation

createData()

static SCIP_RETCODE createData ( SCIP *  scip, SCIP_EXPRDATA **  exprdata, int  ncoefficients, SCIP_Real *  coefficients, SCIP_Real  constant  )

static

creates expression data

Parameters

scip	SCIP data structure
exprdata	pointer where to store expression data
ncoefficients	number of coefficients (i.e., number of children)
coefficients	array with coefficients for all children (or NULL if all 1.0)
constant	constant term of sum

Definition at line 76 of file expr_sum.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, and SCIPduplicateBlockMemoryArray.

Referenced by SCIP_DECL_EXPRCOPYDATA(), and SCIPcreateExprSum().

simplifyTerm()

static SCIP_RETCODE simplifyTerm ( SCIP *  scip, SCIP_EXPR *  duplicate, int  idx, SCIP_Bool *  changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate))  , void *  ownercreatedata  )

static

simplifies the idx-th child of the sum expression duplicate in order for it to be able to be a child of a simplified sum

for example, this means that the idx-th child cannot be itself a sum if it is, we have to flatten it, i.e., take all its children and make them children of duplicate

Parameters

scip	SCIP data structure
duplicate	expression to be simplified
idx	idx of children to be simplified
changed	pointer to store if some term actually got simplified
ownercreatedata	data to pass to ownercreate

Definition at line 114 of file expr_sum.c.

References NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPappendExprChild(), SCIPappendExprSumExpr(), SCIPcreateExprExp(), SCIPcreateExprProduct(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetValueExprValue(), SCIPisExprExp(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprValue(), SCIPreleaseExpr(), SCIPreplaceExprChild(), SCIPsetConstantExprSum(), simplifyTerm(), and TRUE.

Referenced by SCIP_DECL_EXPRSIMPLIFY(), and simplifyTerm().

SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sortExprComp  )

static

Definition at line 346 of file expr_sum.c.

References SORTEXPRDATA::exprs, SORTEXPRDATA::scip, and SCIPcompareExpr().

SCIP_DECL_EXPRSIMPLIFY()

static SCIP_DECL_EXPRSIMPLIFY ( simplifySum  )

static

simplifies a sum expression

goes through each child and simplifies it; then sorts the simplified children; then sum the children that are equal; finally creates a sum expression with all the children that do not have a 0 coefficient and post-process so that SS6 and SS7 are satisfied

Definition at line 364 of file expr_sum.c.

References debugSimplify, SORTEXPRDATA::exprs, FALSE, NULL, REALABS, SORTEXPRDATA::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcaptureExpr(), SCIPcompareExpr(), SCIPcreateExprSum(), SCIPcreateExprValue(), SCIPduplicateExpr(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPfreeBufferArrayNull, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExprhdlrSum(), SCIPisEQ(), SCIPreleaseExpr(), SCIPsortInd(), simplifyTerm(), and TRUE.

SCIP_DECL_EXPRGETSYMDATA()

static SCIP_DECL_EXPRGETSYMDATA ( getSymDataSum  )

static

expression callback to get information for symmetry detection

Definition at line 542 of file expr_sum.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPexprGetChildren(), and SCIPexprGetData().

SCIP_DECL_EXPRCOMPARE()

static SCIP_DECL_EXPRCOMPARE ( compareSum  )

static

compares two sum expressions

The order of two sum expressions is a lexicographical order on the terms.

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 are no such children and they have different number of children, then u < v <=> nchildren(u) < nchildren(v). If there are no such children and they have the same number of children, then u < v <=> const(u) < const(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, 2*x + 3*y < 3*x + 3*y

Definition at line 587 of file expr_sum.c.

References SCIP_Real, SCIPcompareExpr(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), and SCIPgetConstantExprSum().

SCIP_DECL_EXPRCOPYHDLR()

static SCIP_DECL_EXPRCOPYHDLR ( copyhdlrSum  )

static

expression handler copy callback

Definition at line 654 of file expr_sum.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeExprhdlrSum().

SCIP_DECL_EXPRCOPYDATA()

static SCIP_DECL_EXPRCOPYDATA ( copydataSum  )

static

expression data copy callback

Definition at line 663 of file expr_sum.c.

References createData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPexprGetData(), and SCIPexprGetNChildren().

SCIP_DECL_EXPRFREEDATA()

static SCIP_DECL_EXPRFREEDATA ( freedataSum  )

static

expression data free callback

Definition at line 681 of file expr_sum.c.

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

SCIP_DECL_EXPRPRINT()

static SCIP_DECL_EXPRPRINT ( printSum  )

static

expression print callback

! [SnippetExprPrintSum]

! [SnippetExprPrintSum]

Definition at line 700 of file expr_sum.c.

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

SCIP_DECL_EXPREVAL()

static SCIP_DECL_EXPREVAL ( evalSum  )

static

expression point evaluation callback

! [SnippetExprEvalSum]

! [SnippetExprEvalSum]

Definition at line 777 of file expr_sum.c.

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

SCIP_DECL_EXPRFWDIFF()

static SCIP_DECL_EXPRFWDIFF ( fwdiffSum  )

static

expression forward derivative evaluation callback

Definition at line 802 of file expr_sum.c.

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

SCIP_DECL_EXPRBWDIFF()

static SCIP_DECL_EXPRBWDIFF ( bwdiffSum  )

static

expression derivative evaluation callback

Definition at line 826 of file expr_sum.c.

References NULL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), and SCIPisExprValue().

SCIP_DECL_EXPRBWFWDIFF()

static SCIP_DECL_EXPRBWFWDIFF ( bwfwdiffSum  )

static

expression backward forward derivative evaluation callback

Definition at line 841 of file expr_sum.c.

References NULL, and SCIP_OKAY.

SCIP_DECL_EXPRINTEVAL()

static SCIP_DECL_EXPRINTEVAL ( intevalSum  )

static

expression interval evaluation callback

Definition at line 852 of file expr_sum.c.

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

SCIP_DECL_EXPRINITESTIMATES()

static SCIP_DECL_EXPRINITESTIMATES ( initEstimatesSum  )

static

initial estimators callback

Definition at line 898 of file expr_sum.c.

References BMScopyMemoryArray, EXPRHDLR_NAME, NULL, SCIP_OKAY, SCIPexprGetData(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPinfoMessage(), and SCIPprintExpr().

SCIP_DECL_EXPRESTIMATE()

static SCIP_DECL_EXPRESTIMATE ( estimateSum  )

static

expression estimate callback

Definition at line 927 of file expr_sum.c.

References BMSclearMemoryArray, BMScopyMemoryArray, EXPRHDLR_NAME, FALSE, NULL, SCIP_OKAY, SCIPexprGetData(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), and TRUE.

SCIP_DECL_EXPRREVERSEPROP()

static SCIP_DECL_EXPRREVERSEPROP ( reversepropSum  )

static

expression reverse propagation callback

Definition at line 958 of file expr_sum.c.

References BMScopyMemoryArray, NULL, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPallocBufferArray, SCIPexprGetData(), SCIPexprGetNChildren(), SCIPfreeBufferArray, and SCIPintervalPropagateWeightedSum().

SCIP_DECL_EXPRHASH()

static SCIP_DECL_EXPRHASH ( hashSum  )

static

sum hash callback

! [SnippetExprHashSum]

! [SnippetExprHashSum]

Definition at line 990 of file expr_sum.c.

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

SCIP_DECL_EXPRCURVATURE()

static SCIP_DECL_EXPRCURVATURE ( curvatureSum  )

static

expression curvature detection callback

Definition at line 1016 of file expr_sum.c.

References NULL, SCIP_OKAY, SCIPexprcurvMultiply(), SCIPexprGetData(), SCIPexprGetNChildren(), and TRUE.

SCIP_DECL_EXPRMONOTONICITY()

static SCIP_DECL_EXPRMONOTONICITY ( monotonicitySum  )

static

expression monotonicity detection callback

Definition at line 1039 of file expr_sum.c.

References NULL, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_OKAY, SCIPexprGetData(), and SCIPexprGetNChildren().

SCIP_DECL_EXPRINTEGRALITY()

static SCIP_DECL_EXPRINTEGRALITY ( integralitySum  )

static

expression integrality detection callback

! [SnippetExprIntegralitySum]

! [SnippetExprIntegralitySum]

Definition at line 1058 of file expr_sum.c.

References EPSISINT, MIN, NULL, SCIP_IMPLINTTYPE_NONE, SCIP_IMPLINTTYPE_STRONG, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetIntegrality(), and SCIPexprGetNChildren().