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