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-2014 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"
30 #include "nlpi/type_exprinterpret.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 */
55 struct SCIP_ExprTree
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 */
67 struct SCIP_ExprData_Quadratic
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 */
77 struct SCIP_ExprData_Polynomial
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  */
89 struct SCIP_ExprData_Monomial
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 /** a node in an expression graph */
100 struct SCIP_ExprGraphNode
101 {
102  /* definition of expression */
103  SCIP_EXPROP op; /**< operand of expression */
104  SCIP_EXPROPDATA data; /**< data of expression */
105 
106  /* location of expression in expression graph */
107  int depth; /**< depth of node in expression graph */
108  int pos; /**< position of node in expression graph nodes array of depth depth*/
109 
110  /* children of expression */
111  int nchildren; /**< number of child nodes in expression graph */
112  SCIP_EXPRGRAPHNODE** children; /**< children nodes */
113 
114  /* parents of expression */
115  int parentssize; /**< length of parents array */
116  int nparents; /**< number of parent nodes in expression graph */
117  SCIP_EXPRGRAPHNODE** parents; /**< parent nodes */
118  SCIP_Bool parentssorted; /**< whether the parents array is sorted */
119 
120  /* domain propagation */
121  SCIP_INTERVAL bounds; /**< bounds on expression */
122  SCIP_EXPRBOUNDSTATUS boundstatus; /**< status of bounds */
123 
124  /* value */
125  SCIP_Real value; /**< value of expression in last evaluation call */
126 
127  /* curvature */
128  SCIP_EXPRCURV curv; /**< curvature of expression */
129 
130  /* miscellaneous */
131  SCIP_Bool enabled; /**< whether the node is enabled currently */
132  SCIP_Bool simplified; /**< whether the node has been simplified */
133  int nuses; /**< how often node is used */
134 };
135 
136 /** a set of expression trees, stored in a single directed acyclic graph
137  * the variables of the graph are stored at depth 0
138  * for each depth, an array of nodes is stored */
139 struct SCIP_ExprGraph
140 {
141  BMS_BLKMEM* blkmem; /**< block memory */
142 
143  int depth; /**< depth of expression graph */
144  int* nodessize; /**< current size of nodes array for each depth */
145  int* nnodes; /**< number of nodes for each depth */
146  SCIP_EXPRGRAPHNODE*** nodes; /**< nodes of expression graph for each depth */
147 
148  int varssize; /**< length of vars array */
149  int nvars; /**< number of variables in expression graph */
150  void** vars; /**< array for variables in expression graph, having length varssize */
151  SCIP_EXPRGRAPHNODE** varnodes; /**< nodes corresponding to variables in expression graph */
152  SCIP_INTERVAL* varbounds; /**< current bounds on variables */
153  SCIP_HASHMAP* varidxs; /**< maps variables to variable indices */
154 
155  int constssize; /**< length of consts array */
156  int nconsts; /**< number of constants in expression graph */
157  SCIP_EXPRGRAPHNODE** constnodes; /**< nodes corresponding to constants in expression graph */
158  SCIP_Bool constssorted; /**< whether the constnodes array has been sorted */
159 
160  SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)); /**< callback for variable addition event */
161  SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)); /**< callback for variable removal event */
162  SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)); /**< callback for variable index change event */
163  void* userdata; /**< user data associated with callback methods */
164 
165  SCIP_Bool needvarboundprop; /**< whether variable bounds need be propagated, e.g., because new nodes have been added to the graph */
166 };
167 
168 #ifdef __cplusplus
169 }
170 #endif
171 
172 #endif /* __SCIP_STRUCT_EXPRESSION_H__ */
173