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-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 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  /**@} */
75 
76  SCIP_EXPR_LAST = 69 /**< no expression, used for counting reasons */
77 };
78 
79 /** Curvature types */
81 {
82  SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown curvature (or indefinite) */
83  SCIP_EXPRCURV_CONVEX = 1, /**< convex */
84  SCIP_EXPRCURV_CONCAVE = 2, /**< concave */
85  SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */
86 };
87 
88 typedef enum SCIP_ExprOp SCIP_EXPROP; /**< expression operand */
89 typedef union SCIP_ExprOpData SCIP_EXPROPDATA; /**< expression operand data */
90 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */
91 typedef struct SCIP_ExprTree SCIP_EXPRTREE; /**< expression tree */
92 typedef enum SCIP_ExprCurv SCIP_EXPRCURV; /**< curvature types */
93 
94 /** An element of a quadratic term: two variable indices and a coefficient.
95  * The convention is to have idx1 <= idx2.
96  */
97 struct SCIP_QuadElement
98 {
99  int idx1; /**< index of first variable */
100  int idx2; /**< index of second variable */
101  SCIP_Real coef; /**< value of coefficient at position (idx1, idx2) */
102 };
103 /* We have defined struct SCIP_QuadElement here (instead of type_expression.h) to allow fast access, allocation, and copying. (similar to SCIP_INTERVAL) */
104 
105 typedef struct SCIP_QuadElement SCIP_QUADELEM; /**< element of a quadratic term */
106 typedef struct SCIP_ExprData_Quadratic SCIP_EXPRDATA_QUADRATIC; /**< the data of a quadratic expression (SCIP_EXPR_QUADRATIC) */
107 
108 typedef struct SCIP_ExprData_Monomial SCIP_EXPRDATA_MONOMIAL; /**< a monomial as part of the data in a polynomial expression */
109 typedef struct SCIP_ExprData_Polynomial SCIP_EXPRDATA_POLYNOMIAL; /**< the data of a polynomial expression (SCIP_EXPR_POLYNOMIAL) */
110 
111 #define SCIP_EXPR_DEGREEINFINITY 65535 /**< value that stands for an infinite degree of an expression (see SCIPexprGetMaxDegree) */
112 
113 /** signature of an expression (pointwise) evaluation function
114  * The function should return nan, inf, or -inf in result if the function is undefined for the given arguments.
115  *
116  * - opdata operand data
117  * - nargs number of arguments
118  * - argvals values of arguments
119  * - varvals values for variables
120  * - paramvals values for parameters
121  * - result buffer where to store result of evaluation
122  */
123 #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)
124 
125 /** signature of an expression (interval) evaluation function
126  * The function should return an empty interval if the function is undefined for the given arguments.
127  *
128  * - infinity value for infinity
129  * - opdata operand data
130  * - nargs number of arguments
131  * - argvals interval values of arguments
132  * - varvals interval values for variables
133  * - paramvals values for parameters
134  * - result buffer where to store result of evaluation
135  */
136 #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)
137 
138 /** signature of a simple expression curvature check function
139  *
140  * - infinity value for infinity
141  * - opdata operand data
142  * - nargs number of arguments
143  * - argbounds bounds on value of arguments
144  * - argcurv curvature of arguments
145  * - paramvals values for parameters
146  * - result buffer where to store result of curvature check
147  */
148 #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)
149 
150 /** signature of a expression data copy function
151  *
152  * - blkmem block memory
153  * - nchildren number of children in expression
154  * - opdatasource source expression data
155  * - opdatatarget pointer to target expression data
156  */
157 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdatasource, SCIP_EXPROPDATA* opdatatarget)
158 
159 /** signature of a expression data free function
160  *
161  * - blkmem block memory
162  * - nchildren number of children in expression
163  * - opdata expression data to free
164  */
165 #define SCIP_DECL_EXPRFREEDATA(x) void x (BMS_BLKMEM* blkmem, int nchildren, SCIP_EXPROPDATA opdata)
166 
167 typedef struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE; /**< node in an expression graph */
168 typedef struct SCIP_ExprGraph SCIP_EXPRGRAPH; /**< an expression graph (DAG) */
169 
170 /** callback method of expression graph invoked when a new variable has been added to the graph
171  *
172  * input:
173  * - exprgraph expression graph
174  * - userdata a pointer to user data
175  * - var variable that has been added to expression graph
176  * - varnode new expression graph node for a variable
177  */
178 #define SCIP_DECL_EXPRGRAPHVARADDED(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)
179 
180 /** callback method of expression graph invoked when a variable is to be removed from the graph
181  *
182  * input:
183  * - exprgraph expression graph
184  * - userdata a pointer to user data
185  * - var variable that will be removed from the expression graph
186  * - varnode expression graph node corresponding to variable
187  */
188 #define SCIP_DECL_EXPRGRAPHVARREMOVE(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode)
189 
190 /** callback method of expression graph invoked when a variable changes its index
191  *
192  * input:
193  * - exprgraph expression graph
194  * - userdata a pointer to user data
195  * - var variable which will change its index
196  * - varnode expression graph node corresponding to variable
197  * - oldidx current index of variable
198  * - newidx new index the variable will have
199  */
200 #define SCIP_DECL_EXPRGRAPHVARCHGIDX(x) SCIP_RETCODE x (SCIP_EXPRGRAPH* exprgraph, void* userdata, void* var, SCIP_EXPRGRAPHNODE* varnode, int oldidx, int newidx)
201 
202 /* 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
203  * 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
204  * 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
205  */
206 #define SCIP_EXPRBOUNDSTATUS_VALID 0x0 /**< bounds are valid, i.e., conform with bounds of children */
207 #define SCIP_EXPRBOUNDSTATUS_CHILDTIGHTENED 0x1 /**< a child bounds were tightened since last calculation */
208 #define SCIP_EXPRBOUNDSTATUS_CHILDRELAXED 0x2 /**< bounds are not valid and need to be recomputed, because the bounds in a child were relaxed */
209 #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 */
210 #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 */
211 #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 */
212 
213 typedef char SCIP_EXPRBOUNDSTATUS; /**< bitflags that indicate the status of bounds stored in a node of an expression graph */
214 
215 #ifdef __cplusplus
216 }
217 #endif
218 
219 #endif /* __SCIP_TYPE_EXPRESSION_H__ */
220