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