Scippy

SCIP

Solving Constraint Integer Programs

struct_expr.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_expr.h
17  * @brief data definitions for expressions and expression trees
18  * @author Stefan Vigerske
19  * @author Thorsten Gellermann
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_EXPRESSION_H__
25 #define __SCIP_STRUCT_EXPRESSION_H__
26 
27 #include "scip/def.h"
28 #include "scip/type_misc.h"
29 #include "nlpi/type_expr.h"
31 #include "blockmemshell/memory.h"
32 
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36 
37 /** operator data of an expression */
38 union SCIP_ExprOpData
39 {
40  int intval; /**< index of a variable or parameter or a constant integer value */
41  SCIP_Real dbl; /**< a constant double value */
42  void* data; /**< pointer to some data structure */
43 };
44 
45 /** arithmetic expression node */
46 struct SCIP_Expr
47 {
48  SCIP_EXPROP op; /**< operator of the node */
49  int nchildren; /**< number of children */
50  SCIP_EXPR** children; /**< children nodes */
51  SCIP_EXPROPDATA data; /**< operator data */
52 };
53 
54 /** expression tree */
56 {
57  BMS_BLKMEM* blkmem; /**< block memory data structure */
58  SCIP_EXPR* root; /**< root node expression of expression tree */
59  int nvars; /**< number of variables */
60  void** vars; /**< mapping of variable indices to user variables, may be NULL */
61  int nparams; /**< number of parameters (modifiable constants) in expression */
62  SCIP_Real* params; /**< current values for parameters, or NULL if no parameters */
63  SCIP_EXPRINTDATA* interpreterdata; /**< data of expression interpreter (evaluator) */
64 };
65 
66 /** data of quadratic expression: sum_i coef_i x_i y_i */
68 {
69  SCIP_Real constant; /**< constant term */
70  SCIP_Real* lincoefs; /**< linear coefficients of children */
71  SCIP_QUADELEM* quadelems; /**< quadratic elements */
72  int nquadelems; /**< number of quadratic elements */
73  SCIP_Bool sorted; /**< are the quadratic elements sorted? */
74 };
75 
76 /** data of polynomial expression: constant + sum_i monom_i */
78 {
79  SCIP_Real constant; /**< constant term of polynomial */
80  SCIP_EXPRDATA_MONOMIAL** monomials; /**< monomials that constitute the polynomial */
81  int monomialssize; /**< size of monomials array */
82  int nmonomials; /**< number of monomials */
83  SCIP_Bool sorted; /**< are the monomials sorted? */
84 };
85 
86 /** data of monomial in polynomial expression: coef * prod_i child_i^exponent_i
87  * we allow for real values exponents here
88  */
90 {
91  SCIP_Real coef; /**< coefficient of monomial */
92  int factorssize; /**< size of factors arrays */
93  int nfactors; /**< number of factors */
94  int* childidxs; /**< children corresponding to factors */
95  SCIP_Real* exponents; /**< value of exponent for each factor */
96  SCIP_Bool sorted; /**< are the factors sorted (by childidx)? */
97 };
98 
99 /** data of a user-defined expression
100  */
102 {
103  SCIP_USEREXPRDATA* userdata; /**< user data for expression */
104  SCIP_EXPRINTCAPABILITY evalcapability; /**< capabilities of evaluation functions */
105  SCIP_DECL_USEREXPREVAL ((*eval)); /**< evaluation function */
106  SCIP_DECL_USEREXPRINTEVAL ((*inteval)); /**< interval evaluation function */
107  SCIP_DECL_USEREXPRCURV ((*curv)); /**< curvature check function */
108  SCIP_DECL_USEREXPRPROP ((*prop)); /**< interval propagation function */
109  SCIP_DECL_USEREXPRESTIMATE ((*estimate)); /**< under-/over-estimator function */
110  SCIP_DECL_USEREXPRCOPYDATA ((*copydata)); /**< expression data copy function, or NULL if nothing to copy */
111  SCIP_DECL_USEREXPRFREEDATA ((*freedata)); /**< expression data free function, or NULL if nothing to free */
112  SCIP_DECL_USEREXPRPRINT ((*print)); /**< expression print function, or NULL for default string "user()" */
113 };
114 
115 /** a node in an expression graph */
117 {
118  /* definition of expression */
119  SCIP_EXPROP op; /**< operand of expression */
120  SCIP_EXPROPDATA data; /**< data of expression */
121 
122  /* location of expression in expression graph */
123  int depth; /**< depth of node in expression graph */
124  int pos; /**< position of node in expression graph nodes array of depth depth*/
125 
126  /* children of expression */
127  int nchildren; /**< number of child nodes in expression graph */
128  SCIP_EXPRGRAPHNODE** children; /**< children nodes */
129 
130  /* parents of expression */
131  int parentssize; /**< length of parents array */
132  int nparents; /**< number of parent nodes in expression graph */
133  SCIP_EXPRGRAPHNODE** parents; /**< parent nodes */
134  SCIP_Bool parentssorted; /**< whether the parents array is sorted */
135 
136  /* domain propagation */
137  SCIP_INTERVAL bounds; /**< bounds on expression */
138  SCIP_EXPRBOUNDSTATUS boundstatus; /**< status of bounds */
139 
140  /* value */
141  SCIP_Real value; /**< value of expression in last evaluation call */
142 
143  /* curvature */
144  SCIP_EXPRCURV curv; /**< curvature of expression */
145 
146  /* miscellaneous */
147  SCIP_Bool enabled; /**< whether the node is enabled currently */
148  SCIP_Bool simplified; /**< whether the node has been simplified */
149  int nuses; /**< how often node is used */
150 };
151 
152 /** a set of expression trees, stored in a single directed acyclic graph
153  * the variables of the graph are stored at depth 0
154  * for each depth, an array of nodes is stored */
156 {
157  BMS_BLKMEM* blkmem; /**< block memory */
158 
159  int depth; /**< depth of expression graph */
160  int* nodessize; /**< current size of nodes array for each depth */
161  int* nnodes; /**< number of nodes for each depth */
162  SCIP_EXPRGRAPHNODE*** nodes; /**< nodes of expression graph for each depth */
163 
164  int varssize; /**< length of vars array */
165  int nvars; /**< number of variables in expression graph */
166  void** vars; /**< array for variables in expression graph, having length varssize */
167  SCIP_EXPRGRAPHNODE** varnodes; /**< nodes corresponding to variables in expression graph */
168  SCIP_INTERVAL* varbounds; /**< current bounds on variables */
169  SCIP_HASHMAP* varidxs; /**< maps variables to variable indices */
170 
171  int constssize; /**< length of consts array */
172  int nconsts; /**< number of constants in expression graph */
173  SCIP_EXPRGRAPHNODE** constnodes; /**< nodes corresponding to constants in expression graph */
174  SCIP_Bool constssorted; /**< whether the constnodes array has been sorted */
175 
176  SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)); /**< callback for variable addition event */
177  SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)); /**< callback for variable removal event */
178  SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)); /**< callback for variable index change event */
179  void* userdata; /**< user data associated with callback methods */
180 
181  SCIP_Bool needvarboundprop; /**< whether variable bounds need be propagated, e.g., because new nodes have been added to the graph */
182 };
183 
184 #ifdef __cplusplus
185 }
186 #endif
187 
188 #endif /* __SCIP_STRUCT_EXPRESSION_H__ */
SCIP_EXPROPDATA data
Definition: struct_expr.h:51
static SCIP_RETCODE eval(SCIP_EXPR *expr, const vector< Type > &x, SCIP_Real *param, Type &val)
type definitions for miscellaneous datastructures
SCIP_Bool constssorted
Definition: struct_expr.h:174
struct SCIP_UserExprData SCIP_USEREXPRDATA
Definition: type_expr.h:219
SCIP_Real * exponents
Definition: struct_expr.h:95
#define SCIP_DECL_USEREXPREVAL(x)
Definition: type_expr.h:246
#define SCIP_DECL_USEREXPRPRINT(x)
Definition: type_expr.h:308
type definitions for expression interpreter
SCIP_EXPROP op
Definition: struct_expr.h:48
SCIP_EXPRBOUNDSTATUS boundstatus
Definition: struct_expr.h:138
#define SCIP_DECL_USEREXPRINTEVAL(x)
Definition: type_expr.h:259
SCIP_EXPRDATA_MONOMIAL ** monomials
Definition: struct_expr.h:80
unsigned int SCIP_EXPRINTCAPABILITY
BMS_BLKMEM * blkmem
Definition: struct_expr.h:157
SCIP_EXPRCURV curv
Definition: struct_expr.h:144
SCIP_EXPR * root
Definition: struct_expr.h:58
int nchildren
Definition: struct_expr.h:49
#define SCIP_DECL_EXPRGRAPHVARADDED(x)
Definition: type_expr.h:181
SCIP_HASHMAP * varidxs
Definition: struct_expr.h:169
SCIP_Real * params
Definition: struct_expr.h:62
SCIP_Bool simplified
Definition: struct_expr.h:148
union SCIP_ExprOpData SCIP_EXPROPDATA
Definition: type_expr.h:90
enum SCIP_ExprOp SCIP_EXPROP
Definition: type_expr.h:89
SCIP_INTERVAL bounds
Definition: struct_expr.h:137
SCIP_EXPRGRAPHNODE *** nodes
Definition: struct_expr.h:162
SCIP_EXPRGRAPHNODE ** varnodes
Definition: struct_expr.h:167
char SCIP_EXPRBOUNDSTATUS
Definition: type_expr.h:216
#define SCIP_DECL_USEREXPRCURV(x)
Definition: type_expr.h:270
#define SCIP_DECL_USEREXPRESTIMATE(x)
Definition: type_expr.h:234
#define SCIP_DECL_USEREXPRPROP(x)
Definition: type_expr.h:282
SCIP_EXPRGRAPHNODE ** children
Definition: struct_expr.h:128
#define SCIP_Bool
Definition: def.h:61
void ** vars
Definition: struct_expr.h:60
SCIP_Bool needvarboundprop
Definition: struct_expr.h:181
SCIP_USEREXPRDATA * userdata
Definition: struct_expr.h:103
BMS_BLKMEM * blkmem
Definition: struct_expr.h:57
SCIP_EXPR ** children
Definition: struct_expr.h:50
SCIP_INTERVAL * varbounds
Definition: struct_expr.h:168
SCIP_EXPROPDATA data
Definition: struct_expr.h:120
SCIP_EXPRGRAPHNODE ** parents
Definition: struct_expr.h:133
SCIP_EXPROP op
Definition: struct_expr.h:119
SCIP_QUADELEM * quadelems
Definition: struct_expr.h:71
#define SCIP_DECL_EXPRGRAPHVARREMOVE(x)
Definition: type_expr.h:191
enum SCIP_ExprCurv SCIP_EXPRCURV
Definition: type_expr.h:93
SCIP_EXPRINTDATA * interpreterdata
Definition: struct_expr.h:63
SCIP_Bool parentssorted
Definition: struct_expr.h:134
SCIP_EXPRGRAPHNODE ** constnodes
Definition: struct_expr.h:173
type definitions for expressions and expression trees
#define SCIP_DECL_USEREXPRCOPYDATA(x)
Definition: type_expr.h:291
#define SCIP_Real
Definition: def.h:135
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:392
struct SCIP_ExprIntData SCIP_EXPRINTDATA
#define SCIP_DECL_USEREXPRFREEDATA(x)
Definition: type_expr.h:299
SCIP_EXPRINTCAPABILITY evalcapability
Definition: struct_expr.h:104
#define SCIP_DECL_EXPRGRAPHVARCHGIDX(x)
Definition: type_expr.h:203
memory allocation routines