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