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   expr.h
26   	 * @brief  private functions to work with algebraic expressions
27   	 * @ingroup INTERNALAPI
28   	 * @author Ksenia Bestuzheva
29   	 * @author Benjamin Mueller
30   	 * @author Felipe Serrano
31   	 * @author Stefan Vigerske
32   	 */
33   	
34   	#ifndef SCIP_EXPR_H_
35   	#define SCIP_EXPR_H_
36   	
37   	#include "scip/pub_expr.h"
38   	#include "scip/type_set.h"
39   	#include "scip/type_stat.h"
40   	#include "scip/type_clock.h"
41   	#include "blockmemshell/memory.h"
42   	
43   	#ifdef NDEBUG
44   	#include "scip/struct_expr.h"
45   	#include "scip/struct_set.h"
46   	#endif
47   	
48   	#ifdef __cplusplus
49   	extern "C" {
50   	#endif
51   	
52   	/**@name Expression Handler Methods */
53   	/**@{ */
54   	
55   	/** create expression handler */
56   	SCIP_RETCODE SCIPexprhdlrCreate(
57   	   BMS_BLKMEM*           blkmem,             /**< block memory */
58   	   SCIP_EXPRHDLR**       exprhdlr,           /**< buffer where to store created expression handler */
59   	   const char*           name,               /**< name of expression handler (must not be NULL) */
60   	   const char*           desc,               /**< description of expression handler (can be NULL) */
61   	   unsigned int          precedence,         /**< precedence of expression operation (used for printing) */
62   	   SCIP_DECL_EXPREVAL((*eval)),              /**< point evaluation callback (must not be NULL) */
63   	   SCIP_EXPRHDLRDATA*    data                /**< data of expression handler (can be NULL) */
64   	   );
65   	
66   	/** frees expression handler */
67   	SCIP_RETCODE SCIPexprhdlrFree(
68   	   SCIP_EXPRHDLR**       exprhdlr,           /**< pointer to expression handler to be freed */
69   	   SCIP_SET*             set,                /**< global SCIP settings */
70   	   BMS_BLKMEM*           blkmem              /**< block memory */
71   	   );
72   	
73   	/** copies the given expression handler to a new scip */
74   	SCIP_RETCODE SCIPexprhdlrCopyInclude(
75   	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
76   	   SCIP_SET*             targetset           /**< SCIP_SET of SCIP to copy to */
77   	   );
78   	
79   	/** initialization of expression handler (resets statistics) */
80   	void SCIPexprhdlrInit(
81   	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
82   	   SCIP_SET*             set                 /**< global SCIP settings */
83   	   );
84   	
85   	/** calls the print callback of an expression handler
86   	 *
87   	 * The method prints an expression.
88   	 * It is called while iterating over the expression graph at different stages.
89   	 *
90   	 * @see SCIP_DECL_EXPRPRINT
91   	 */
92   	SCIP_RETCODE SCIPexprhdlrPrintExpr(
93   	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
94   	   SCIP_SET*             set,                /**< global SCIP settings */
95   	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
96   	   SCIP_EXPR*            expr,               /**< expression */
97   	   SCIP_EXPRITER_STAGE   stage,              /**< stage of expression iteration */
98   	   int                   currentchild,       /**< index of current child if in stage visitingchild or visitedchild */
99   	   unsigned int          parentprecedence,   /**< precedence of parent */
100  	   FILE*                 file                /**< the file to print to */
101  	   );
102  	
103  	/** calls the parse callback of an expression handler
104  	 *
105  	 * The method parses an expression.
106  	 * It should be called when parsing an expression and an operator with the expr handler name is found.
107  	 *
108  	 * @see SCIP_DECL_EXPRPARSE
109  	 */
110  	SCIP_RETCODE SCIPexprhdlrParseExpr(
111  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
112  	   SCIP_SET*             set,                /**< global SCIP settings */
113  	   const char*           string,             /**< string containing expression to be parse */
114  	   const char**          endstring,          /**< buffer to store the position of string after parsing */
115  	   SCIP_EXPR**           expr,               /**< buffer to store the parsed expression */
116  	   SCIP_Bool*            success,            /**< buffer to store whether the parsing was successful or not */
117  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
118  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
119  	   );
120  	
121  	/** calls the curvature check callback of an expression handler
122  	 *
123  	 * @see SCIP_DECL_EXPRCURVATURE
124  	 */
125  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprCurvature() macro */
126  	SCIP_RETCODE SCIPexprhdlrCurvatureExpr(
127  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
128  	   SCIP_SET*             set,                /**< global SCIP settings */
129  	   SCIP_EXPR*            expr,               /**< expression to check the curvature for */
130  	   SCIP_EXPRCURV         exprcurvature,      /**< desired curvature of this expression */
131  	   SCIP_Bool*            success,            /**< buffer to store whether the desired curvature be obtained */
132  	   SCIP_EXPRCURV*        childcurv           /**< array to store required curvature for each child */
133  	   );
134  	
135  	/** calls the monotonicity check callback of an expression handler
136  	 *
137  	 * @see SCIP_DECL_EXPRMONOTONICITY
138  	 */
139  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprMonotonicity() macro */
140  	SCIP_RETCODE SCIPexprhdlrMonotonicityExpr(
141  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
142  	   SCIP_SET*             set,                /**< global SCIP settings */
143  	   SCIP_EXPR*            expr,               /**< expression to check the monotonicity for */
144  	   int                   childidx,           /**< index of the considered child expression */
145  	   SCIP_MONOTONE*        result              /**< buffer to store the monotonicity */
146  	   );
147  	
148  	/** calls the integrality check callback of an expression handler
149  	 *
150  	 * @see SCIP_DECL_EXPRINTEGRALITY
151  	 */
152  	SCIP_RETCODE SCIPexprhdlrIntegralityExpr(
153  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
154  	   SCIP_SET*             set,                /**< global SCIP settings */
155  	   SCIP_EXPR*            expr,               /**< expression to check integrality for */
156  	   SCIP_Bool*            isintegral          /**< buffer to store whether expression is integral */
157  	   );
158  	
159  	/** calls the hash callback of an expression handler
160  	 *
161  	 * The method hashes an expression by taking the hashes of its children into account.
162  	 *
163  	 * @see SCIP_DECL_EXPRHASH
164  	 */
165  	SCIP_RETCODE SCIPexprhdlrHashExpr(
166  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
167  	   SCIP_SET*             set,                /**< global SCIP settings */
168  	   SCIP_EXPR*            expr,               /**< expression to be hashed */
169  	   unsigned int*         hashkey,            /**< buffer to store the hash value */
170  	   unsigned int*         childrenhashes      /**< array with hash values of children */
171  	   );
172  	
173  	/** calls the compare callback of an expression handler
174  	 *
175  	 * The method receives two expressions, expr1 and expr2, and returns
176  	 * - -1 if expr1 < expr2,
177  	 * - 0  if expr1 = expr2,
178  	 * - 1  if expr1 > expr2.
179  	 *
180  	 * @see SCIP_DECL_EXPRCOMPARE
181  	 */
182  	int SCIPexprhdlrCompareExpr(
183  	   SCIP_SET*             set,                /**< global SCIP settings */
184  	   SCIP_EXPR*            expr1,              /**< first expression in comparison */
185  	   SCIP_EXPR*            expr2               /**< second expression in comparison */
186  	   );
187  	
188  	/** calls the evaluation callback of an expression handler
189  	 *
190  	 * The method evaluates an expression by taking the values of its children into account.
191  	 *
192  	 * Further, allows to evaluate w.r.t. given expression and children values instead of those stored in children expressions.
193  	 *
194  	 * @see SCIP_DECL_EXPREVAL
195  	 */
196  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEval() macro */
197  	SCIP_RETCODE SCIPexprhdlrEvalExpr(
198  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
199  	   SCIP_SET*             set,                /**< global SCIP settings */
200  	   BMS_BUFMEM*           bufmem,             /**< buffer memory, can be NULL if childrenvals is NULL */
201  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
202  	   SCIP_Real*            val,                /**< buffer to store value of expression */
203  	   SCIP_Real*            childrenvals,       /**< values for children, or NULL if values stored in children should be used */
204  	   SCIP_SOL*             sol                 /**< solution that is evaluated (can be NULL) */
205  	   );
206  	
207  	/** calls the backward derivative evaluation callback of an expression handler
208  	 *
209  	 * The method should compute the partial derivative of expr w.r.t its child at childidx.
210  	 * That is, it returns
211  	 * \f[
212  	 *   \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}}
213  	 * \f]
214  	 *
215  	 * Further, allows to differentiate w.r.t. given expression and children values instead of those stored in children expressions.
216  	 *
217  	 * @see SCIP_DECL_EXPRBWDIFF
218  	 */
219  	SCIP_RETCODE SCIPexprhdlrBwDiffExpr(
220  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
221  	   SCIP_SET*             set,                /**< global SCIP settings */
222  	   BMS_BUFMEM*           bufmem,             /**< buffer memory, can be NULL if childrenvals is NULL */
223  	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
224  	   int                   childidx,           /**< index of the child */
225  	   SCIP_Real*            derivative,         /**< buffer to store the partial derivative w.r.t. the i-th children */
226  	   SCIP_Real*            childrenvals,       /**< values for children, or NULL if values stored in children should be used */
227  	   SCIP_Real             exprval             /**< value for expression, used only if childrenvals is not NULL */
228  	   );
229  	
230  	/** calls the forward differentiation callback of an expression handler
231  	 *
232  	 * @see SCIP_DECL_EXPRFWDIFF
233  	 */
234  	SCIP_RETCODE SCIPexprhdlrFwDiffExpr(
235  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
236  	   SCIP_SET*             set,                /**< global SCIP settings */
237  	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
238  	   SCIP_Real*            dot,                /**< buffer to store derivative value */
239  	   SCIP_SOL*             direction           /**< direction of the derivative (useful only for var expressions) */
240  	   );
241  	
242  	/** calls the evaluation and forward-differentiation callback of an expression handler
243  	 *
244  	 * The method evaluates an expression by taking the values of its children into account.
245  	 * The method differentiates an expression by taking the values and directional derivatives of its children into account.
246  	 *
247  	 * Further, allows to evaluate and differentiate w.r.t. given values for children instead of those stored in children expressions.
248  	 *
249  	 * It probably doesn't make sense to call this function for a variable-expression if sol and/or direction are not given.
250  	 *
251  	 * @see SCIP_DECL_EXPREVAL
252  	 * @see SCIP_DECL_EXPRFWDIFF
253  	 */
254  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEvalFwdiff() macro */
255  	SCIP_RETCODE SCIPexprhdlrEvalFwDiffExpr(
256  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
257  	   SCIP_SET*             set,                /**< global SCIP settings */
258  	   BMS_BUFMEM*           bufmem,             /**< buffer memory, can be NULL if childrenvals is NULL */
259  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
260  	   SCIP_Real*            val,                /**< buffer to store value of expression */
261  	   SCIP_Real*            dot,                /**< buffer to store derivative value */
262  	   SCIP_Real*            childrenvals,       /**< values for children, or NULL if values stored in children should be used */
263  	   SCIP_SOL*             sol,                /**< solution that is evaluated (can be NULL) */
264  	   SCIP_Real*            childrendirs,       /**< directional derivatives for children, or NULL if dot-values stored in children should be used */
265  	   SCIP_SOL*             direction           /**< direction of the derivative (useful only for var expressions, can be NULL if childrendirs is given) */
266  	   );
267  	
268  	/** calls the evaluation callback for Hessian directions (backward over forward) of an expression handler
269  	 *
270  	 * @see SCIP_DECL_EXPRBWFWDIFF
271  	 */
272  	SCIP_RETCODE SCIPexprhdlrBwFwDiffExpr(
273  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
274  	   SCIP_SET*             set,                /**< global SCIP settings */
275  	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
276  	   int                   childidx,           /**< index of the child */
277  	   SCIP_Real*            bardot,             /**< buffer to store derivative value */
278  	   SCIP_SOL*             direction           /**< direction of the derivative (useful only for var expressions) */
279  	   );
280  	
281  	/** calls the interval evaluation callback of an expression handler
282  	 *
283  	 * @see SCIP_DECL_EXPRINTEVAL
284  	 */
285  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprInteval() macro */
286  	SCIP_RETCODE SCIPexprhdlrIntEvalExpr(
287  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
288  	   SCIP_SET*             set,                /**< global SCIP settings */
289  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
290  	   SCIP_INTERVAL*        interval,           /**< buffer where to store interval */
291  	   SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), /**< callback to be called when interval-evaluating a variable */
292  	   void*                 intevalvardata      /**< data to be passed to intevalvar callback */
293  	   );
294  	
295  	/** calls the estimator callback of an expression handler
296  	 *
297  	 * @see SCIP_DECL_EXPRESTIMATE
298  	 */
299  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprEstimate() macro */
300  	SCIP_RETCODE SCIPexprhdlrEstimateExpr(
301  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
302  	   SCIP_SET*             set,                /**< global SCIP settings */
303  	   SCIP_EXPR*            expr,               /**< expression to be estimated */
304  	   SCIP_INTERVAL*        localbounds,        /**< current bounds for children */
305  	   SCIP_INTERVAL*        globalbounds,       /**< global bounds for children */
306  	   SCIP_Real*            refpoint,           /**< children values for the reference point where to estimate */
307  	   SCIP_Bool             overestimate,       /**< whether the expression needs to be over- or underestimated */
308  	   SCIP_Real             targetvalue,        /**< a value that the estimator shall exceed, can be +/-infinity */
309  	   SCIP_Real*            coefs,              /**< array to store coefficients of estimator */
310  	   SCIP_Real*            constant,           /**< buffer to store constant part of estimator */
311  	   SCIP_Bool*            islocal,            /**< buffer to store whether estimator is valid locally only */
312  	   SCIP_Bool*            success,            /**< buffer to indicate whether an estimator could be computed */
313  	   SCIP_Bool*            branchcand          /**< array to indicate which children (not) to consider for branching */
314  	   );
315  	
316  	/** calls the intitial estimators callback of an expression handler
317  	 *
318  	 * @see SCIP_DECL_EXPRINITESTIMATES
319  	 */
320  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprInitestimates() macro */
321  	SCIP_RETCODE SCIPexprhdlrInitEstimatesExpr(
322  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
323  	   SCIP_SET*             set,                /**< global SCIP settings */
324  	   SCIP_EXPR*            expr,               /**< expression to be estimated */
325  	   SCIP_INTERVAL*        bounds,             /**< bounds for children */
326  	   SCIP_Bool             overestimate,       /**< whether the expression shall be overestimated or underestimated */
327  	   SCIP_Real*            coefs[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store coefficients of computed estimators */
328  	   SCIP_Real             constant[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store constant of computed estimators */
329  	   int*                  nreturned           /**< buffer to store number of estimators that have been computed */
330  	   );
331  	
332  	/** calls the simplification callback of an expression handler
333  	 *
334  	 * @see SCIP_DECL_EXPRSIMPLIFY
335  	 */
336  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPsimplifyExpr() and SCIPexprSimplify() macros */
337  	SCIP_RETCODE SCIPexprhdlrSimplifyExpr(
338  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
339  	   SCIP_SET*             set,                /**< global SCIP settings */
340  	   SCIP_EXPR*            expr,               /**< expression to simplify */
341  	   SCIP_EXPR**           simplifiedexpr,     /**< buffer to store the simplified expression */
342  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
343  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
344  	   );
345  	
346  	/** calls the reverse propagation callback of an expression handler
347  	 *
348  	 * The method propagates given bounds over the children of an expression.
349  	 *
350  	 * @see SCIP_DECL_EXPRREVERSEPROP
351  	 */
352  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcallExprReverseprop() macro */
353  	SCIP_RETCODE SCIPexprhdlrReversePropExpr(
354  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
355  	   SCIP_SET*             set,                /**< global SCIP settings */
356  	   SCIP_EXPR*            expr,               /**< expression to propagate */
357  	   SCIP_INTERVAL         bounds,             /**< the bounds on the expression that should be propagated */
358  	   SCIP_INTERVAL*        childrenbounds,     /**< array to store computed bounds for children, initialized with current activity */
359  	   SCIP_Bool*            infeasible          /**< buffer to store whether a children bounds were propagated to an empty interval */
360  	   );
361  	
362  	/**@} */
363  	
364  	
365  	/**@name Expression Methods */
366  	/**@{ */
367  	
368  	/** creates and captures an expression with given expression data and children */
369  	SCIP_RETCODE SCIPexprCreate(
370  	   SCIP_SET*             set,                /**< global SCIP settings */
371  	   BMS_BLKMEM*           blkmem,             /**< block memory */
372  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
373  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
374  	   SCIP_EXPRDATA*        exprdata,           /**< expression data (expression assumes ownership) */
375  	   int                   nchildren,          /**< number of children */
376  	   SCIP_EXPR**           children,           /**< children (can be NULL if nchildren is 0) */
377  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
378  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
379  	   );
380  	
381  	/** appends child to the children list of expr */
382  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPappendExprChild() macro */
383  	SCIP_RETCODE SCIPexprAppendChild(
384  	   SCIP_SET*             set,                /**< global SCIP settings */
385  	   BMS_BLKMEM*           blkmem,             /**< block memory */
386  	   SCIP_EXPR*            expr,               /**< expression */
387  	   SCIP_EXPR*            child               /**< expression to be appended */
388  	   );
389  	
390  	/** overwrites/replaces a child of an expressions
391  	 *
392  	 * @note the old child is released and the newchild is captured, unless they are the same (=same pointer)
393  	 */
394  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPreplaceExprChild() macro */
395  	SCIP_RETCODE SCIPexprReplaceChild(
396  	   SCIP_SET*             set,                /**< global SCIP settings */
397  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
398  	   BMS_BLKMEM*           blkmem,             /**< block memory */
399  	   SCIP_EXPR*            expr,               /**< expression where a child is going to be replaced */
400  	   int                   childidx,           /**< index of child being replaced */
401  	   SCIP_EXPR*            newchild            /**< the new child */
402  	   );
403  	
404  	/** remove all children of expr */
405  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPremoveExprChildren() macro */
406  	SCIP_RETCODE SCIPexprRemoveChildren(
407  	   SCIP_SET*             set,                /**< global SCIP settings */
408  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
409  	   BMS_BLKMEM*           blkmem,             /**< block memory */
410  	   SCIP_EXPR*            expr                /**< expression */
411  	   );
412  	
413  	/** copies an expression including subexpressions
414  	 *
415  	 * @note If copying fails due to an expression handler not being available in the targetscip, then *targetexpr will be set to NULL.
416  	 *
417  	 * For all or some expressions, a mapping to an existing expression can be specified via the mapexpr callback.
418  	 * The mapped expression (including its children) will not be copied in this case and its ownerdata will not be touched.
419  	 * If, however, the mapexpr callback returns NULL for the targetexpr, then the expr will be copied in the usual way.
420  	 */
421  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPduplicateExpr() macro */
422  	SCIP_RETCODE SCIPexprCopy(
423  	   SCIP_SET*             set,                /**< global SCIP settings */
424  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
425  	   BMS_BLKMEM*           blkmem,             /**< block memory */
426  	   SCIP_SET*             targetset,          /**< global SCIP settings data structure where target expression will live */
427  	   SCIP_STAT*            targetstat,         /**< dynamic problem statistics in target SCIP */
428  	   BMS_BLKMEM*           targetblkmem,       /**< block memory in target SCIP */
429  	   SCIP_EXPR*            sourceexpr,         /**< expression to be copied */
430  	   SCIP_EXPR**           targetexpr,         /**< buffer to store pointer to copy of source expression */
431  	   SCIP_DECL_EXPR_MAPEXPR((*mapexpr)),       /**< expression mapping function, or NULL for creating new expressions */
432  	   void*                 mapexprdata,        /**< data of expression mapping function */
433  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
434  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
435  	   );
436  	
437  	/** duplicates the given expression without its children */
438  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPduplicateExprShallow() macro */
439  	SCIP_RETCODE SCIPexprDuplicateShallow(
440  	   SCIP_SET*             set,                /**< global SCIP settings */
441  	   BMS_BLKMEM*           blkmem,             /**< block memory */
442  	   SCIP_EXPR*            expr,               /**< original expression */
443  	   SCIP_EXPR**           copyexpr,           /**< buffer to store (shallow) duplicate of expr */
444  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
445  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
446  	   );
447  	
448  	/** captures an expression (increments usage count) */
449  	void SCIPexprCapture(
450  	   SCIP_EXPR*            expr                /**< expression */
451  	   );
452  	
453  	/** releases an expression (decrements usage count and possibly frees expression) */
454  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPreleaseExpr() macro */
455  	SCIP_RETCODE SCIPexprRelease(
456  	   SCIP_SET*             set,                /**< global SCIP settings */
457  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
458  	   BMS_BLKMEM*           blkmem,             /**< block memory */
459  	   SCIP_EXPR**           expr                /**< pointer to expression */
460  	   );
461  	
462  	/** returns whether an expression is a variable expression */
463  	SCIP_Bool SCIPexprIsVar(
464  	   SCIP_SET*             set,                /**< global SCIP settings */
465  	   SCIP_EXPR*            expr                /**< expression */
466  	   );
467  	
468  	/** returns whether an expression is a value expression */
469  	SCIP_Bool SCIPexprIsValue(
470  	   SCIP_SET*             set,                /**< global SCIP settings */
471  	   SCIP_EXPR*            expr                /**< expression */
472  	   );
473  	
474  	/** returns whether an expression is a sum expression */
475  	SCIP_Bool SCIPexprIsSum(
476  	   SCIP_SET*             set,                /**< global SCIP settings */
477  	   SCIP_EXPR*            expr                /**< expression */
478  	   );
479  	
480  	/** returns whether an expression is a product expression */
481  	SCIP_Bool SCIPexprIsProduct(
482  	   SCIP_SET*             set,                /**< global SCIP settings */
483  	   SCIP_EXPR*            expr                /**< expression */
484  	   );
485  	
486  	/** returns whether an expression is a power expression */
487  	SCIP_Bool SCIPexprIsPower(
488  	   SCIP_SET*             set,                /**< global SCIP settings */
489  	   SCIP_EXPR*            expr                /**< expression */
490  	   );
491  	
492  	/** print an expression as info-message */
493  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPprintExpr() macro */
494  	SCIP_RETCODE SCIPexprPrint(
495  	   SCIP_SET*             set,                /**< global SCIP settings */
496  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
497  	   BMS_BLKMEM*           blkmem,             /**< block memory */
498  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
499  	   FILE*                 file,               /**< file to print to, or NULL for stdout */
500  	   SCIP_EXPR*            expr                /**< expression to be printed */
501  	   );
502  	
503  	/** initializes printing of expressions in dot format to a give FILE* pointer */
504  	SCIP_RETCODE SCIPexprPrintDotInit(
505  	   SCIP_SET*             set,                /**< global SCIP settings */
506  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
507  	   BMS_BLKMEM*           blkmem,             /**< block memory */
508  	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
509  	   FILE*                 file,               /**< file to print to, or NULL for stdout */
510  	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
511  	   );
512  	
513  	/** initializes printing of expressions in dot format to a file with given filename */
514  	SCIP_RETCODE SCIPexprPrintDotInit2(
515  	   SCIP_SET*             set,                /**< global SCIP settings */
516  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
517  	   BMS_BLKMEM*           blkmem,             /**< block memory */
518  	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
519  	   const char*           filename,           /**< name of file to print to */
520  	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
521  	   );
522  	
523  	/** main part of printing an expression in dot format */
524  	SCIP_RETCODE SCIPexprPrintDot(
525  	   SCIP_SET*             set,                /**< global SCIP settings */
526  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
527  	   SCIP_EXPRPRINTDATA*   printdata,          /**< data as initialized by \ref SCIPprintExprDotInit() */
528  	   SCIP_EXPR*            expr                /**< expression to be printed */
529  	   );
530  	
531  	/** finishes printing of expressions in dot format */
532  	SCIP_RETCODE SCIPexprPrintDotFinal(
533  	   SCIP_SET*             set,                /**< global SCIP settings */
534  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
535  	   BMS_BLKMEM*           blkmem,             /**< block memory */
536  	   SCIP_EXPRPRINTDATA**  printdata           /**< buffer where dot printing data has been stored */
537  	   );
538  	
539  	/** prints structure of an expression a la Maple's dismantle */
540  	SCIP_RETCODE SCIPexprDismantle(
541  	   SCIP_SET*             set,                /**< global SCIP settings */
542  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
543  	   BMS_BLKMEM*           blkmem,             /**< block memory */
544  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
545  	   FILE*                 file,               /**< file to print to, or NULL for stdout */
546  	   SCIP_EXPR*            expr                /**< expression to dismantle */
547  	   );
548  	
549  	/** evaluate an expression in a point
550  	 *
551  	 * Iterates over expressions to also evaluate children, if necessary.
552  	 * Value can be received via SCIPexprGetEvalValue().
553  	 * If an evaluation error (division by zero, ...) occurs, this value will
554  	 * be set to SCIP_INVALID.
555  	 *
556  	 * If a nonzero \p soltag is passed, then only (sub)expressions are
557  	 * reevaluated that have a different solution tag. If a soltag of 0
558  	 * is passed, then subexpressions are always reevaluated.
559  	 * The tag is stored together with the value and can be received via
560  	 * SCIPexprGetEvalTag().
561  	 */
562  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExpr() macro */
563  	SCIP_RETCODE SCIPexprEval(
564  	   SCIP_SET*             set,                /**< global SCIP settings */
565  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
566  	   BMS_BLKMEM*           blkmem,             /**< block memory */
567  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
568  	   SCIP_SOL*             sol,                /**< solution to be evaluated */
569  	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
570  	   );
571  	
572  	/** evaluates gradient of an expression for a given point
573  	 *
574  	 * Initiates an expression walk to also evaluate children, if necessary.
575  	 * Value can be received via SCIPgetExprPartialDiffNonlinear().
576  	 * If an error (division by zero, ...) occurs, this value will
577  	 * be set to SCIP_INVALID.
578  	 */
579  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprGradient() macro */
580  	SCIP_RETCODE SCIPexprEvalGradient(
581  	   SCIP_SET*             set,                /**< global SCIP settings */
582  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
583  	   BMS_BLKMEM*           blkmem,             /**< block memory */
584  	   SCIP_EXPR*            rootexpr,           /**< expression to be evaluated */
585  	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
586  	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
587  	   );
588  	
589  	/** evaluates Hessian-vector product of an expression for a given point and direction
590  	 *
591  	 * Evaluates children, if necessary.
592  	 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear()
593  	 * If an error (division by zero, ...) occurs, this value will
594  	 * be set to SCIP_INVALID.
595  	 */
596  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprHessianDir() macro */
597  	SCIP_RETCODE SCIPexprEvalHessianDir(
598  	   SCIP_SET*             set,                /**< global SCIP settings */
599  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
600  	   BMS_BLKMEM*           blkmem,             /**< block memory */
601  	   SCIP_EXPR*            rootexpr,           /**< expression to be evaluated */
602  	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
603  	   SCIP_Longint          soltag,             /**< tag that uniquely identifies the solution (with its values), or 0. */
604  	   SCIP_SOL*             direction           /**< direction */
605  	   );
606  	
607  	/** possibly reevaluates and then returns the activity of the expression
608  	 *
609  	 * Reevaluate activity if currently stored is no longer uptodate.
610  	 * If the expr owner provided a evalactivity-callback, then call this.
611  	 * Otherwise, loop over descendants and compare activitytag with stat's domchgcount, i.e.,
612  	 * whether some bound was changed since last evaluation, to check whether exprhdlrs INTEVAL should be called.
613  	 *
614  	 * @note If expression is set to be integral, then activities are tightened to integral values.
615  	 *   Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
616  	 */
617  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPevalExprActivity() macro */
618  	SCIP_RETCODE SCIPexprEvalActivity(
619  	   SCIP_SET*             set,                /**< global SCIP settings */
620  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
621  	   BMS_BLKMEM*           blkmem,             /**< block memory */
622  	   SCIP_EXPR*            rootexpr            /**< expression */
623  	   );
624  	
625  	/** compare expressions
626  	 *
627  	 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
628  	 * @note The given expressions are assumed to be simplified.
629  	 */
630  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcompareExpr() macro */
631  	int SCIPexprCompare(
632  	   SCIP_SET*             set,                /**< global SCIP settings */
633  	   SCIP_EXPR*            expr1,              /**< first expression */
634  	   SCIP_EXPR*            expr2               /**< second expression */
635  	   );
636  	
637  	/** simplifies an expression
638  	 *
639  	 * @see SCIPsimplifyExpr
640  	 */
641  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPsimplifyExpr() macro */
642  	SCIP_RETCODE SCIPexprSimplify(
643  	   SCIP_SET*             set,                /**< global SCIP settings */
644  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
645  	   BMS_BLKMEM*           blkmem,             /**< block memory */
646  	   SCIP_EXPR*            rootexpr,           /**< expression to be simplified */
647  	   SCIP_EXPR**           simplified,         /**< buffer to store simplified expression */
648  	   SCIP_Bool*            changed,            /**< buffer to store if rootexpr actually changed */
649  	   SCIP_Bool*            infeasible,         /**< buffer to store whether infeasibility has been detected */
650  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
651  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
652  	   );
653  	
654  	
655  	/** retrieves symmetry information from an expression
656  	 *
657  	 * @see SCIPgetSymDataExpr
658  	 */
659  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPgetSymdataExpr() macro */
660  	SCIP_RETCODE SCIPexprGetSymData(
661  	   SCIP_SET*             set,                /**< global SCIP settings */
662  	   SCIP_EXPR*            expr,               /**< expression from which information is retrieved */
663  	   SYM_EXPRDATA**        symdata             /**< buffer to store symmetry information */
664  	   );
665  	
666  	#ifdef NDEBUG
667  	#define SCIPexprCapture(expr) ++(expr)->nuses
668  	#define SCIPexprIsVar(set, expr)     ((expr)->exprhdlr == (set)->exprhdlrvar)
669  	#define SCIPexprIsValue(set, expr)   ((expr)->exprhdlr == (set)->exprhdlrval)
670  	#define SCIPexprIsSum(set, expr)     ((expr)->exprhdlr == (set)->exprhdlrsum)
671  	#define SCIPexprIsProduct(set, expr) ((expr)->exprhdlr == (set)->exprhdlrproduct)
672  	#define SCIPexprIsPower(set, expr)   ((expr)->exprhdlr == (set)->exprhdlrpow)
673  	#endif
674  	
675  	/**@} */
676  	
677  	/**@name Expression Iterator Methods */
678  	/**@{ */
679  	
680  	/** creates an expression iterator */
681  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcreateExpriter() macro */
682  	SCIP_RETCODE SCIPexpriterCreate(
683  	   SCIP_STAT*            stat,               /**< dynamic problem statistics */
684  	   BMS_BLKMEM*           blkmem,             /**< block memory */
685  	   SCIP_EXPRITER**       iterator            /**< buffer to store expression iterator */
686  	   );
687  	
688  	/** frees an expression iterator */
689  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPfreeExpriter() macro */
690  	void SCIPexpriterFree(
691  	   SCIP_EXPRITER**       iterator            /**< pointer to the expression iterator */
692  	   );
693  	
694  	/**@} */
695  	
696  	
697  	/**@name Quadratic expression functions */
698  	/**@{ */
699  	
700  	/** checks whether an expression is quadratic
701  	 *
702  	 * An expression is quadratic if it is either a power expression with exponent 2.0, a product of two expressions,
703  	 * or a sum of terms where at least one is a square or a product of two.
704  	 *
705  	 * Use \ref SCIPexprGetQuadraticData to get data about the representation as quadratic.
706  	 */
707  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcheckExprQuadratic() macro */
708  	SCIP_RETCODE SCIPexprCheckQuadratic(
709  	   SCIP_SET*             set,                /**< global SCIP settings */
710  	   BMS_BLKMEM*           blkmem,             /**< block memory */
711  	   SCIP_EXPR*            expr,               /**< expression */
712  	   SCIP_Bool*            isquadratic         /**< buffer to store result */
713  	   );
714  	
715  	/** frees information on quadratic representation of an expression
716  	 *
717  	 * Reverts SCIPexprCheckQuadratic().
718  	 * Before doing changes to an expression, it can be useful to call this function.
719  	 */
720  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPfreeExprQuadratic() macro */
721  	void SCIPexprFreeQuadratic(
722  	   BMS_BLKMEM*           blkmem,             /**< block memory */
723  	   SCIP_EXPR*            expr                /**< expression */
724  	   );
725  	
726  	/** Checks the curvature of the quadratic function stored in quaddata
727  	 *
728  	 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
729  	 * If Q is
730  	 * - semidefinite positive -> curv is set to convex,
731  	 * - semidefinite negative -> curv is set to concave,
732  	 * - otherwise -> curv is set to unknown.
733  	 *
734  	 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
735  	 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
736  	 */
737  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPcomputeExprQuadraticCurvature() macro */
738  	SCIP_RETCODE SCIPexprComputeQuadraticCurvature(
739  	   SCIP_SET*             set,                /**< global SCIP settings */
740  	   BMS_BLKMEM*           blkmem,             /**< block memory */
741  	   BMS_BUFMEM*           bufmem,             /**< buffer memory */
742  	   SCIP_MESSAGEHDLR*     messagehdlr,        /**< message handler */
743  	   SCIP_EXPR*            expr,               /**< quadratic expression */
744  	   SCIP_EXPRCURV*        curv,               /**< pointer to store the curvature of quadratics */
745  	   SCIP_HASHMAP*         assumevarfixed,     /**< hashmap containing variables that should be assumed to be fixed, or NULL */
746  	   SCIP_Bool             storeeigeninfo      /**< whether the eigenvalues and eigenvectors should be stored */
747  	   );
748  	
749  	/**@} */
750  	
751  	/**@name Monomial expression functions */
752  	/**@{ */
753  	
754  	/** returns a monomial representation of a product expression
755  	 *
756  	 * The array to store all factor expressions needs to be of size the number of
757  	 * children in the expression which is given by SCIPexprGetNChildren().
758  	 *
759  	 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where
760  	 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can
761  	 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents.
762  	 *
763  	 * A non-trivial monomial is a product of a least two expressions.
764  	 */
765  	SCIP_EXPORT  /* need SCIP_EXPORT here, because func is exposed in API via SCIPgetExprMonomialData() macro */
766  	SCIP_RETCODE SCIPexprGetMonomialData(
767  	   SCIP_SET*             set,                /**< global SCIP settings */
768  	   BMS_BLKMEM*           blkmem,             /**< block memory */
769  	   SCIP_EXPR*            expr,               /**< expression */
770  	   SCIP_Real*            coef,               /**< coefficient \f$c\f$ */
771  	   SCIP_Real*            exponents,          /**< exponents \f$\alpha\f$ */
772  	   SCIP_EXPR**           exprs               /**< expressions \f$x\f$ */
773  	   );
774  	
775  	/**@} */
776  	
777  	#ifdef __cplusplus
778  	}
779  	#endif
780  	
781  	#endif /* SCIP_EXPR_H_ */
782