Scippy

SCIP

Solving Constraint Integer Programs

type_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 type_expr.h
17  * @brief type definitions for expressions and expression trees
18  * @ingroup TYPEDEFINITIONS
19  * @author Stefan Vigerske
20  * @author Thorsten Gellermann
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_TYPE_EXPRESSION_H__
26 #define __SCIP_TYPE_EXPRESSION_H__
27 
28 #ifdef __cplusplus
29 extern "C" {
30 #endif
31 
32 /** Operators of expressions.
33  */
35  /**@name Terminals (Leaves) */
36  /**@{ */
37  SCIP_EXPR_VARIDX = 1, /**< variable given by index (stored in data.idx) */
38  SCIP_EXPR_CONST = 2, /**< constant (value stored in data.dbl) */
39  SCIP_EXPR_PARAM = 3, /**< parameter = a constant that can be modified (should not be simplified away) */
40  /**@} */
41 
42  /**@name Simple Operands */
43  /**@{ */
44  SCIP_EXPR_PLUS = 8, /**< addition (2 operands) */
45  SCIP_EXPR_MINUS = 9, /**< substraction (2 operands) */
46  SCIP_EXPR_MUL = 10, /**< multiplication (2 operands) */
47  SCIP_EXPR_DIV = 11, /**< division (2 operands) */
48  SCIP_EXPR_SQUARE = 12, /**< square (1 operand) */
49  SCIP_EXPR_SQRT = 13, /**< square root (1 operand) */
50  SCIP_EXPR_REALPOWER = 14, /**< power with real exponent (1 operand!, assumed to be nonnegative, exponent is stored in expression data) */
51  SCIP_EXPR_INTPOWER = 15, /**< power with integer exponent (1 operand!, exponent stored in expression data) */
52  SCIP_EXPR_SIGNPOWER = 16, /**< signed power (sign(x)|x|^a, 1 operand!, exponent is stored in expression data) */
53  SCIP_EXPR_EXP = 17, /**< exponential (e^x, 1 operand) */
54  SCIP_EXPR_LOG = 18, /**< natural logarithm (ln(x), 1 operand) */
55  SCIP_EXPR_SIN = 19, /**< sinus (1 operand) */
56  SCIP_EXPR_COS = 20, /**< cosinus (1 operand) */
57  SCIP_EXPR_TAN = 21, /**< tangent (1 operand) */
58  /* SCIP_EXPR_ERF = 22, */ /**< gaussian error function (1 operand) */
59  /* SCIP_EXPR_ERFI = 23, */ /**< imaginary part of gaussian error function (1 operand) */
60  SCIP_EXPR_MIN = 24, /**< minimum (2 operands) */
61  SCIP_EXPR_MAX = 25, /**< maximum (2 operands) */
62  SCIP_EXPR_ABS = 26, /**< absolute value (1 operand) */
63  SCIP_EXPR_SIGN = 27, /**< sign of value (1 operand) */
64  /**@} */
65 
66  /**@name Complex Operands
67  */
68  /**@{ */
69  SCIP_EXPR_SUM = 64, /**< summation sum_{i=1}^n op_i (n operands) */
70  SCIP_EXPR_PRODUCT = 65, /**< product prod_{i=1}^n op_i (n operands) */
71  SCIP_EXPR_LINEAR = 66, /**< linear term sum_{i=1}^n a_i op_i (n operands) */
72  SCIP_EXPR_QUADRATIC = 67, /**< quadratic term sum_{i,j=1}^n a_{i,j} op_i op_j (n operands) */
73  SCIP_EXPR_POLYNOMIAL= 68, /**< polynomial term sum_{I} a_{I}ops^I (I a multiindex, n operands) */
74  SCIP_EXPR_USER = 69, /**< a user defined expression */
75  /**@} */
76 
77  SCIP_EXPR_LAST = 70 /**< no expression, used for counting reasons */
78 };
79 
80 /** Curvature types */
82 {
83  SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown curvature (or indefinite) */
84  SCIP_EXPRCURV_CONVEX = 1, /**< convex */
85  SCIP_EXPRCURV_CONCAVE = 2, /**< concave */
86  SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */
87 };
88 
89 typedef enum SCIP_ExprOp SCIP_EXPROP; /**< expression operand */
90 typedef union SCIP_ExprOpData SCIP_EXPROPDATA; /**< expression operand data */
91 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */
92 typedef struct SCIP_ExprTree SCIP_EXPRTREE; /**< expression tree */
93 typedef enum SCIP_ExprCurv SCIP_EXPRCURV; /**< curvature types */
94 
95 /** An element of a quadratic term: two variable indices and a coefficient.
96  * The convention is to have idx1 <= idx2.
97  */
99 {
100  int idx1; /**< index of first variable */
101  int idx2; /**< index of second variable */
102  SCIP_Real coef; /**< value of coefficient at position (idx1, idx2) */
103 };
104 /* We have defined struct SCIP_QuadElement here (instead of type_expression.h) to allow fast access, allocation, and copying. (similar to SCIP_INTERVAL) */
105 
106 typedef struct SCIP_QuadElement SCIP_QUADELEM; /**< element of a quadratic term */
107 typedef struct SCIP_ExprData_Quadratic SCIP_EXPRDATA_QUADRATIC; /**< the data of a quadratic expression (SCIP_EXPR_QUADRATIC) */
108 
109 typedef struct SCIP_ExprData_Monomial SCIP_EXPRDATA_MONOMIAL; /**< a monomial as part of the data in a polynomial expression */
110 typedef struct SCIP_ExprData_Polynomial SCIP_EXPRDATA_POLYNOMIAL; /**< the data of a polynomial expression (SCIP_EXPR_POLYNOMIAL) */
111 
112 typedef struct SCIP_ExprData_User SCIP_EXPRDATA_USER; /**< expression data of a user expression (not the user-data of a user expression) */
113 
114 #define SCIP_EXPR_DEGREEINFINITY 65535 /**< value that stands for an infinite degree of an expression (see SCIPexprGetMaxDegree) */
115 
116 /** signature of an expression (pointwise) evaluation function
117  * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.
118  *
119  * - opdata operand data
120  * - nargs number of arguments
121  * - argvals values of arguments
122  * - varvals values for variables
123  * - paramvals values for parameters
124  * - result buffer where to store result of evaluation
125  */
126 #define SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (SCIP_EXPROPDATA opdata, int nargs, SCIP_Real* argvals, SCIP_Real* varvals, SCIP_Real* paramvals, SCIP_Real* result)
127 
128 /** signature of an expression (interval) evaluation function
129  * The function should return an empty interval if the function is undefined for the given arguments.
130  *
131  * - infinity value for infinity
132  * - opdata operand data
133  * - nargs number of arguments
134  * - argvals interval values of arguments
135  * - varvals interval values for variables
136  * - paramvals values for parameters
137  * - result buffer where to store result of evaluation
138  */
139 #define SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* varvals, SCIP_Real* paramvals, SCIP_INTERVAL* result)
140 
141 /** signature of a simple expression curvature check function
142  *
143  * - infinity value for infinity
144  * - opdata operand data
145  * - nargs number of arguments
146  * - argbounds bounds on value of arguments
147  * - argcurv curvature of arguments
148  * - paramvals values for parameters
149  * - result buffer where to store result of curvature check
150  */
151 #define SCIP_DECL_EXPRCURV(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_EXPROPDATA opdata, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)
152 
153 /** signature of a expression data copy function
154  *
155  * - blkmem block memory
156  * - nchildren number of children in expression
157  * - opdatasource source expression data
158  * - opdatatarget pointer to target expression data
159  */
160 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdatasource, SCIP_EXPROPDATA* opdatatarget)
161 
162 /** signature of a expression data free function
163  *
164  * - blkmem block memory
165  * - nchildren number of children in expression
166  * - opdata expression data to free
167  */
168 #define SCIP_DECL_EXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdata)
169 
170 typedef struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE; /**< node in an expression graph */
171 typedef struct SCIP_ExprGraph SCIP_EXPRGRAPH; /**< an expression graph (DAG) */
172 
173 /** callback method of expression graph invoked when a new variable has been added to the graph
174  *
175  * input:
176  * - exprgraph expression graph
177  * - userdata a pointer to user data
178  * - var variable that has been added to expression graph
179  * - varnode new expression graph node for a variable
180  */
181 #define SCIP_DECL_EXPRGRAPHVARADDED(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)
182 
183 /** callback method of expression graph invoked when a variable is to be removed from the graph
184  *
185  * input:
186  * - exprgraph expression graph
187  * - userdata a pointer to user data
188  * - var variable that will be removed from the expression graph
189  * - varnode expression graph node corresponding to variable
190  */
191 #define SCIP_DECL_EXPRGRAPHVARREMOVE(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)
192 
193 /** callback method of expression graph invoked when a variable changes its index
194  *
195  * input:
196  * - exprgraph expression graph
197  * - userdata a pointer to user data
198  * - var variable which will change its index
199  * - varnode expression graph node corresponding to variable
200  * - oldidx current index of variable
201  * - newidx new index the variable will have
202  */
203 #define SCIP_DECL_EXPRGRAPHVARCHGIDX(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode, int oldidx, int newidx)
204 
205 /* SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE is used to indicate that bounds in a node should be propagated down even if they are not better than the bounds given by the child nodes
206  * this is useful if the expression itself has a domain that is not the whole real numbers and we want to propagate this information down to a child node
207  * e.g., a x^0.3 should result in x >= 0 even if no new bounds on the expression x^0.3 have been obtained
208  */
209 #define SCIP_EXPRBOUNDSTATUS_VALID 0x0 /**< bounds are valid, i.e., conform with bounds of children */
210 #define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED 0x1 /**< a child bounds were tightened since last calculation */
211 #define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED 0x2 /**< bounds are not valid and need to be recomputed, because the bounds in a child were relaxed */
212 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT 0x4 /**< bounds have been tightened by reverse propagation in a parent, they are valid as long as there has been no relaxation of bounds somewhere in the graph */
213 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT (0x8 | SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENT) /**< bounds have recently been tightened by reverse propagation in a parent, this tightening has not been propagated further down yet */
214 #define SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTFORCE (0x10 | SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT) /**< bounds may have recently been tightened by reverse propagation in a parent, in any case we want to propagate bounds further down */
215 
216 typedef char SCIP_EXPRBOUNDSTATUS; /**< bitflags that indicate the status of bounds stored in a node of an expression graph */
217 
218 
219 typedef struct SCIP_UserExprData SCIP_USEREXPRDATA; /**< the user data of a user expression */
220 
221 /** signature of an user's expression under/over estimation function
222  * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.
223  *
224  * - infinity value for infinity
225  * - data user expression data
226  * - nargs number of arguments
227  * - argvals values of arguments
228  * - argbounds bounds on value of arguments
229  * - overestimate flag indicating whether to over- or under estimate the expression
230  * - coeffs buffer where to store resulting coeffs of arguments for the estimator
231  * - constant buffer where to store resulting constant of the estimator
232  * - success buffer to indicate whether under-/overestimation was successful
233  */
234 #define SCIP_DECL_USEREXPRESTIMATE(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_INTERVAL* argbounds, SCIP_Bool overestimate, SCIP_Real* coeffs, SCIP_Real* constant, SCIP_Bool *success)
235 
236 /** signature of an user's expression (pointwise) evaluation function
237  * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.
238  *
239  * - data user expression data
240  * - nargs number of arguments
241  * - argvals values of arguments
242  * - funcvalue buffer where to store result of function evaluation
243  * - gradient buffer where to store result of gradient evaluation (NULL if not requested)
244  * - hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix)
245  */
246 #define SCIP_DECL_USEREXPREVAL(x) SCIP_RETCODE x (SCIP_USEREXPRDATA* data, int nargs, SCIP_Real* argvals, SCIP_Real* funcvalue, SCIP_Real* gradient, SCIP_Real* hessian)
247 
248 /** signature of an user's expression (interval) evaluation function
249  * The function should return an empty interval if the function is undefined for the given arguments.
250  *
251  * - infinity value for infinity
252  * - data user expression data
253  * - nargs number of arguments
254  * - argvals interval values of arguments
255  * - funvalue buffer where to store result of function evaluation
256  * - gradient buffer where to store result of gradient evaluation (NULL if not requested)
257  * - hessian buffer where to store result of Hessian evaluation (NULL if not requested, currently full dense matrix)
258  */
259 #define SCIP_DECL_USEREXPRINTEVAL(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argvals, SCIP_INTERVAL* funcvalue, SCIP_INTERVAL* gradient, SCIP_INTERVAL* hessian)
260 
261 /** signature of a user's expression curvature check function
262  *
263  * - infinity value for infinity
264  * - data user expression data
265  * - nargs number of arguments
266  * - argbounds bounds on value of arguments
267  * - argcurv curvature of arguments
268  * - result buffer where to store result of curvature check
269  */
270 #define SCIP_DECL_USEREXPRCURV(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_EXPRCURV* argcurv, SCIP_EXPRCURV* result)
271 
272 /** signature of an user's expression interval propagation function
273  * The function should compute intervals of the arguments given an interval for the function itself and all arguments.
274  *
275  * - infinity value for infinity
276  * - data user expression data
277  * - nargs number of arguments
278  * - argbounds bounds on values of arguments (on output: tightened bounds)
279  * - funcbounds bounds on function value
280  * - cutoff buffer to indicate whether an empty child interval was found
281  */
282 #define SCIP_DECL_USEREXPRPROP(x) SCIP_RETCODE x (SCIP_Real infinity, SCIP_USEREXPRDATA* data, int nargs, SCIP_INTERVAL* argbounds, SCIP_INTERVAL funcbounds, SCIP_Bool* cutoff)
283 
284 /** signature of a user's expression data copy function
285  *
286  * - blkmem block memory
287  * - nchildren number of children in expression
288  * - datasource source user expression data
289  * - datatarget target user expression data
290  */
291 #define SCIP_DECL_USEREXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* datasource, SCIP_USEREXPRDATA** datatarget)
292 
293 /** signature of a user's expression data free function
294  *
295  * - blkmem block memory
296  * - nchildren number of children in expression
297  * - data user expression data to free
298  */
299 #define SCIP_DECL_USEREXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_USEREXPRDATA* data)
300 
301 
302 #ifdef __cplusplus
303 }
304 #endif
305 
306 #endif /* __SCIP_TYPE_EXPRESSION_H__ */
struct SCIP_UserExprData SCIP_USEREXPRDATA
Definition: type_expr.h:219
SCIP_Real coef
Definition: type_expr.h:102
union SCIP_ExprOpData SCIP_EXPROPDATA
Definition: type_expr.h:90
enum SCIP_ExprOp SCIP_EXPROP
Definition: type_expr.h:89
char SCIP_EXPRBOUNDSTATUS
Definition: type_expr.h:216
SCIP_ExprCurv
Definition: type_expr.h:81
enum SCIP_ExprCurv SCIP_EXPRCURV
Definition: type_expr.h:93
#define SCIP_Real
Definition: def.h:127
SCIP_ExprOp
Definition: type_expr.h:34