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-2022 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  * See also \ref EXPRCOPYHDLR.
197  */
198 #define SCIP_DECL_EXPRCOPYHDLR(x) SCIP_RETCODE x (\
199  SCIP* scip, \
200  SCIP_EXPRHDLR* sourceexprhdlr)
201 
202 /** expression handler free callback
203  *
204  * Frees the data of an expression handler.
205  *
206  * \param[in] scip SCIP main data structure
207  * \param[in] exprhdlr expression handler
208  * \param[in] exprhdlrdata expression handler data to be freed
209  *
210  * See also \ref EXPRFREEHDLR.
211  */
212 #define SCIP_DECL_EXPRFREEHDLR(x) SCIP_RETCODE x (\
213  SCIP* scip, \
214  SCIP_EXPRHDLR* exprhdlr, \
215  SCIP_EXPRHDLRDATA** exprhdlrdata)
216 
217 /** expression data copy callback
218  *
219  * Copies the data of an expression.
220  *
221  * This method is called when creating copies of an expression within
222  * the same or between different SCIP instances. It is given the
223  * source expression, which data shall be copied. It expects
224  * that *targetexprdata will be set. This data will then be used
225  * to create a new expression.
226  *
227  * This callback must be implemented for expressions that have data.
228  *
229  * \param[in] targetscip target SCIP main data structure
230  * \param[in] targetexprhdlr expression handler in target SCIP
231  * \param[out] targetexprdata pointer to store the copied expression data
232  * \param[in] sourcescip source SCIP main data structure
233  * \param[in] sourceexpr expression in source SCIP which data is to be copied
234  *
235  * See also \ref EXPRCOPYDATA.
236  */
237 #define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (\
238  SCIP* targetscip, \
239  SCIP_EXPRHDLR* targetexprhdlr, \
240  SCIP_EXPRDATA** targetexprdata, \
241  SCIP* sourcescip, \
242  SCIP_EXPR* sourceexpr)
243 
244 /** expression data free callback
245  *
246  * Frees the data of an expression.
247  * Shall call SCIPexprSetData(expr, NULL).
248  *
249  * This callback must be implemented for expressions that have data.
250  *
251  * \param[in] scip SCIP main data structure
252  * \param[in] expr the expression which data to be freed
253  *
254  * See also \ref EXPRFREEDATA.
255  */
256 #define SCIP_DECL_EXPRFREEDATA(x) SCIP_RETCODE x (\
257  SCIP* scip, \
258  SCIP_EXPR* expr)
259 
260 /** expression print callback
261  *
262  * Prints an expression.
263  * It is called while DFS-iterating over the expression at different stages, that is,
264  * when the expression is visited the first time, before each child of the expression is visited,
265  * after each child of the expression has been visited, and when the iterator leaves the expression
266  * for its parent. See also \ref SCIP_EXPRITER_DFS "expression iteration docu".
267  *
268  * \param[in] scip SCIP main data structure
269  * \param[in] expr expression which data is to be printed
270  * \param[in] stage stage of expression iteration
271  * \param[in] currentchild index of current child if in stage visitingchild or visitedchild
272  * \param[in] parentprecedence precedence of parent
273  * \param[in] file the file to print to
274  *
275  * See also \ref EXPRPRINT.
276  */
277 #define SCIP_DECL_EXPRPRINT(x) SCIP_RETCODE x (\
278  SCIP* scip, \
279  SCIP_EXPR* expr, \
280  SCIP_EXPRITER_STAGE stage, \
281  int currentchild, \
282  unsigned int parentprecedence, \
283  FILE* file)
284 
285 /** expression parse callback
286  *
287  * Parses an expression.
288  * It is called when parsing an expression and an operator with the expr handler name is found.
289  *
290  * \param[in] scip SCIP main data structure
291  * \param[in] string string containing expression to be parse
292  * \param[in] ownercreate function to call to create ownerdata
293  * \param[in] ownercreatedata data to pass to ownercreate
294  * \param[out] endstring buffer to store the position of string after parsing
295  * \param[out] expr buffer to store the parsed expression
296  * \param[out] success buffer to store whether the parsing was successful or not
297  *
298  * See also \ref EXPRPARSE.
299  */
300 #define SCIP_DECL_EXPRPARSE(x) SCIP_RETCODE x (\
301  SCIP* scip, \
302  SCIP_EXPRHDLR* exprhdlr, \
303  const char* string, \
304  const char** endstring, \
305  SCIP_EXPR** expr, \
306  SCIP_Bool* success, \
307  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
308  void* ownercreatedata)
309 
310 /** expression curvature detection callback
311  *
312  * The method returns whether an expression can have a desired curvature under conditions on the
313  * curvature of the children.
314  * That is, the method shall return TRUE in success and requirements on the curvature for each child
315  * which will suffice for this expression to be convex (or concave, or linear, as specified by caller)
316  * w.r.t. the current activities of all children.
317  * It can return "unknown" for a child's curvature if its curvature does not matter (though that's
318  * rarely the case).
319  *
320  * \param[in] scip SCIP main data structure
321  * \param[in] expr expression to check the curvature for
322  * \param[in] exprcurvature desired curvature of this expression
323  * \param[out] success buffer to store whether the desired curvature was obtained
324  * \param[out] childcurv array to store required curvature for each child
325  *
326  * See also \ref EXPRCURVATURE.
327  */
328 #define SCIP_DECL_EXPRCURVATURE(x) SCIP_RETCODE x (\
329  SCIP* scip, \
330  SCIP_EXPR* expr, \
331  SCIP_EXPRCURV exprcurvature, \
332  SCIP_Bool* success, \
333  SCIP_EXPRCURV* childcurv)
334 
335 /** expression monotonicity detection callback
336  *
337  * The method computes the monotonicity of an expression with respect to a given child.
338  *
339  * \param[in] scip SCIP main data structure
340  * \param[in] expr expression to check the monotonicity for
341  * \param[in] childidx index of the considered child expression
342  * \param[out] result buffer to store the monotonicity
343  *
344  * See also \ref EXPRMONOTONICITY.
345  */
346 #define SCIP_DECL_EXPRMONOTONICITY(x) SCIP_RETCODE x (\
347  SCIP* scip, \
348  SCIP_EXPR* expr, \
349  int childidx, \
350  SCIP_MONOTONE* result)
351 
352 /** expression integrality detection callback
353  *
354  * The method checks whether an expression evaluates always to an integral value in a feasible solution.
355  * Usually uses SCIPexprIsIntegral() to check whether children evaluate to an integral value.
356  *
357  * \param[in] scip SCIP main data structure
358  * \param[in] expr expression to check the integrality for
359  * \param[out] isintegral buffer to store whether expr is integral
360  *
361  * See also \ref EXPRINTEGRALITY.
362  */
363 #define SCIP_DECL_EXPRINTEGRALITY(x) SCIP_RETCODE x (\
364  SCIP* scip, \
365  SCIP_EXPR* expr, \
366  SCIP_Bool* isintegral)
367 
368 /** expression hash callback
369  *
370  * The method hashes an expression by taking the hashes of its children into account.
371  *
372  * \param[in] scip SCIP main data structure
373  * \param[in] expr expression to be hashed
374  * \param[out] hashkey buffer to store the hash value
375  * \param[in] childrenhashes array with hash values of children
376  *
377  * See also \ref EXPRHASH.
378  */
379 #define SCIP_DECL_EXPRHASH(x) SCIP_RETCODE x (\
380  SCIP* scip, \
381  SCIP_EXPR* expr, \
382  unsigned int* hashkey, \
383  unsigned int* childrenhashes)
384 
385 /** expression compare callback
386  *
387  * the method receives two expressions, expr1 and expr2. Must return
388  * -1 if expr1 < expr2, or
389  * 0 if expr1 = expr2, or
390  * 1 if expr1 > expr2.
391  *
392  * \param[in] scip SCIP main data structure
393  * \param[in] expr1 first expression in comparison
394  * \param[in] expr2 second expression in comparison
395  *
396  * See also \ref EXPRCOMPARE.
397  */
398 #define SCIP_DECL_EXPRCOMPARE(x) int x (\
399  SCIP* scip, \
400  SCIP_EXPR* expr1, \
401  SCIP_EXPR* expr2)
402 
403 /** expression (point-) evaluation callback
404  *
405  * The method evaluates an expression by taking the values of its children into account.
406  *
407  * \param[in] scip SCIP main data structure
408  * \param[in] expr expression to be evaluated
409  * \param[out] val buffer where to store value
410  * \param[in] sol solution that is evaluated (can be NULL)
411  *
412  * See also \ref EXPREVAL.
413  */
414 #define SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (\
415  SCIP* scip, \
416  SCIP_EXPR* expr, \
417  SCIP_Real* val, \
418  SCIP_SOL* sol)
419 
420 /** backward derivative evaluation callback
421  *
422  * The method should compute the partial derivative of expr w.r.t. its child at childidx.
423  * That is, it should return
424  * \f[
425  * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}}
426  * \f]
427  *
428  * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
429  *
430  * \param[in] scip SCIP main data structure
431  * \param[in] expr expression to be differentiated
432  * \param[in] childidx index of the child
433  * \param[out] val buffer to store the partial derivative w.r.t. the childidx-th children
434  *
435  * See also \ref EXPRBWDIFF.
436  */
437 #define SCIP_DECL_EXPRBWDIFF(x) SCIP_RETCODE x (\
438  SCIP* scip, \
439  SCIP_EXPR* expr, \
440  int childidx, \
441  SCIP_Real* val)
442 
443 /** forward derivative evaluation callback
444  *
445  * The method should evaluate the directional derivative of expr.
446  * 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$
447  * are the children of the expr.
448  * The directional derivative is evaluated at the point
449  * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
450  * in the direction given by direction.
451  *
452  * This method should return
453  * \f[
454  * \sum_{i = 1}^n \frac{\partial \text{expr}}{\partial c_i} D_u c_i,
455  * \f]
456  * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
457  * which can be accessed via SCIPexprGetDot().
458  *
459  * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
460  *
461  * \param[in] scip SCIP main data structure
462  * \param[in] expr expression to be differentiated
463  * \param[out] dot buffer to store derivative value
464  * \param[in] direction direction of the derivative (useful only for var expressions)
465  *
466  * See also \ref EXPRFWDIFF.
467  */
468 #define SCIP_DECL_EXPRFWDIFF(x) SCIP_RETCODE x (\
469  SCIP* scip, \
470  SCIP_EXPR* expr, \
471  SCIP_Real* dot, \
472  SCIP_SOL* direction)
473 
474 /** derivative evaluation callback for Hessian directions (backward over forward)
475  *
476  * The method computes the total derivative, w.r.t. its children, of the partial derivative of expr w.r.t. childidx.
477  * Equivalently, it computes the partial derivative w.r.t. childidx of the total derivative.
478  *
479  * 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$
480  * are the children of the expr.
481  * The directional derivative is evaluated at the point
482  * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
483  * in the direction given by direction.
484  *
485  * This method should return
486  * \f[
487  * \sum_{i = 1}^n \frac{\partial^2 \text{expr}}{\partial c_i} \partial c_{\text{childidx}} D_u c_i,
488  * \f]
489  *
490  * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
491  * which can be accessed via SCIPexprGetDot().
492  *
493  * Thus, if \f$ n = 1 \f$ (i.e. if expr represents an univariate operator), the method should return
494  * \f[
495  * \text{expr}^{\prime \prime}(\text{SCIPexprGetEvalValue}(c)) D_u c.
496  * \f]
497  *
498  * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
499  *
500  * \param[in] scip SCIP main data structure
501  * \param[in] expr expression to be evaluated
502  * \param[in] childidx index of the child
503  * \param[out] bardot buffer to store derivative value
504  * \param[in] direction direction of the derivative (useful only for var expressions)
505  *
506  * See also \ref EXPRBWFWDIFF.
507  */
508 #define SCIP_DECL_EXPRBWFWDIFF(x) SCIP_RETCODE x (\
509  SCIP* scip, \
510  SCIP_EXPR* expr, \
511  int childidx, \
512  SCIP_Real* bardot, \
513  SCIP_SOL* direction)
514 
515 /** expression (interval-) evaluation callback
516  *
517  * The method evaluates an expression by taking the intervals of its children into account.
518  *
519  * \param[in] scip SCIP main data structure
520  * \param[in] expr expression to be evaluated
521  * \param[out] interval buffer where to store interval
522  * \param[in] intevalvar callback to be called when interval evaluating a variable
523  * \param[in] intevalvardata data to be passed to intevalvar callback
524  *
525  * See also \ref EXPRINTEVAL.
526  */
527 #define SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (\
528  SCIP* scip, \
529  SCIP_EXPR* expr, \
530  SCIP_INTERVAL* interval, \
531  SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), \
532  void* intevalvardata)
533 
534 /** expression under/overestimation callback
535  *
536  * The method tries to compute a linear under- or overestimator that is as tight as possible
537  * at a given point. The estimator must be valid w.r.t. the bounds given by localbounds.
538  * If the value of the estimator in the reference point is smaller (larger) than targetvalue
539  * when underestimating (overestimating), then no estimator needs to be computed.
540  * Note, that targetvalue can be infinite if any estimator will be accepted.
541  * If successful, it shall store the coefficient of the i-th child in entry coefs[i] and
542  * the constant part in constant.
543  * If the estimator is also valid w.r.t. the bounds given by globalbounds, then *islocal shall
544  * be set to FALSE.
545  * The callback shall indicate in branchcand[i] whether branching on the i-th child would improve
546  * the estimator. It can be assumed that branchcand[i] has been initialized to TRUE for all children.
547  *
548  * \param[in] scip SCIP main data structure
549  * \param[in] expr expression
550  * \param[in] localbounds current bounds for children
551  * \param[in] globalbounds global bounds for children
552  * \param[in] refpoint values for children in the reference point where to estimate
553  * \param[in] overestimate whether the expression needs to be over- or underestimated
554  * \param[in] targetvalue a value that the estimator shall exceed, can be +/-infinity
555  * \param[out] coefs array to store coefficients of estimator
556  * \param[out] constant buffer to store constant part of estimator
557  * \param[out] islocal buffer to store whether estimator is valid locally only
558  * \param[out] success buffer to indicate whether an estimator could be computed
559  * \param[out] branchcand array to indicate which children to consider for branching
560  *
561  * See also \ref EXPRESTIMATE.
562  */
563 #define SCIP_DECL_EXPRESTIMATE(x) SCIP_RETCODE x (\
564  SCIP* scip, \
565  SCIP_EXPR* expr, \
566  SCIP_INTERVAL* localbounds, \
567  SCIP_INTERVAL* globalbounds, \
568  SCIP_Real* refpoint, \
569  SCIP_Bool overestimate, \
570  SCIP_Real targetvalue, \
571  SCIP_Real* coefs, \
572  SCIP_Real* constant, \
573  SCIP_Bool* islocal, \
574  SCIP_Bool* success, \
575  SCIP_Bool* branchcand)
576 
577 /** expression initial under/overestimation callback
578  *
579  * The method tries to compute a few linear under- or overestimator that approximate the
580  * behavior of the expression. The estimator must be valid w.r.t. the bounds given by bounds.
581  * These estimators may be used to initialize a linear relaxation.
582  * The callback shall return the number of computed estimators in nreturned,
583  * store the coefficient of the i-th child for the j-th estimator in entry coefs[j][i],
584  * and store the constant part for the j-th estimator in constant[j].
585  *
586  * \param[in] scip SCIP main data structure
587  * \param[in] expr expression
588  * \param[in] bounds bounds for children
589  * \param[in] overestimate whether the expression shall be overestimated or underestimated
590  * \param[out] coefs buffer to store coefficients of computed estimators
591  * \param[out] constant buffer to store constant of computed estimators
592  * \param[out] nreturned buffer to store number of estimators that have been computed
593  *
594  * See also \ref EXPRINITESTIMATES.
595  */
596 #define SCIP_DECL_EXPRINITESTIMATES(x) SCIP_RETCODE x ( \
597  SCIP* scip, \
598  SCIP_EXPR* expr, \
599  SCIP_INTERVAL* bounds, \
600  SCIP_Bool overestimate, \
601  SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], \
602  SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], \
603  int* nreturned)
604 
605 /** expression simplify callback
606  *
607  * The method shall try to simplify an expression by applying algebraic transformations
608  * and return the simplified expression.
609  * It can assume that children have been simplified.
610  * If no simplification is possible, then shall set *simplifiedexpr to expr and capture *simplifiedexpr.
611  *
612  * \param[in] scip SCIP main data structure
613  * \param[in] expr expression to simplify
614  * \param[in] ownercreate function to call to create ownerdata
615  * \param[in] ownercreatedata data to pass to ownercreate
616  * \param[out] simplifiedexpr buffer to store the simplified expression
617  *
618  * See also \ref EXPRSIMPLIFY and SCIPsimplifyExpr().
619  */
620 #define SCIP_DECL_EXPRSIMPLIFY(x) SCIP_RETCODE x (\
621  SCIP* scip, \
622  SCIP_EXPR* expr, \
623  SCIP_EXPR** simplifiedexpr, \
624  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
625  void* ownercreatedata)
626 
627 /** expression callback for reverse propagation
628  *
629  * The method propagates given bounds over the children of an expression.
630  * Shall compute an interval overestimate on
631  * \f[
632  * \{ x_i : \text{expr}(c_1,\ldots,c_{i-1},x_i,c_{i+1},\ldots,c_n) \in \text{bounds} \}
633  * \f]
634  * for each child i and store it in childrenbounds[i].
635  * The initial intervals \f$c_i, i=1,\ldots,n,\f$ are given by childrenbounds, too.
636  *
637  * \param[in] scip SCIP main data structure
638  * \param[in] expr expression
639  * \param[in] bounds the bounds on the expression that should be propagated
640  * \param[in,out] childrenbounds array to store computed bounds for children, initialized with current activity
641  * \param[out] infeasible buffer to store whether a children bounds were propagated to an empty interval
642  *
643  * See also \ref EXPRREVERSEPROP.
644  */
645 #define SCIP_DECL_EXPRREVERSEPROP(x) SCIP_RETCODE x (\
646  SCIP* scip, \
647  SCIP_EXPR* expr, \
648  SCIP_INTERVAL bounds, \
649  SCIP_INTERVAL* childrenbounds, \
650  SCIP_Bool* infeasible)
651 
652 /** @} */ /* expression handler */
653 
654 
655 
656 /** @name Expression iterator
657  * @{
658  */
659 
660 /** maximal number of iterators that can be active on an expression graph concurrently
661  *
662  * How often an expression graph iteration can be started within an active iteration, plus one.
663  */
664 #define SCIP_EXPRITER_MAXNACTIVE 5
665 
666 /* stages of expression DFS iteration */
667 #define SCIP_EXPRITER_ENTEREXPR 1u /**< an expression is visited the first time (before any of its children are visited) */
668 #define SCIP_EXPRITER_VISITINGCHILD 2u /**< a child of an expression is to be visited */
669 #define SCIP_EXPRITER_VISITEDCHILD 4u /**< a child of an expression has been visited */
670 #define SCIP_EXPRITER_LEAVEEXPR 8u /**< an expression is to be left (all of its children have been processed) */
671 #define SCIP_EXPRITER_ALLSTAGES (SCIP_EXPRITER_ENTEREXPR | SCIP_EXPRITER_VISITINGCHILD | SCIP_EXPRITER_VISITEDCHILD | SCIP_EXPRITER_LEAVEEXPR)
672 
673 /** stage of DFS iterator */
674 typedef unsigned int SCIP_EXPRITER_STAGE;
675 
676 /** user data storage type for expression iteration */
677 typedef union
678 {
679  SCIP_Real realval; /**< a floating-point value */
680  int intval; /**< an integer value */
681  int intvals[2]; /**< two integer values */
682  unsigned int uintval; /**< an unsigned integer value */
683  void* ptrval; /**< a pointer */
684 } SCIP_EXPRITER_USERDATA;
685 
686 /** mode for expression iterator */
687 typedef enum
688 {
689  SCIP_EXPRITER_RTOPOLOGIC, /**< reverse topological order */
690  SCIP_EXPRITER_BFS, /**< breadth-first search */
691  SCIP_EXPRITER_DFS /**< depth-first search */
692 } SCIP_EXPRITER_TYPE;
693 
694 typedef struct SCIP_ExprIterData SCIP_EXPRITERDATA; /**< expression iterator data of a specific expression */
695 typedef struct SCIP_ExprIter SCIP_EXPRITER; /**< expression iterator */
696 
697 /** @} */ /* expression iterator */
698 
699 /** @name Expression printing
700  * @{
701  */
702 
703 #define SCIP_EXPRPRINT_EXPRSTRING 0x1u /**< print the math. function that the expression represents (e.g., "c0+c1") */
704 #define SCIP_EXPRPRINT_EXPRHDLR 0x2u /**< print expression handler name */
705 #define SCIP_EXPRPRINT_NUSES 0x4u /**< print number of uses (reference counting) */
706 #define SCIP_EXPRPRINT_EVALVALUE 0x8u /**< print evaluation value */
707 #define SCIP_EXPRPRINT_EVALTAG 0x18u /**< print evaluation value and tag */
708 #define SCIP_EXPRPRINT_ACTIVITY 0x20u /**< print activity value */
709 #define SCIP_EXPRPRINT_ACTIVITYTAG 0x60u /**< print activity value and corresponding tag */
710 #define SCIP_EXPRPRINT_OWNER 0x80u /**< print ownerdata */
711 
712 /** print everything */
713 #define SCIP_EXPRPRINT_ALL SCIP_EXPRPRINT_EXPRSTRING | SCIP_EXPRPRINT_EXPRHDLR | SCIP_EXPRPRINT_NUSES | SCIP_EXPRPRINT_EVALTAG | SCIP_EXPRPRINT_ACTIVITYTAG | SCIP_EXPRPRINT_OWNER
714 
715 typedef unsigned int SCIP_EXPRPRINT_WHAT; /**< exprprint bitflags */
716 typedef struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA; /**< data when printing an expression */
717 
718 /** @} */
719 
720 
721 #endif /* SCIP_TYPE_EXPR_H_ */
SCIP_MONOTONE
SCIP_MONOTONE
Definition: type_expr.h:57
SCIP_EXPRITER_USERDATA::realval
SCIP_Real realval
Definition: type_expr.h:679
SCIP_MONOTONE_UNKNOWN
Definition: type_expr.h:59
SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:52
SCIP_EXPRITER_RTOPOLOGIC
Definition: type_expr.h:689
SCIP_Exprhdlr
Definition: struct_expr.h:34
SCIP_EXPRDATA
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:44
SCIP_EXPRITER_TYPE
SCIP_EXPRITER_TYPE
Definition: type_expr.h:687
SCIP_EXPRPRINTDATA
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition: type_expr.h:716
SCIP_EXPRCURV_LINEAR
Definition: type_expr.h:53
SCIP_EXPRITER_USERDATA::uintval
unsigned int uintval
Definition: type_expr.h:682
SCIP_MONOTONE_DEC
Definition: type_expr.h:61
SCIP_EXPR_OWNERDATA
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition: type_expr.h:68
SCIP_EXPRITER_USERDATA
Definition: type_expr.h:677
SCIP_MONOTONE_CONST
Definition: type_expr.h:62
SCIP_EXPRITER_BFS
Definition: type_expr.h:690
intervalarith.h
interval arithmetics for provable bounds
SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:51
SCIP_EXPRITER_DFS
Definition: type_expr.h:691
type_scip.h
type definitions for SCIP&#39;s main datastructure
SCIP_EXPRCURV_UNKNOWN
Definition: type_expr.h:50
SCIP_EXPRITERDATA
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition: type_expr.h:694
type_var.h
type definitions for problem variables
SCIP_ExprIter
Definition: struct_expr.h:193
SCIP_EXPRPRINT_WHAT
unsigned int SCIP_EXPRPRINT_WHAT
Definition: type_expr.h:715
SCIP_Expr
Definition: struct_expr.h:95
SCIP_EXPRITER_USERDATA::intval
int intval
Definition: type_expr.h:680
SCIP_EXPRCURV
SCIP_EXPRCURV
Definition: type_expr.h:48
SCIP_EXPRITER_USERDATA::ptrval
void * ptrval
Definition: type_expr.h:683
type_tree.h
type definitions for branch and bound tree
SCIP_EXPRHDLRDATA
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:183
type_sol.h
type definitions for storing primal CIP solutions
SCIP_MONOTONE_INC
Definition: type_expr.h:60
SCIP_Real
#define SCIP_Real
Definition: def.h:177
SCIP_EXPRITER_STAGE
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:674
def.h
common defines and data types used in all packages of SCIP