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-2016 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 };
113 
114 /** a node in an expression graph */
116 {
117  /* definition of expression */
118  SCIP_EXPROP op; /**< operand of expression */
119  SCIP_EXPROPDATA data; /**< data of expression */
120 
121  /* location of expression in expression graph */
122  int depth; /**< depth of node in expression graph */
123  int pos; /**< position of node in expression graph nodes array of depth depth*/
124 
125  /* children of expression */
126  int nchildren; /**< number of child nodes in expression graph */
127  SCIP_EXPRGRAPHNODE** children; /**< children nodes */
128 
129  /* parents of expression */
130  int parentssize; /**< length of parents array */
131  int nparents; /**< number of parent nodes in expression graph */
132  SCIP_EXPRGRAPHNODE** parents; /**< parent nodes */
133  SCIP_Bool parentssorted; /**< whether the parents array is sorted */
134 
135  /* domain propagation */
136  SCIP_INTERVAL bounds; /**< bounds on expression */
137  SCIP_EXPRBOUNDSTATUS boundstatus; /**< status of bounds */
138 
139  /* value */
140  SCIP_Real value; /**< value of expression in last evaluation call */
141 
142  /* curvature */
143  SCIP_EXPRCURV curv; /**< curvature of expression */
144 
145  /* miscellaneous */
146  SCIP_Bool enabled; /**< whether the node is enabled currently */
147  SCIP_Bool simplified; /**< whether the node has been simplified */
148  int nuses; /**< how often node is used */
149 };
150 
151 /** a set of expression trees, stored in a single directed acyclic graph
152  * the variables of the graph are stored at depth 0
153  * for each depth, an array of nodes is stored */
155 {
156  BMS_BLKMEM* blkmem; /**< block memory */
157 
158  int depth; /**< depth of expression graph */
159  int* nodessize; /**< current size of nodes array for each depth */
160  int* nnodes; /**< number of nodes for each depth */
161  SCIP_EXPRGRAPHNODE*** nodes; /**< nodes of expression graph for each depth */
162 
163  int varssize; /**< length of vars array */
164  int nvars; /**< number of variables in expression graph */
165  void** vars; /**< array for variables in expression graph, having length varssize */
166  SCIP_EXPRGRAPHNODE** varnodes; /**< nodes corresponding to variables in expression graph */
167  SCIP_INTERVAL* varbounds; /**< current bounds on variables */
168  SCIP_HASHMAP* varidxs; /**< maps variables to variable indices */
169 
170  int constssize; /**< length of consts array */
171  int nconsts; /**< number of constants in expression graph */
172  SCIP_EXPRGRAPHNODE** constnodes; /**< nodes corresponding to constants in expression graph */
173  SCIP_Bool constssorted; /**< whether the constnodes array has been sorted */
174 
175  SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)); /**< callback for variable addition event */
176  SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)); /**< callback for variable removal event */
177  SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)); /**< callback for variable index change event */
178  void* userdata; /**< user data associated with callback methods */
179 
180  SCIP_Bool needvarboundprop; /**< whether variable bounds need be propagated, e.g., because new nodes have been added to the graph */
181 };
182 
183 #ifdef __cplusplus
184 }
185 #endif
186 
187 #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:173
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
type definitions for expression interpreter
SCIP_EXPROP op
Definition: struct_expr.h:48
SCIP_EXPRBOUNDSTATUS boundstatus
Definition: struct_expr.h:137
#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:156
SCIP_EXPRCURV curv
Definition: struct_expr.h:143
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:168
SCIP_Real * params
Definition: struct_expr.h:62
SCIP_Bool simplified
Definition: struct_expr.h:147
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:136
SCIP_EXPRGRAPHNODE *** nodes
Definition: struct_expr.h:161
SCIP_EXPRGRAPHNODE ** varnodes
Definition: struct_expr.h:166
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:127
#define SCIP_Bool
Definition: def.h:53
void ** vars
Definition: struct_expr.h:60
SCIP_Bool needvarboundprop
Definition: struct_expr.h:180
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:167
SCIP_EXPROPDATA data
Definition: struct_expr.h:119
SCIP_EXPRGRAPHNODE ** parents
Definition: struct_expr.h:132
SCIP_EXPROP op
Definition: struct_expr.h:118
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:133
SCIP_EXPRGRAPHNODE ** constnodes
Definition: struct_expr.h:172
type definitions for expressions and expression trees
#define SCIP_DECL_USEREXPRCOPYDATA(x)
Definition: type_expr.h:291
#define SCIP_Real
Definition: def.h:127
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