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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file type_expr.h
17 * @ingroup TYPEDEFINITIONS
18 * @brief type and macro definitions related to algebraic expressions
19 * @author Ksenia Bestuzheva
20 * @author Benjamin Mueller
21 * @author Felipe Serrano
22 * @author Stefan Vigerske
23 *
24 * This file defines the interface for expression handlers.
25 *
26 * - \ref EXPRHDLRS "List of available expression handlers"
27 */
28
29 /** @defgroup DEFPLUGINS_EXPR Default expression handlers
30 * @ingroup DEFPLUGINS
31 * @brief implementation files (.c files) of the default expression handlers of SCIP
32 */
33
34 #ifndef SCIP_TYPE_EXPR_H_
35 #define SCIP_TYPE_EXPR_H_
36
37 #include "scip/def.h"
38 #include "scip/intervalarith.h"
39 #include "scip/type_scip.h"
40 #include "scip/type_sol.h"
41 #include "scip/type_var.h"
42 #include "scip/type_tree.h"
43
44 typedef struct SCIP_ExprData SCIP_EXPRDATA; /**< expression data, e.g., coefficients */
45 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */
46
47 /** curvature types */
48 typedef enum
49 {
50 SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown or indefinite curvature */
51 SCIP_EXPRCURV_CONVEX = 1, /**< convex */
52 SCIP_EXPRCURV_CONCAVE = 2, /**< concave */
53 SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */
54 } SCIP_EXPRCURV;
55
56 /** monotonicity */
57 typedef enum
58 {
59 SCIP_MONOTONE_UNKNOWN = 0, /**< unknown or non-monotone */
60 SCIP_MONOTONE_INC = 1, /**< increasing */
61 SCIP_MONOTONE_DEC = 2, /**< decreasing */
62 SCIP_MONOTONE_CONST = SCIP_MONOTONE_INC | SCIP_MONOTONE_DEC /**< constant = increasing and decreasing */
63 } SCIP_MONOTONE;
64
65 /**@name Expression Owner */
66 /**@{ */
67
68 typedef struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA; /**< data stored by expression owner (e.g., conshdlr, nlp) in expression */
69
70 /** callback for freeing ownerdata of expression
71 *
72 * This callback is called while an expression is freed.
73 * The callback shall free the ownerdata, if any.
74 * That is, the callback is also called on expressions that only store this callback, but no ownerdata.
75 *
76 * Note, that the children of the expression have already been released when this callback is called.
77 * The callback must not try to access the expressions children.
78 *
79 * \param[in] scip SCIP main data structure
80 * \param[in] expr the expression which is freed
81 * \param[in] ownerdata the ownerdata stored in the expression
82 */
83 #define SCIP_DECL_EXPR_OWNERFREE(x) SCIP_RETCODE x(\
84 SCIP* scip, \
85 SCIP_EXPR* expr, \
86 SCIP_EXPR_OWNERDATA** ownerdata)
87
88 /** callback for printing ownerdata of expression
89 *
90 * This callback is called when printing details on an expression, e.g., SCIPdismantleExpr().
91 *
92 * \param[in] scip SCIP main data structure
93 * \param[in] expr the expression which is printed
94 * \param[in] file file to print to, or NULL for stdout
95 * \param[in] ownerdata the ownerdata stored in the expression
96 */
97 #define SCIP_DECL_EXPR_OWNERPRINT(x) SCIP_RETCODE x(\
98 SCIP* scip, \
99 FILE* file, \
100 SCIP_EXPR* expr, \
101 SCIP_EXPR_OWNERDATA* ownerdata)
102
103 /** callback for owner-specific activity evaluation
104 *
105 * This callback is called when evaluating the activity of an expression, e.g., SCIPevalActivity().
106 * The callback should ensure that activity is updated, if required, by calling SCIPsetActivity().
107 * The callback can use the activitytag in the expression to recognize whether it needs to become active.
108 *
109 * \param[in] scip SCIP main data structure
110 * \param[in] expr the expression for which activity should be updated
111 * \param[in] ownerdata the ownerdata stored in the expression
112 */
113 #define SCIP_DECL_EXPR_OWNEREVALACTIVITY(x) SCIP_RETCODE x(\
114 SCIP* scip, \
115 SCIP_EXPR* expr, \
116 SCIP_EXPR_OWNERDATA* ownerdata)
117
118 /** callback for creating ownerdata of expression
119 *
120 * This callback is called when an expression has been created.
121 * It can create data which is then stored in the expression.
122 *
123 * \param[in] scip SCIP main data structure
124 * \param[in] expr the expression that has been created
125 * \param[out] ownerdata buffer to store ownerdata that shall be stored in expression (can be NULL, initialized to NULL)
126 * \param[out] ownerfree buffer to store function to be called to free ownerdata when expression is freed (can be NULL, initialized to NULL)
127 * \param[out] ownerprint buffer to store function to be called to print ownerdata (can be NULL, initialized to NULL)
128 * \param[out] ownerevalactivity buffer to store function to be called to evaluate activity (can be NULL, initialized to NULL)
129 * \param[in] ownercreatedata data that has been passed on by future owner of expression that can be used to create ownerdata
130 */
131 #define SCIP_DECL_EXPR_OWNERCREATE(x) SCIP_RETCODE x(\
132 SCIP* scip, \
133 SCIP_EXPR* expr, \
134 SCIP_EXPR_OWNERDATA** ownerdata, \
135 SCIP_DECL_EXPR_OWNERFREE((**ownerfree)), \
136 SCIP_DECL_EXPR_OWNERPRINT((**ownerprint)), \
137 SCIP_DECL_EXPR_OWNEREVALACTIVITY((**ownerevalactivity)), \
138 void* ownercreatedata)
139
140 /** @} */ /* expression owner */
141
142 /** callback that returns bounds for a given variable as used in interval evaluation
143 *
144 * Implements a relaxation scheme for variable bounds and translates between different infinity values.
145 * Returns an interval that contains the current variable bounds, but might be (slightly) larger.
146 *
147 * \param[in] scip SCIP main data structure
148 * \param[in] var variable for which to obtain bounds
149 * \param[in] intevalvardata data that belongs to this callback
150 */
151 #define SCIP_DECL_EXPR_INTEVALVAR(x) SCIP_INTERVAL x (\
152 SCIP* scip, \
153 SCIP_VAR* var, \
154 void* intevalvardata \
155 )
156
157 /** expression mapping callback for expression copy callback
158 *
159 * The method maps an expression (in a source SCIP instance) to an expression
160 * (in a target SCIP instance) and captures the target expression.
161 *
162 * \param[in] targetscip target SCIP main data structure
163 * \param[out] targetexpr pointer to store the mapped expression, or NULL if expression shall be copied; initialized to NULL
164 * \param[in] sourcescip source SCIP main data structure
165 * \param[in] sourceexpr expression to be mapped
166 * \param[in] ownercreate callback to call when creating a new expression
167 * \param[in] ownercreatedata data for ownercreate callback
168 * \param[in] mapexprdata data of mapexpr callback
169 */
170 #define SCIP_DECL_EXPR_MAPEXPR(x) SCIP_RETCODE x (\
171 SCIP* targetscip, \
172 SCIP_EXPR** targetexpr, \
173 SCIP* sourcescip, \
174 SCIP_EXPR* sourceexpr, \
175 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
176 void* ownercreatedata, \
177 void* mapexprdata)
178
179 /**@name Expression Handler */
180 /**@{ */
181
182 typedef struct SCIP_Exprhdlr SCIP_EXPRHDLR; /**< expression handler */
183 typedef struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA; /**< expression handler data, e.g., SCIP parameter values */
184
185 /** the maximal number of estimates an expression handler can return in the INITESTIMATES callback */
186 #define SCIP_EXPR_MAXINITESTIMATES 10
187
188 /** expression handler copy callback
189 *
190 * The method should include the expression handler into a given SCIP instance.
191 * It is usually called when doing a copy of SCIP.
192 *
193 * \param[in] scip target SCIP main data structure where to include expression handler
194 * \param[in] sourceexprhdlr expression handler in source SCIP
195 */
196 #define SCIP_DECL_EXPRCOPYHDLR(x) SCIP_RETCODE x (\
197 SCIP* scip, \
198 SCIP_EXPRHDLR* sourceexprhdlr)
199
200 /** expression handler free callback
201 *
202 * Frees the data of an expression handler.
203 *
204 * \param[in] scip SCIP main data structure
205 * \param[in] exprhdlr expression handler
206 * \param[in] exprhdlrdata expression handler data to be freed
207 */
208 #define SCIP_DECL_EXPRFREEHDLR(x) SCIP_RETCODE x (\
209 SCIP* scip, \
210 SCIP_EXPRHDLR* exprhdlr, \
211 SCIP_EXPRHDLRDATA** exprhdlrdata)
212
213 /** expression data copy callback
214 *
215 * Copies the data of an expression.
216 *
217 * This method is called when creating copies of an expression within
218 * the same or between different SCIP instances. It is given the
219 * source expression, which data shall be copied. It expects
220 * that *targetexprdata will be set. This data will then be used
221 * to create a new expression.
222 *
223 * This callback must be implemented for expressions that have data.
224 *
225 * \param[in] targetscip target SCIP main data structure
226 * \param[in] targetexprhdlr expression handler in target SCIP
227 * \param[out] targetexprdata pointer to store the copied expression data
228 * \param[in] sourcescip source SCIP main data structure
229 * \param[in] sourceexpr expression in source SCIP which data is to be copied
230 */
231 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (\
232 SCIP* targetscip, \
233 SCIP_EXPRHDLR* targetexprhdlr, \
234 SCIP_EXPRDATA** targetexprdata, \
235 SCIP* sourcescip, \
236 SCIP_EXPR* sourceexpr)
237
238 /** expression data free callback
239 *
240 * Frees the data of an expression.
241 * Shall call SCIPexprSetData(expr, NULL).
242 *
243 * This callback must be implemented for expressions that have data.
244 *
245 * \param[in] scip SCIP main data structure
246 * \param[in] expr the expression which data to be freed
247 */
248 #define SCIP_DECL_EXPRFREEDATA(x) SCIP_RETCODE x (\
249 SCIP* scip, \
250 SCIP_EXPR* expr)
251
252 /** expression print callback
253 *
254 * Prints an expression.
255 * It is called while DFS-iterating over the expression at different stages, that is,
256 * when the expression is visited the first time, before each child of the expression is visited,
257 * after each child of the expression has been visited, and when the iterator leaves the expression
258 * for its parent. See also \ref SCIP_EXPRITER_DFS "expression iteration docu".
259 *
260 * \param[in] scip SCIP main data structure
261 * \param[in] expr expression which data is to be printed
262 * \param[in] stage stage of expression iteration
263 * \param[in] currentchild index of current child if in stage visitingchild or visitedchild
264 * \param[in] parentprecedence precedence of parent
265 * \param[in] file the file to print to
266 */
267 #define SCIP_DECL_EXPRPRINT(x) SCIP_RETCODE x (\
268 SCIP* scip, \
269 SCIP_EXPR* expr, \
270 SCIP_EXPRITER_STAGE stage, \
271 int currentchild, \
272 unsigned int parentprecedence, \
273 FILE* file)
274
275 /** expression parse callback
276 *
277 * Parses an expression.
278 * It is called when parsing an expression and an operator with the expr handler name is found.
279 *
280 * \param[in] scip SCIP main data structure
281 * \param[in] string string containing expression to be parse
282 * \param[in] ownercreate function to call to create ownerdata
283 * \param[in] ownercreatedata data to pass to ownercreate
284 * \param[out] endstring buffer to store the position of string after parsing
285 * \param[out] expr buffer to store the parsed expression
286 * \param[out] success buffer to store whether the parsing was successful or not
287 */
288 #define SCIP_DECL_EXPRPARSE(x) SCIP_RETCODE x (\
289 SCIP* scip, \
290 SCIP_EXPRHDLR* exprhdlr, \
291 const char* string, \
292 const char** endstring, \
293 SCIP_EXPR** expr, \
294 SCIP_Bool* success, \
295 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
296 void* ownercreatedata)
297
298 /** expression curvature detection callback
299 *
300 * The method returns whether an expression can have a desired curvature under conditions on the
301 * curvature of the children.
302 * That is, the method shall return TRUE in success and requirements on the curvature for each child
303 * which will suffice for this expression to be convex (or concave, or linear, as specified by caller)
304 * w.r.t. the current activities of all children.
305 * It can return "unknown" for a child's curvature if its curvature does not matter (though that's
306 * rarely the case).
307 *
308 * It can be assumes that the activity evaluation of the expression has been called before
309 * and that the expression has been simplified.
310 *
311 * \param[in] scip SCIP main data structure
312 * \param[in] expr expression to check the curvature for
313 * \param[in] exprcurvature desired curvature of this expression
314 * \param[out] success buffer to store whether the desired curvature was obtained
315 * \param[out] childcurv array to store required curvature for each child
316 */
317 #define SCIP_DECL_EXPRCURVATURE(x) SCIP_RETCODE x (\
318 SCIP* scip, \
319 SCIP_EXPR* expr, \
320 SCIP_EXPRCURV exprcurvature, \
321 SCIP_Bool* success, \
322 SCIP_EXPRCURV* childcurv)
323
324 /** expression monotonicity detection callback
325 *
326 * The method computes the monotonicity of an expression with respect to a given child.
327 *
328 * \param[in] scip SCIP main data structure
329 * \param[in] expr expression to check the monotonicity for
330 * \param[in] childidx index of the considered child expression
331 * \param[out] result buffer to store the monotonicity
332 */
333 #define SCIP_DECL_EXPRMONOTONICITY(x) SCIP_RETCODE x (\
334 SCIP* scip, \
335 SCIP_EXPR* expr, \
336 int childidx, \
337 SCIP_MONOTONE* result)
338
339 /** expression integrality detection callback
340 *
341 * The method checks whether an expression evaluates always to an integral value in a feasible solution.
342 * Usually uses SCIPexprIsIntegral() to check whether children evaluate to an integral value.
343 *
344 * \param[in] scip SCIP main data structure
345 * \param[in] expr expression to check the integrality for
346 * \param[out] isintegral buffer to store whether expr is integral
347 */
348 #define SCIP_DECL_EXPRINTEGRALITY(x) SCIP_RETCODE x (\
349 SCIP* scip, \
350 SCIP_EXPR* expr, \
351 SCIP_Bool* isintegral)
352
353 /** expression hash callback
354 *
355 * The method hashes an expression by taking the hashes of its children into account.
356 *
357 * \param[in] scip SCIP main data structure
358 * \param[in] expr expression to be hashed
359 * \param[out] hashkey buffer to store the hash value
360 * \param[in] childrenhashes array with hash values of children
361 */
362 #define SCIP_DECL_EXPRHASH(x) SCIP_RETCODE x (\
363 SCIP* scip, \
364 SCIP_EXPR* expr, \
365 unsigned int* hashkey, \
366 unsigned int* childrenhashes)
367
368 /** expression compare callback
369 *
370 * the method receives two expressions, expr1 and expr2. Must return
371 * -1 if expr1 < expr2,
372 * 0 if expr1 = expr2, or
373 * 1 if expr1 > expr2.
374 *
375 * \param[in] scip SCIP main data structure
376 * \param[in] expr1 first expression in comparison
377 * \param[in] expr2 second expression in comparison
378 */
379 #define SCIP_DECL_EXPRCOMPARE(x) int x (\
380 SCIP* scip, \
381 SCIP_EXPR* expr1, \
382 SCIP_EXPR* expr2)
383
384 /** expression (point-) evaluation callback
385 *
386 * The method evaluates an expression by taking the values of its children into account.
387 *
388 * \param[in] scip SCIP main data structure
389 * \param[in] expr expression to be evaluated
390 * \param[out] val buffer where to store value
391 * \param[in] sol solution that is evaluated (can be NULL)
392 */
393 #define SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (\
394 SCIP* scip, \
395 SCIP_EXPR* expr, \
396 SCIP_Real* val, \
397 SCIP_SOL* sol)
398
399 /** backward derivative evaluation callback
400 *
401 * The method should compute the partial derivative of expr w.r.t. its child at childidx.
402 * That is, it should return
403 * \f[
404 * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}}
405 * \f]
406 *
407 * \param[in] scip SCIP main data structure
408 * \param[in] expr expression to be differentiated
409 * \param[in] childidx index of the child
410 * \param[out] val buffer to store the partial derivative w.r.t. the childidx-th children
411 */
412 #define SCIP_DECL_EXPRBWDIFF(x) SCIP_RETCODE x (\
413 SCIP* scip, \
414 SCIP_EXPR* expr, \
415 int childidx, \
416 SCIP_Real* val)
417
418 /** forward derivative evaluation callback
419 *
420 * The method should evaluate the directional derivative of expr.
421 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$
422 * are the children of the expr.
423 * The directional derivative is evaluated at the point
424 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
425 * in the direction given by direction.
426 *
427 * This method should return
428 * \f[
429 * \sum_{i = 1}^n \frac{\partial \text{expr}}{\partial c_i} D_u c_i,
430 * \f]
431 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
432 * which can be accessed via SCIPexprGetDot().
433 *
434 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
435 *
436 * \param[in] scip SCIP main data structure
437 * \param[in] expr expression to be differentiated
438 * \param[out] dot buffer to store derivative value
439 * \param[in] direction direction of the derivative (useful only for var expressions)
440 */
441 #define SCIP_DECL_EXPRFWDIFF(x) SCIP_RETCODE x (\
442 SCIP* scip, \
443 SCIP_EXPR* expr, \
444 SCIP_Real* dot, \
445 SCIP_SOL* direction)
446
447 /** derivative evaluation callback for Hessian directions (backward over forward)
448 *
449 * The method computes the total derivative, w.r.t its children, of the partial derivative of expr w.r.t childidx.
450 * Equivalently, it computes the partial derivative w.r.t childidx of the total derivative.
451 *
452 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$
453 * are the children of the expr.
454 * The directional derivative is evaluated at the point
455 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
456 * in the direction given by direction.
457 *
458 * This method should return
459 * \f[
460 * \sum_{i = 1}^n \frac{\partial^2 \text{expr}}{\partial c_i} \partial c_{\text{childidx}} D_u c_i,
461 * \f]
462 *
463 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
464 * which can be accessed via SCIPexprGetDot.
465 *
466 * Thus, if \f$ n = 1 \f$ (i.e. if expr represents an univariate operator), the method should return
467 * \f[
468 * \text{expr}^{\prime \prime}(\text{SCIPexprGetEvalValue}(c)) D_u c.
469 * \f]
470 *
471 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
472 *
473 * \param[in] scip SCIP main data structure
474 * \param[in] expr expression to be evaluated
475 * \param[in] childidx index of the child
476 * \param[out] bardot buffer to store derivative value
477 * \param[in] direction direction of the derivative (useful only for var expressions)
478 */
479 #define SCIP_DECL_EXPRBWFWDIFF(x) SCIP_RETCODE x (\
480 SCIP* scip, \
481 SCIP_EXPR* expr, \
482 int childidx, \
483 SCIP_Real* bardot, \
484 SCIP_SOL* direction)
485
486 /** expression (interval-) evaluation callback
487 *
488 * The method evaluates an expression by taking the intervals of its children into account.
489 *
490 * \param[in] scip SCIP main data structure
491 * \param[in] expr expression to be evaluated
492 * \param[out] interval buffer where to store interval
493 * \param[in] intevalvar callback to be called when interval evaluating a variable
494 * \param[in] intevalvardata data to be passed to intevalvar callback
495 */
496 #define SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (\
497 SCIP* scip, \
498 SCIP_EXPR* expr, \
499 SCIP_INTERVAL* interval, \
500 SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), \
501 void* intevalvardata)
502
503 /** expression under/overestimation callback
504 *
505 * The method tries to compute a linear under- or overestimator that is as tight as possible
506 * at a given point. The estimator must be valid w.r.t. the bounds given by localbounds.
507 * If the value of the estimator in the reference point is smaller (larger) than targetvalue
508 * when underestimating (overestimating), then no estimator needs to be computed.
509 * Note, that targetvalue can be infinite if any estimator will be accepted.
510 * If successful, it shall store the coefficient of the i-th child in entry coefs[i] and
511 * the constant part in constant.
512 * If the estimator is also valid w.r.t. the bounds given by globalbounds, then *islocal shall
513 * be set to FALSE.
514 * The callback shall indicate in branchcand[i] whether branching on the i-th child would improve
515 * the estimator. It can be assumed that branchcand[i] has been initialized to TRUE for all children.
516 *
517 * \param[in] scip SCIP main data structure
518 * \param[in] expr expression
519 * \param[in] localbounds current bounds for children
520 * \param[in] globalbounds global bounds for children
521 * \param[in] refpoint values for children in the reference point where to estimate
522 * \param[in] overestimate whether the expression needs to be over- or underestimated
523 * \param[in] targetvalue a value that the estimator shall exceed, can be +/-infinity
524 * \param[out] coefs array to store coefficients of estimator
525 * \param[out] constant buffer to store constant part of estimator
526 * \param[out] islocal buffer to store whether estimator is valid locally only
527 * \param[out] success buffer to indicate whether an estimator could be computed
528 * \param[out] branchcand array to indicate which children to consider for branching
529 */
530 #define SCIP_DECL_EXPRESTIMATE(x) SCIP_RETCODE x (\
531 SCIP* scip, \
532 SCIP_EXPR* expr, \
533 SCIP_INTERVAL* localbounds, \
534 SCIP_INTERVAL* globalbounds, \
535 SCIP_Real* refpoint, \
536 SCIP_Bool overestimate, \
537 SCIP_Real targetvalue, \
538 SCIP_Real* coefs, \
539 SCIP_Real* constant, \
540 SCIP_Bool* islocal, \
541 SCIP_Bool* success, \
542 SCIP_Bool* branchcand)
543
544 /** expression initial under/overestimation callback
545 *
546 * The method tries to compute a few linear under- or overestimator that approximate the
547 * behavior of the expression. The estimator must be valid w.r.t. the bounds given by bounds.
548 * These estimators may be used to initialize a linear relaxation.
549 * The callback shall return the number of computed estimators in nreturned,
550 * store the coefficient of the i-th child for the j-th estimator in entry coefs[j][i],
551 * and store the constant part for the j-th estimator in constant[j].
552 *
553 * \param[in] scip SCIP main data structure
554 * \param[in] expr expression
555 * \param[in] bounds bounds for children
556 * \param[in] overestimate whether the expression shall be overestimated or underestimated
557 * \param[out] coefs buffer to store coefficients of computed estimators
558 * \param[out] constant buffer to store constant of computed estimators
559 * \param[out] nreturned buffer to store number of estimators that have been computed
560 */
561 #define SCIP_DECL_EXPRINITESTIMATES(x) SCIP_RETCODE x ( \
562 SCIP* scip, \
563 SCIP_EXPR* expr, \
564 SCIP_INTERVAL* bounds, \
565 SCIP_Bool overestimate, \
566 SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], \
567 SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], \
568 int* nreturned)
569
570 /** expression simplify callback
571 *
572 * The method shall try to simplify an expression by applying algebraic transformations
573 * and return the simplified expression.
574 * It can assume that children have been simplified.
575 * If no simplification is possible, then shall set *simplifiedexpr to expr and capture *simplifiedexpr.
576 *
577 * \param[in] scip SCIP main data structure
578 * \param[in] expr expression to simplify
579 * \param[in] ownercreate function to call to create ownerdata
580 * \param[in] ownercreatedata data to pass to ownercreate
581 * \param[out] simplifiedexpr buffer to store the simplified expression
582 */
583 #define SCIP_DECL_EXPRSIMPLIFY(x) SCIP_RETCODE x (\
584 SCIP* scip, \
585 SCIP_EXPR* expr, \
586 SCIP_EXPR** simplifiedexpr, \
587 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
588 void* ownercreatedata)
589
590 /** expression callback for reverse propagation
591 *
592 * The method propagates given bounds over the children of an expression.
593 * Shall compute an interval overestimate on
594 * \f[
595 * \{ x_i : \text{expr}(c_1,\ldots,c_{i-1},x_i,c_{i+1},\ldots,c_n) \in \text{bounds} \}
596 * \f]
597 * for each child i and store it in childrenbounds[i].
598 * The initial intervals \f$c_i, i=1,\ldots,n,\f$ are given by childrenbounds, too.
599 *
600 * \param[in] scip SCIP main data structure
601 * \param[in] expr expression
602 * \param[in] bounds the bounds on the expression that should be propagated
603 * \param[in,out] childrenbounds array to store computed bounds for children, initialized with current activity
604 * \param[out] infeasible buffer to store whether a children bounds were propagated to an empty interval
605 */
606 #define SCIP_DECL_EXPRREVERSEPROP(x) SCIP_RETCODE x (\
607 SCIP* scip, \
608 SCIP_EXPR* expr, \
609 SCIP_INTERVAL bounds, \
610 SCIP_INTERVAL* childrenbounds, \
611 SCIP_Bool* infeasible)
612
613 /** @} */ /* expression handler */
614
615
616
617 /** @name Expression iterator
618 * @{
619 */
620
621 /** maximal number of iterators that can be active on an expression graph concurrently
622 *
623 * How often an expression graph iteration can be started within an active iteration, plus one.
624 */
625 #define SCIP_EXPRITER_MAXNACTIVE 5
626
627 /* stages of expression DFS iteration */
628 #define SCIP_EXPRITER_ENTEREXPR 1u /**< an expression is visited the first time (before any of its children are visited) */
629 #define SCIP_EXPRITER_VISITINGCHILD 2u /**< a child of an expression is to be visited */
630 #define SCIP_EXPRITER_VISITEDCHILD 4u /**< a child of an expression has been visited */
631 #define SCIP_EXPRITER_LEAVEEXPR 8u /**< an expression is to be left (all of its children have been processed) */
632 #define SCIP_EXPRITER_ALLSTAGES (SCIP_EXPRITER_ENTEREXPR | SCIP_EXPRITER_VISITINGCHILD | SCIP_EXPRITER_VISITEDCHILD | SCIP_EXPRITER_LEAVEEXPR)
633
634 /** stage of DFS iterator */
635 typedef unsigned int SCIP_EXPRITER_STAGE;
636
637 /** user data storage type for expression iteration */
638 typedef union
639 {
640 SCIP_Real realval; /**< a floating-point value */
641 int intval; /**< an integer value */
642 int intvals[2]; /**< two integer values */
643 unsigned int uintval; /**< an unsigned integer value */
644 void* ptrval; /**< a pointer */
645 } SCIP_EXPRITER_USERDATA;
646
647 /** mode for expression iterator */
648 typedef enum
649 {
650 SCIP_EXPRITER_RTOPOLOGIC, /**< reverse topological order */
651 SCIP_EXPRITER_BFS, /**< breadth-first search */
652 SCIP_EXPRITER_DFS /**< depth-first search */
653 } SCIP_EXPRITER_TYPE;
654
655 typedef struct SCIP_ExprIterData SCIP_EXPRITERDATA; /**< expression iterator data of a specific expression */
656 typedef struct SCIP_ExprIter SCIP_EXPRITER; /**< expression iterator */
657
658 /** @} */ /* expression iterator */
659
660 /** @name Expression printing
661 * @{
662 */
663
664 #define SCIP_EXPRPRINT_EXPRSTRING 0x1u /**< print the math. function that the expression represents (e.g., "c0+c1") */
665 #define SCIP_EXPRPRINT_EXPRHDLR 0x2u /**< print expression handler name */
666 #define SCIP_EXPRPRINT_NUSES 0x4u /**< print number of uses (reference counting) */
667 #define SCIP_EXPRPRINT_EVALVALUE 0x8u /**< print evaluation value */
668 #define SCIP_EXPRPRINT_EVALTAG 0x18u /**< print evaluation value and tag */
669 #define SCIP_EXPRPRINT_ACTIVITY 0x20u /**< print activity value */
670 #define SCIP_EXPRPRINT_ACTIVITYTAG 0x60u /**< print activity value and corresponding tag */
671 #define SCIP_EXPRPRINT_OWNER 0x80u /**< print ownerdata */
672
673 /** print everything */
674 #define SCIP_EXPRPRINT_ALL SCIP_EXPRPRINT_EXPRSTRING | SCIP_EXPRPRINT_EXPRHDLR | SCIP_EXPRPRINT_NUSES | SCIP_EXPRPRINT_EVALTAG | SCIP_EXPRPRINT_ACTIVITYTAG | SCIP_EXPRPRINT_OWNER
675
676 typedef unsigned int SCIP_EXPRPRINT_WHAT; /**< exprprint bitflags */
677 typedef struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA; /**< data when printing an expression */
678
679 /** @} */
680
681
682 #endif /* SCIP_TYPE_EXPR_H_ */
683