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"

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_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_RealSCIPgetCoefsExprSum (SCIP_EXPR *expr)
 
SCIP_Real SCIPgetConstantExprSum (SCIP_EXPR *expr)
 

Macro Definition Documentation

◆ EXPRHDLR_NAME

#define EXPRHDLR_NAME   "sum"

◆ EXPRHDLR_DESC

#define EXPRHDLR_DESC   "summation with coefficients and a constant"

Definition at line 35 of file expr_sum.c.

Referenced by SCIPincludeExprhdlrSum().

◆ EXPRHDLR_PRECEDENCE

#define EXPRHDLR_PRECEDENCE   40000

Definition at line 36 of file expr_sum.c.

Referenced by SCIP_DECL_EXPRPRINT(), and SCIPincludeExprhdlrSum().

◆ EXPRHDLR_HASHKEY

#define EXPRHDLR_HASHKEY   SCIPcalcFibHash(47161.0)

Definition at line 37 of file expr_sum.c.

Referenced by SCIP_DECL_EXPRHASH().

◆ debugSimplify

#define debugSimplify   while( FALSE ) printf

macro to activate/deactivate debugging information of simplify method

Definition at line 44 of file expr_sum.c.

Referenced by SCIP_DECL_EXPRSIMPLIFY().

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 65 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 103 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(), and TRUE.

Referenced by SCIP_DECL_EXPRSIMPLIFY().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sortExprComp  )
static

Definition at line 335 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 353 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_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 544 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 611 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 620 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 638 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 657 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 734 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 759 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 783 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 798 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 947 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 973 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 996 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 1015 of file expr_sum.c.

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