Scippy

SCIP

Solving Constraint Integer Programs

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_RealSCIPgetCoefsExprSum (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
scipSCIP data structure
exprdatapointer where to store expression data
ncoefficientsnumber of coefficients (i.e., number of children)
coefficientsarray with coefficients for all children (or NULL if all 1.0)
constantconstant 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
scipSCIP data structure
duplicateexpression to be simplified
idxidx of children to be simplified
changedpointer to store if some term actually got simplified
ownercreatedatadata 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()

◆ SCIP_DECL_EXPRINITESTIMATES()

static SCIP_DECL_EXPRINITESTIMATES ( initEstimatesSum  )
static

◆ SCIP_DECL_EXPRESTIMATE()

static SCIP_DECL_EXPRESTIMATE ( estimateSum  )
static

◆ SCIP_DECL_EXPRREVERSEPROP()

static SCIP_DECL_EXPRREVERSEPROP ( reversepropSum  )
static

◆ 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, NULL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetData(), SCIPexprGetNChildren(), and SCIPexprIsIntegral().