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   scip_expr.h
26   	 * @ingroup PUBLICCOREAPI
27   	 * @brief  public functions to work with algebraic expressions
28   	 * @author Ksenia Bestuzheva
29   	 * @author Benjamin Mueller
30   	 * @author Felipe Serrano
31   	 * @author Stefan Vigerske
32   	 */
33   	
34   	#ifndef SCIP_SCIP_EXPR_H_
35   	#define SCIP_SCIP_EXPR_H_
36   	
37   	#include "scip/type_scip.h"
38   	#include "scip/type_expr.h"
39   	#include "scip/type_misc.h"
40   	
41   	#ifdef NDEBUG
42   	#include "scip/struct_scip.h"
43   	#include "scip/struct_set.h"
44   	#include "scip/struct_mem.h"
45   	#include "scip/struct_stat.h"
46   	#include "scip/set.h"
47   	#include "scip/expr.h"
48   	#endif
49   	
50   	#ifdef __cplusplus
51   	extern "C" {
52   	#endif
53   	
54   	/**@addtogroup PublicExprHandlerMethods
55   	 * @{
56   	 */
57   	
58   	/** creates the handler for an expression handler and includes it into SCIP */
59   	SCIP_EXPORT
60   	SCIP_RETCODE SCIPincludeExprhdlr(
61   	   SCIP*                 scip,               /**< SCIP data structure */
62   	   SCIP_EXPRHDLR**       exprhdlr,           /**< buffer where to store created expression handler */
63   	   const char*           name,               /**< name of expression handler (must not be NULL) */
64   	   const char*           desc,               /**< description of expression handler (can be NULL) */
65   	   unsigned int          precedence,         /**< precedence of expression operation (used for printing) */
66   	   SCIP_DECL_EXPREVAL((*eval)),              /**< point evaluation callback (must not be NULL) */
67   	   SCIP_EXPRHDLRDATA*    data                /**< data of expression handler (can be NULL) */
68   	   );
69   	
70   	/** gives expression handlers */
71   	SCIP_EXPORT
72   	SCIP_EXPRHDLR** SCIPgetExprhdlrs(
73   	   SCIP*                 scip                /**< SCIP data structure */
74   	);
75   	
76   	/** gives number of expression handlers */
77   	SCIP_EXPORT
78   	int SCIPgetNExprhdlrs(
79   	   SCIP*                 scip                /**< SCIP data structure */
80   	);
81   	
82   	/** returns an expression handler of a given name (or NULL if not found) */
83   	SCIP_EXPORT
84   	SCIP_EXPRHDLR* SCIPfindExprhdlr(
85   	   SCIP*                 scip,               /**< SCIP data structure */
86   	   const char*           name                /**< name of expression handler */
87   	   );
88   	
89   	/** returns expression handler for variable expressions (or NULL if not included) */
90   	SCIP_EXPORT
91   	SCIP_EXPRHDLR* SCIPgetExprhdlrVar(
92   	   SCIP*                 scip                /**< SCIP data structure */
93   	   );
94   	
95   	/** returns expression handler for constant value expressions (or NULL if not included) */
96   	SCIP_EXPORT
97   	SCIP_EXPRHDLR* SCIPgetExprhdlrValue(
98   	   SCIP*                 scip                /**< SCIP data structure */
99   	   );
100  	
101  	/** returns expression handler for sum expressions (or NULL if not included) */
102  	SCIP_EXPORT
103  	SCIP_EXPRHDLR* SCIPgetExprhdlrSum(
104  	   SCIP*                 scip                /**< SCIP data structure */
105  	   );
106  	
107  	/** returns expression handler for product expressions (or NULL if not included) */
108  	SCIP_EXPORT
109  	SCIP_EXPRHDLR* SCIPgetExprhdlrProduct(
110  	   SCIP*                 scip                /**< SCIP data structure */
111  	   );
112  	
113  	/** returns expression handler for power expressions (or NULL if not included) */
114  	SCIP_EXPORT
115  	SCIP_EXPRHDLR* SCIPgetExprhdlrPower(
116  	   SCIP*                 scip                /**< SCIP data structure */
117  	   );
118  	
119  	#ifdef NDEBUG
120  	/* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and
121  	 * speed up the algorithms.
122  	 */
123  	#define SCIPgetExprhdlrs(scip)       (scip)->set->exprhdlrs
124  	#define SCIPgetNExprhdlrs(scip)      (scip)->set->nexprhdlrs
125  	#define SCIPfindExprhdlr(scip, name) SCIPsetFindExprhdlr((scip)->set, name)
126  	#define SCIPgetExprhdlrVar(scip)     (scip)->set->exprhdlrvar
127  	#define SCIPgetExprhdlrValue(scip)   (scip)->set->exprhdlrval
128  	#define SCIPgetExprhdlrSum(scip)     (scip)->set->exprhdlrsum
129  	#define SCIPgetExprhdlrProduct(scip) (scip)->set->exprhdlrproduct
130  	#define SCIPgetExprhdlrPower(scip)   (scip)->set->exprhdlrpow
131  	#endif
132  	
133  	/** @} */
134  	
135  	/**@addtogroup PublicExprMethods
136  	 * @{
137  	 */
138  	
139  	/**@name Expressions */
140  	/**@{ */
141  	
142  	/** creates and captures an expression with given expression data and children */
143  	SCIP_EXPORT
144  	SCIP_RETCODE SCIPcreateExpr(
145  	   SCIP*                 scip,               /**< SCIP data structure */
146  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
147  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
148  	   SCIP_EXPRDATA*        exprdata,           /**< expression data (expression assumes ownership) */
149  	   int                   nchildren,          /**< number of children */
150  	   SCIP_EXPR**           children,           /**< children (can be NULL if nchildren is 0) */
151  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
152  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
153  	   );
154  	
155  	/** creates and captures an expression with given expression data and up to two children */
156  	SCIP_EXPORT
157  	SCIP_RETCODE SCIPcreateExpr2(
158  	   SCIP*                 scip,               /**< SCIP data structure */
159  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
160  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
161  	   SCIP_EXPRDATA*        exprdata,           /**< expression data */
162  	   SCIP_EXPR*            child1,             /**< first child (can be NULL) */
163  	   SCIP_EXPR*            child2,             /**< second child (can be NULL) */
164  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
165  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
166  	   );
167  	
168  	/** creates and captures an expression representing a quadratic function */
169  	SCIP_EXPORT
170  	SCIP_RETCODE SCIPcreateExprQuadratic(
171  	   SCIP*                 scip,               /**< SCIP data structure */
172  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
173  	   int                   nlinvars,           /**< number of linear terms */
174  	   SCIP_VAR**            linvars,            /**< array with variables in linear part */
175  	   SCIP_Real*            lincoefs,           /**< array with coefficients of variables in linear part */
176  	   int                   nquadterms,         /**< number of quadratic terms */
177  	   SCIP_VAR**            quadvars1,          /**< array with first variables in quadratic terms */
178  	   SCIP_VAR**            quadvars2,          /**< array with second variables in quadratic terms */
179  	   SCIP_Real*            quadcoefs,          /**< array with coefficients of quadratic terms */
180  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
181  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
182  	   );
183  	
184  	/** creates and captures an expression representing a monomial
185  	 *
186  	 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents.
187  	 * So this function actually creates an expression for a signomial that has exactly one term.
188  	 */
189  	SCIP_EXPORT
190  	SCIP_RETCODE SCIPcreateExprMonomial(
191  	   SCIP*                 scip,               /**< SCIP data structure */
192  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
193  	   int                   nfactors,           /**< number of factors in monomial */
194  	   SCIP_VAR**            vars,               /**< variables in the monomial */
195  	   SCIP_Real*            exponents,          /**< exponent in each factor, or NULL if all 1.0 */
196  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
197  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
198  	   );
199  	
200  	/** appends child to the children list of expr
201  	 *
202  	 * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle an increase in the number of children.
203  	 */
204  	SCIP_EXPORT
205  	SCIP_RETCODE SCIPappendExprChild(
206  	   SCIP*                 scip,               /**< SCIP data structure */
207  	   SCIP_EXPR*            expr,               /**< expression */
208  	   SCIP_EXPR*            child               /**< expression to be appended */
209  	   );
210  	
211  	/** overwrites/replaces a child of an expressions
212  	 *
213  	 * The old child is released and the newchild is captured, unless they are the same (=same pointer).
214  	 */
215  	SCIP_EXPORT
216  	SCIP_RETCODE SCIPreplaceExprChild(
217  	   SCIP*                 scip,               /**< SCIP data structure */
218  	   SCIP_EXPR*            expr,               /**< expression which is going to replace a child */
219  	   int                   childidx,           /**< index of child being replaced */
220  	   SCIP_EXPR*            newchild            /**< the new child */
221  	   );
222  	
223  	/** remove all children of expr
224  	 *
225  	 * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle the removal of all children.
226  	 */
227  	SCIP_EXPORT
228  	SCIP_RETCODE SCIPremoveExprChildren(
229  	   SCIP*                 scip,               /**< SCIP data structure */
230  	   SCIP_EXPR*            expr                /**< expression */
231  	   );
232  	
233  	/** duplicates the given expression and its children */
234  	SCIP_EXPORT
235  	SCIP_RETCODE SCIPduplicateExpr(
236  	   SCIP*                 scip,               /**< SCIP data structure */
237  	   SCIP_EXPR*            expr,               /**< original expression */
238  	   SCIP_EXPR**           copyexpr,           /**< buffer to store duplicate of expr */
239  	   SCIP_DECL_EXPR_MAPEXPR((*mapexpr)),       /**< expression mapping function, or NULL for creating new expressions */
240  	   void*                 mapexprdata,        /**< data of expression mapping function */
241  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
242  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
243  	   );
244  	
245  	/** duplicates the given expression, but reuses its children */
246  	SCIP_EXPORT
247  	SCIP_RETCODE SCIPduplicateExprShallow(
248  	   SCIP*                 scip,               /**< SCIP data structure */
249  	   SCIP_EXPR*            expr,               /**< original expression */
250  	   SCIP_EXPR**           copyexpr,           /**< buffer to store (shallow) duplicate of expr */
251  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
252  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
253  	   );
254  	
255  	/** copies an expression including children to use in a (possibly different) SCIP instance */
256  	SCIP_EXPORT
257  	SCIP_RETCODE SCIPcopyExpr(
258  	   SCIP*                 sourcescip,         /**< source SCIP data structure */
259  	   SCIP*                 targetscip,         /**< target SCIP data structure */
260  	   SCIP_EXPR*            expr,               /**< original expression */
261  	   SCIP_EXPR**           copyexpr,           /**< buffer to store duplicate of expr */
262  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
263  	   void*                 ownercreatedata,    /**< data to pass to ownercreate */
264  	   SCIP_HASHMAP*         varmap,             /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding
265  	                                              *   variables of the target SCIP, or NULL */
266  	   SCIP_HASHMAP*         consmap,            /**< a hashmap to store the mapping of source constraints to the corresponding
267  	                                              *   target constraints, or NULL */
268  	   SCIP_Bool             global,             /**< create a global or a local copy? */
269  	   SCIP_Bool*            valid               /**< pointer to store whether all checked or enforced constraints were validly copied */
270  	   );
271  	
272  	/** creates an expression from a string
273  	 *
274  	 * We specify the grammar that defines the syntax of an expression.
275  	 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power,
276  	 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`.
277  	 *
278  	 * The actual definition:
279  	 * <pre>
280  	 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
281  	 * Term       -> Factor { ("*" | "/" ) Factor }
282  	 * Factor     -> Base [ "^" "number" | "^(" "number" ")" ]
283  	 * Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
284  	 * </pre>
285  	 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`.
286  	 *
287  	 * Note that `Op` and `OpExpression` are undefined.
288  	 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method).
289  	 */
290  	SCIP_EXPORT
291  	SCIP_RETCODE SCIPparseExpr(
292  	   SCIP*                 scip,               /**< SCIP data structure */
293  	   SCIP_EXPR**           expr,               /**< pointer to store the expr parsed */
294  	   const char*           exprstr,            /**< string with the expr to parse */
295  	   const char**          finalpos,           /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */
296  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
297  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
298  	   );
299  	
300  	/** captures an expression (increments usage count) */
301  	SCIP_EXPORT
302  	void SCIPcaptureExpr(
303  	   SCIP_EXPR*            expr                /**< expression to be captured */
304  	   );
305  	
306  	/** releases an expression (decrements usage count and possibly frees expression) */
307  	SCIP_EXPORT
308  	SCIP_RETCODE SCIPreleaseExpr(
309  	   SCIP*                 scip,               /**< SCIP data structure */
310  	   SCIP_EXPR**           expr                /**< pointer to expression to be released */
311  	   );
312  	
313  	/** returns whether an expression is a variable expression */
314  	SCIP_EXPORT
315  	SCIP_Bool SCIPisExprVar(
316  	   SCIP*                 scip,               /**< SCIP data structure */
317  	   SCIP_EXPR*            expr                /**< expression */
318  	   );
319  	
320  	/** returns whether an expression is a value expression */
321  	SCIP_EXPORT
322  	SCIP_Bool SCIPisExprValue(
323  	   SCIP*                 scip,               /**< SCIP data structure */
324  	   SCIP_EXPR*            expr                /**< expression */
325  	   );
326  	
327  	/** returns whether an expression is a sum expression */
328  	SCIP_EXPORT
329  	SCIP_Bool SCIPisExprSum(
330  	   SCIP*                 scip,               /**< SCIP data structure */
331  	   SCIP_EXPR*            expr                /**< expression */
332  	   );
333  	
334  	/** returns whether an expression is a product expression */
335  	SCIP_EXPORT
336  	SCIP_Bool SCIPisExprProduct(
337  	   SCIP*                 scip,               /**< SCIP data structure */
338  	   SCIP_EXPR*            expr                /**< expression */
339  	   );
340  	
341  	/** returns whether an expression is a power expression */
342  	SCIP_EXPORT
343  	SCIP_Bool SCIPisExprPower(
344  	   SCIP*                 scip,               /**< SCIP data structure */
345  	   SCIP_EXPR*            expr                /**< expression */
346  	   );
347  	
348  	/** print an expression as info-message */
349  	SCIP_EXPORT
350  	SCIP_RETCODE SCIPprintExpr(
351  	   SCIP*                 scip,               /**< SCIP data structure */
352  	   SCIP_EXPR*            expr,               /**< expression to be printed */
353  	   FILE*                 file                /**< file to print to, or NULL for stdout */
354  	   );
355  	
356  	/** initializes printing of expressions in dot format to a give FILE* pointer */
357  	SCIP_EXPORT
358  	SCIP_RETCODE SCIPprintExprDotInit(
359  	   SCIP*                 scip,               /**< SCIP data structure */
360  	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
361  	   FILE*                 file,               /**< file to print to, or NULL for stdout */
362  	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
363  	   );
364  	
365  	/** initializes printing of expressions in dot format to a file with given filename */
366  	SCIP_EXPORT
367  	SCIP_RETCODE SCIPprintExprDotInit2(
368  	   SCIP*                 scip,               /**< SCIP data structure */
369  	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
370  	   const char*           filename,           /**< name of file to print to */
371  	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
372  	   );
373  	
374  	/** main part of printing an expression in dot format */
375  	SCIP_EXPORT
376  	SCIP_RETCODE SCIPprintExprDot(
377  	   SCIP*                 scip,               /**< SCIP data structure */
378  	   SCIP_EXPRPRINTDATA*   printdata,          /**< data as initialized by \ref SCIPprintExprDotInit() */
379  	   SCIP_EXPR*            expr                /**< expression to be printed */
380  	   );
381  	
382  	/** finishes printing of expressions in dot format */
383  	SCIP_EXPORT
384  	SCIP_RETCODE SCIPprintExprDotFinal(
385  	   SCIP*                 scip,               /**< SCIP data structure */
386  	   SCIP_EXPRPRINTDATA**  printdata           /**< buffer where dot printing data has been stored */
387  	   );
388  	
389  	/** shows a single expression by use of dot and gv
390  	 *
391  	 * This function is meant for debugging purposes.
392  	 * It's signature is kept as simple as possible to make it
393  	 * easily callable from gdb, for example.
394  	 *
395  	 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file, then calls ghostview (gv) to show the file.
396  	 * SCIP will hold until ghostscript is closed.
397  	 */
398  	SCIP_EXPORT
399  	SCIP_RETCODE SCIPshowExpr(
400  	   SCIP*                 scip,               /**< SCIP data structure */
401  	   SCIP_EXPR*            expr                /**< expression to be printed */
402  	   );
403  	
404  	/** prints structure of an expression a la Maple's dismantle */
405  	SCIP_EXPORT
406  	SCIP_RETCODE SCIPdismantleExpr(
407  	   SCIP*                 scip,               /**< SCIP data structure */
408  	   FILE*                 file,               /**< file to print to, or NULL for stdout */
409  	   SCIP_EXPR*            expr                /**< expression to dismantle */
410  	   );
411  	
412  	/** evaluate an expression in a point
413  	 *
414  	 * Iterates over expressions to also evaluate children, if necessary.
415  	 * Value can be received via SCIPexprGetEvalValue().
416  	 * If an evaluation error (division by zero, ...) occurs, this value will
417  	 * be set to SCIP_INVALID.
418  	 *
419  	 * If a nonzero \p soltag is passed, then only (sub)expressions are
420  	 * reevaluated that have a different solution tag. If a soltag of 0
421  	 * is passed, then subexpressions are always reevaluated.
422  	 * The tag is stored together with the value and can be received via
423  	 * SCIPexprGetEvalTag().
424  	 */
425  	SCIP_EXPORT
426  	SCIP_RETCODE SCIPevalExpr(
427  	   SCIP*                 scip,               /**< SCIP data structure */
428  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
429  	   SCIP_SOL*             sol,                /**< solution to be evaluated */
430  	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
431  	   );
432  	
433  	/** returns a previously unused solution tag for expression evaluation */
434  	SCIP_EXPORT
435  	SCIP_Longint SCIPgetExprNewSoltag(
436  	   SCIP*                 scip                /**< SCIP data structure */
437  	   );
438  	
439  	/**@} */
440  	
441  	/** @name Differentiation
442  	 * @anchor SCIP_EXPR_DIFF
443  	 *
444  	 * @par Gradients (Automatic differentiation Backward mode)
445  	 *
446  	 * Given a function, say, \f$f(s(x,y),t(x,y))\f$ there is a common mnemonic technique to compute its partial derivatives, using a tree diagram.
447  	 * Suppose we want to compute the partial derivative of \f$f\f$ w.r.t. \f$x\f$.
448  	 * Write the function as a tree:
449  	 *
450  	 *     f
451  	 *     |-----|
452  	 *     s     t
453  	 *     |--|  |--|
454  	 *     x  y  x  y
455  	 *
456  	 * The weight of an edge between two nodes represents the partial derivative of the parent w.r.t. the children, e.g.,
457  	 *
458  	 *     f
459  	 *     |
460  	 *     s
461  	 *
462  	 * is \f$ \partial_sf \f$.
463  	 * The weight of a path is the product of the weight of the edges in the path.
464  	 * The partial derivative of \f$f\f$ w.r.t. \f$x\f$ is then the sum of the weights of all paths connecting \f$f\f$ with \f$x\f$:
465  	 * \f[ \frac{\partial f}{\partial x} = \partial_s f \cdot \partial_x s + \partial_t f \cdot \partial_x t. \f]
466  	 *
467  	 * We follow this method in order to compute the gradient of an expression (root) at a given point (point).
468  	 * Note that an expression is a DAG representation of a function, but there is a 1-1 correspondence between paths
469  	 * in the DAG and path in a tree diagram of a function.
470  	 * Initially, we set `root->derivative` to 1.0.
471  	 * Then, traversing the tree in Depth First (see \ref SCIPexpriterInit), for every expr that *has* children,
472  	 * we store in its i-th child, `child[i]->derivative`, the derivative of expr w.r.t. child evaluated at point multiplied with `expr->derivative`.
473  	 *
474  	 * For example:
475  	 * 1. `f->derivative` = 1.0
476  	 * 2. `s->derivative` = \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$
477  	 * 3. `x->derivative` = \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$
478  	 *
479  	 * However, when the child is a variable expressions, we actually need to initialize `child->derivative` to 0.0
480  	 * and afterwards add, instead of overwrite the computed value.
481  	 * The complete example would then be:
482  	 *
483  	 * 1. `f->derivative` = 1.0, `x->derivative` = 0.0, `y->derivative` = 0.0
484  	 * 2. `s->derivative` =  \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$
485  	 * 3. `x->derivative` += \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$
486  	 * 4. `y->derivative` += \f$\partial_y s \,\cdot\f$ `s->derivative` = \f$\partial_y s \cdot \partial_s f\f$
487  	 * 5. `t->derivative` =  \f$\partial_t f \,\cdot\f$ `f->derivative` = \f$\partial_t f\f$
488  	 * 6. `x->derivative` += \f$\partial_x t \,\cdot\f$ `t->derivative` = \f$\partial_x t \cdot \partial_t f\f$
489  	 * 7. `y->derivative` += \f$\partial_y t \,\cdot\f$ `t->derivative` = \f$\partial_y t \cdot \partial_t f\f$
490  	 *
491  	 * Note that, to compute this, we only need to know, for each expression, its partial derivatives w.r.t a given child at a point.
492  	 * This is what the callback `SCIP_DECL_EXPRBWDIFF` should return.
493  	 * Indeed, from "derivative of expr w.r.t. child evaluated at point multiplied with expr->derivative",
494  	 * note that at the moment of processing a child, we already know `expr->derivative`, so the only
495  	 * missing piece of information is "the derivative of expr w.r.t. child evaluated at point".
496  	 *
497  	 * An equivalent way of interpreting the procedure is that `expr->derivative` stores the derivative of the root w.r.t. expr.
498  	 * This way, `x->derivative` and `y->derivative` will contain the partial derivatives of root w.r.t. the variable, that is, the gradient.
499  	 * Note, however, that this analogy is only correct for leave expressions, since the derivative value of an intermediate expression gets overwritten.
500  	 *
501  	 *
502  	 * \par Hessian (Automatic differentiation Backward on Forward mode)
503  	 *
504  	 * Computing the Hessian is more complicated since it is the derivative of the gradient, which is a function with more than one output.
505  	 * We compute the Hessian by computing "directions" of the Hessian, that is \f$H\cdot u\f$ for different \f$u\f$.
506  	 * This is easy in general, since it is the gradient of the *scalar* function \f$\nabla f u\f$, that is,
507  	 * the directional derivative of \f$f\f$ in the direction \f$u\f$: \f$D_u f\f$.
508  	 *
509  	 * This is easily computed via the so called forward mode.
510  	 * Just as `expr->derivative` stores the partial derivative of the root w.r.t. expr,
511  	 * `expr->dot` stores the directional derivative of expr in the direction \f$u\f$.
512  	 * Then, by the chain rule, `expr->dot` = \f$\sum_{c:\text{children}} \partial_c \text{expr} \,\cdot\f$ `c->dot`.
513  	 *
514  	 * Starting with `x[i]->dot` = \f$u_i\f$, we can compute `expr->dot` for every expression at the same time we evaluate expr.
515  	 * Computing `expr->dot` is the purpose of the callback `SCIP_DECL_EXPRFWDIFF`.
516  	 * Obviously, when this callback is called, the "dots" of all children are known
517  	 * (just like evaluation, where the value of all children are known).
518  	 *
519  	 * Once we have this information, we compute the gradient of this function, following the same idea as before.
520  	 * We define `expr->bardot` to be the directional derivative in direction \f$u\f$ of the partial derivative of the root w.r.t `expr`,
521  	 * that is \f$D_u (\partial_{\text{expr}} f) = D_u\f$ (`expr->derivative`).
522  	 *
523  	 * This way, `x[i]->bardot` = \f$D_u (\partial_{x_i} f) = e_i^T H_f u\f$.
524  	 * Hence `vars->bardot` contain \f$H_f u\f$.
525  	 * By the chain rule, product rule, and definition we have
526  	 * \f{eqnarray*}{
527  	 * \texttt{expr->bardot} & = & D_u (\partial_{\text{expr}} f) \\
528  	 *   & = & D_u ( \partial_{\text{parent}} f \cdot \partial_{\text{expr}} \text{parent} )  \\
529  	 *   & = & D_u ( \texttt{parent->derivative} \cdot \partial_{\text{expr}} \text{parent} ) \\
530  	 *   & = & \partial_{\text{expr}} \text{parent} \cdot D_u (\texttt{parent->derivative}) + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) \\
531  	 *   & = & \texttt{parent->bardot} \cdot \partial_{\text{expr}} \text{parent} + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent})
532  	 * \f}
533  	 *
534  	 * Note that we have computed `parent->bardot` and `parent->derivative` at this point,
535  	 * while \f$\partial_{\text{expr}} \text{parent}\f$ is the return of `SCIP_DECL_EXPRBWDIFF`.
536  	 * Hence the only information we need to compute is \f$D_u (\partial_{\text{expr}} \text{parent})\f$.
537  	 * This is the purpose of the callback `SCIP_DECL_EXPRBWFWDIFF`.
538  	 *
539  	 * @{
540  	 */
541  	
542  	/** evaluates gradient of an expression for a given point
543  	 *
544  	 * Initiates an expression walk to also evaluate children, if necessary.
545  	 * Value can be received via SCIPgetExprPartialDiffNonlinear().
546  	 * If an error (division by zero, ...) occurs, this value will
547  	 * be set to SCIP_INVALID.
548  	 */
549  	SCIP_EXPORT
550  	SCIP_RETCODE SCIPevalExprGradient(
551  	   SCIP*                 scip,               /**< SCIP data structure */
552  	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
553  	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
554  	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
555  	   );
556  	
557  	/** evaluates Hessian-vector product of an expression for a given point and direction
558  	 *
559  	 * Evaluates children, if necessary.
560  	 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear().
561  	 * If an error (division by zero, ...) occurs, this value will
562  	 * be set to SCIP_INVALID.
563  	 */
564  	SCIP_EXPORT
565  	SCIP_RETCODE SCIPevalExprHessianDir(
566  	   SCIP*                 scip,               /**< SCIP data structure */
567  	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
568  	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
569  	   SCIP_Longint          soltag,             /**< tag that uniquely identifies the solution (with its values), or 0. */
570  	   SCIP_SOL*             direction           /**< direction */
571  	   );
572  	
573  	/**@} */  /* end of differentiation methods */
574  	
575  	/**@name Expressions
576  	 * @{
577  	 */
578  	
579  	/** possibly reevaluates and then returns the activity of the expression
580  	 *
581  	 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation).
582  	 *
583  	 * The owner of the expression may overwrite the methods used to evaluate the activity,
584  	 * including whether the local or global domain of variables is used.
585  	 * By default (no owner, or owner doesn't overwrite activity evaluation),
586  	 * the local domain of variables is used.
587  	 *
588  	 * @note If expression is set to be integral, then activities are tightened to integral values.
589  	 *   Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
590  	 */
591  	SCIP_EXPORT
592  	SCIP_RETCODE SCIPevalExprActivity(
593  	   SCIP*                 scip,               /**< SCIP data structure */
594  	   SCIP_EXPR*            expr                /**< expression */
595  	   );
596  	
597  	/** compare expressions
598  	 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
599  	 * @note The given expressions are assumed to be simplified.
600  	 */
601  	SCIP_EXPORT
602  	int SCIPcompareExpr(
603  	   SCIP*                 scip,               /**< SCIP data structure */
604  	   SCIP_EXPR*            expr1,              /**< first expression */
605  	   SCIP_EXPR*            expr2               /**< second expression */
606  	   );
607  	
608  	/** compute the hash value of an expression */
609  	SCIP_EXPORT
610  	SCIP_RETCODE SCIPhashExpr(
611  	   SCIP*                 scip,               /**< SCIP data structure */
612  	   SCIP_EXPR*            expr,               /**< expression */
613  	   unsigned int*         hashval             /**< pointer to store the hash value */
614  	   );
615  	
616  	/** simplifies an expression
617  	 *
618  	 * This is largely inspired by Joel Cohen's
619  	 * *Computer algebra and symbolic computation: Mathematical methods*,
620  	 * in particular Chapter 3.
621  	 * The other fountain of inspiration are the simplifying methods of expr.c in SCIP 7.
622  	 *
623  	 * Note: The things to keep in mind when adding simplification rules are the following.
624  	 * I will be using the product expressions (see expr_product.c) as an example.
625  	 * There are mainly 3 parts of the simplification process. You need to decide
626  	 * at which stage the simplification rule makes sense.
627  	 * 1. Simplify each factor (simplifyFactor()): At this stage we got the children of the product expression.
628  	 *    At this point, each child is simplified when viewed as a stand-alone expression, but not necessarily when viewed as child of a product expression.
629  	 *    Rules like SP2, SP7, etc are enforced at this point.
630  	 * 2. Multiply the factors (mergeProductExprlist()): At this point rules like SP4, SP5 and SP14 are enforced.
631  	 * 3. Build the actual simplified product expression (buildSimplifiedProduct()):
632  	 *    At this point rules like SP10, SP11, etc are enforced.
633  	 *
634  	 * During steps 1 and 2 do not forget to set the flag `changed` to TRUE when something actually changes.
635  	 *
636  	 * \par Definition of simplified expressions
637  	 *
638  	 * An expression is simplified if it
639  	 * - is a value expression
640  	 * - is a var expression
641  	 * - is a product expression such that
642  	 *   - SP1: every child is simplified
643  	 *   - SP2: no child is a product
644  	 *   - SP4: no two children are the same expression (those should be multiplied)
645  	 *   - SP5: the children are sorted [commutative rule]
646  	 *   - SP7: no child is a value
647  	 *   - SP8: its coefficient is 1.0 (otherwise should be written as sum)
648  	 *   - SP10: it has at least two children
649  	 *   - TODO?: at most one child is an `abs`
650  	 *   - SP11: no two children are `expr*log(expr)`
651  	 *     (TODO: we could handle more complicated stuff like \f$xy\log(x) \to - y * \mathrm{entropy}(x)\f$, but I am not sure this should happen at the simplification level;
652  	 *            similar for \f$(xy) \log(xy)\f$, which currently simplifies to \f$xy \log(xy)\f$)
653  	 *   - SP12: if it has two children, then neither of them is a sum (expand sums)
654  	 *   - SP12b: if it has at least two children and expandalways is set, then no child is a sum (expand sums always)
655  	 *   - SP13: no child is a sum with a single term
656  	 *   - SP14: at most one child is an `exp`
657  	 * - is a power expression such that
658  	 *   - POW1: exponent is not 0
659  	 *   - POW2: exponent is not 1
660  	 *   - POW3: its child is not a value
661  	 *   - POW4: its child is simplified
662  	 *   - POW5: if exponent is integer, its child is not a product
663  	 *   - POW5a: if exponent is fractional and distribfracexponent param is enabled, its child is not a product
664  	 *   - POW6: if exponent is integer, its child is not a sum with a single term (\f$(2x)^2 \to 4x^2\f$)
665  	 *   - POW7: if exponent is integer and at most expandmaxeponent param, its child is not a sum (expand sums)
666  	 *   - POW8: its child is not a power unless \f$(x^n)^m\f$ with \f$nm\f$ being integer and \f$n\f$ or \f$m\f$ fractional and \f$n\f$ not being even integer
667  	 *   - POW9: its child is not a sum with a single term with a positive coefficient: \f$(25x)^{0.5} \to 5 x^{0.5}\f$
668  	 *   - POW10: its child is not a binary variable: \f$b^e, e > 0 \to b\f$; \f$b^e, e < 0 \to b := 1\f$
669  	 *   - POW11: its child is not an exponential: \f$\exp(\text{expr})^e \to \exp(e\cdot\text{expr})\f$
670  	 *   - POW12: its child is not an absolute value if the exponent is an even integer: \f$\abs(\text{expr})^e, e \text{ even} \to \text{expr}^e\f$
671  	 * - is a signedpower expression such that
672  	 *   - SPOW1: exponent is not 0
673  	 *   - SPOW2: exponent is not 1
674  	 *   - SPOW3: its child is not a value
675  	 *   - SPOW4: its child is simplified
676  	 *   - SPOW5: (TODO) do we want to distribute signpowers over products like we do for powers?
677  	 *   - SPOW6: exponent is not an odd integer: (signpow odd expr) -> (pow odd expr)
678  	 *   - SPOW8: if exponent is integer, its child is not a power
679  	 *   - SPOW9: its child is not a sum with a single term: \f$\mathrm{signpow}(25x,0.5) \to 5\mathrm{signpow}(x,0.5)\f$
680  	 *   - SPOW10: its child is not a binary variable: \f$\mathrm{signpow}(b,e), e > 0 \to b\f$; \f$\mathrm{signpow}(b,e), e < 0 \to b := 1\f$
681  	 *   - SPOW11: its child is not an exponential: \f$\mathrm{signpow}(\exp(\text{expr}),e) \to \exp(e\cdot\text{expr})\f$
682  	 *   - TODO: what happens when child is another signed power?
683  	 *   - TODO: if child &ge; 0 -> transform to normal power; if child < 0 -> transform to - normal power
684  	 *
685  	 *   TODO: Some of these criteria are too restrictive for signed powers; for example, the exponent does not need to be
686  	 *   an integer for signedpower to distribute over a product (SPOW5, SPOW6, SPOW8). Others can also be improved.
687  	 * - is a sum expression such that
688  	 *   - SS1: every child is simplified
689  	 *   - SS2: no child is a sum
690  	 *   - SS3: no child is a value (values should go in the constant of the sum)
691  	 *   - SS4: no two children are the same expression (those should be summed up)
692  	 *   - SS5: the children are sorted [commutative rule]
693  	 *   - SS6: it has at least one child
694  	 *   - SS7: if it consists of a single child, then either constant is != 0.0 or coef != 1
695  	 *   - SS8: no child has coefficient 0
696  	 *   - SS9: if a child c is a product that has an exponential expression as one of its factors, then the coefficient of c is +/-1.0
697  	 *   - SS10: if a child c is an exponential, then the coefficient of c is +/-1.0
698  	 * - it is a function with simplified arguments, but not all of them can be values
699  	 * - TODO? a logarithm doesn't have a product as a child
700  	 * - TODO? the exponent of an exponential is always 1
701  	 *
702  	 * \par Ordering Rules (see SCIPexprCompare())
703  	 * \anchor EXPR_ORDER
704  	 * These rules define a total order on *simplified* expressions.
705  	 * There are two groups of rules, when comparing equal type expressions and different type expressions.
706  	 *
707  	 * Equal type expressions:
708  	 * - OR1: u,v value expressions: u < v &hArr; val(u) < val(v)
709  	 * - OR2: u,v var expressions: u < v &hArr; `SCIPvarGetIndex(var(u))` < `SCIPvarGetIndex(var(v))`
710  	 * - OR3: u,v are both sum or product expression: < is a lexicographical order on the terms
711  	 * - OR4: u,v are both pow: u < v &hArr; base(u) < base(v) or, base(u) = base(v) and expo(u) < expo(v)
712  	 * - OR5: u,v are \f$u = f(u_1, ..., u_n), v = f(v_1, ..., v_m)\f$: u < v &hArr; For the first k such that \f$u_k \neq v_k\f$, \f$u_k < v_k\f$, or if such a \f$k\f$ doesn't exist, then \f$n < m\f$.
713  	 *
714  	 * Different type expressions:
715  	 * - OR6: u value, v other: u < v always
716  	 * - OR7: u sum, v var or func: u < v &hArr; u < 0+v;
717  	 *        In other words, if \f$u = \sum_{i=1}^n \alpha_i u_i\f$, then u < v &hArr; \f$u_n\f$ < v or if \f$u_n\f$ = v and \f$\alpha_n\f$ < 1.
718  	 * - OR8: u product, v pow, sum, var or func: u < v &hArr; u < 1*v;
719  	 *        In other words, if \f$u = \prod_{i=1}^n u_i\f$, then u < v &hArr; \f$u_n\f$ < v.
720  	 *        Note: since this applies only to simplified expressions, the form of the product is correct.
721  	 *              Simplified products  do *not* have constant coefficients.
722  	 * - OR9: u pow, v sum, var or func: u < v &hArr; u < v^1
723  	 * - OR10: u var, v func: u < v always
724  	 * - OR11: u func, v other type of func: u < v &hArr; name(type(u)) < name(type(v))
725  	 * - OR12: none of the rules apply: u < v &hArr; ! v < u
726  	 *
727  	 * Examples:
728  	 * - x < x^2 ?:  x is var and x^2 power, so none applies (OR12).
729  	 *   Hence, we try to answer x^2 < x ?: x^2 < x &hArr; x < x or if x = x and 2 < 1 &hArr; 2 < 1 &hArr; False. So x < x^2 is True.
730  	 * - x < x^-1 --OR12&rarr; ~(x^-1 < x) --OR9&rarr; ~(x^-1 < x^1) --OR4&rarr; ~(x < x or -1 < 1) &rarr; ~True &rarr; False
731  	 * - x*y < x --OR8&rarr; x*y < 1*x --OR3&rarr; y < x --OR2&rarr; False
732  	 * - x*y < y --OR8&rarr; x*y < 1*y --OR3&rarr; y < x --OR2&rarr; False
733  	 *
734  	 * \par Algorithm
735  	 *
736  	 * The recursive version of the algorithm is
737  	 *
738  	 *     EXPR simplify(expr)
739  	 *        for c in 1..expr->nchildren
740  	 *           expr->children[c] = simplify(expr->children[c])
741  	 *        end
742  	 *        return expr->exprhdlr->simplify(expr)
743  	 *     end
744  	 *
745  	 * Important: Whatever is returned by a simplify callback **has** to be simplified.
746  	 * Also, all children of the given expression **are** already simplified.
747  	 */
748  	SCIP_EXPORT
749  	SCIP_RETCODE SCIPsimplifyExpr(
750  	   SCIP*                 scip,               /**< SCIP data structure */
751  	   SCIP_EXPR*            rootexpr,           /**< expression to be simplified */
752  	   SCIP_EXPR**           simplified,         /**< buffer to store simplified expression */
753  	   SCIP_Bool*            changed,            /**< buffer to store if rootexpr actually changed */
754  	   SCIP_Bool*            infeasible,         /**< buffer to store whether infeasibility has been detected */
755  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
756  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
757  	   );
758  	
759  	/** retrieves symmetry information from an expression */
760  	SCIP_EXPORT
761  	SCIP_RETCODE SCIPgetSymDataExpr(
762  	   SCIP*                 scip,               /**< SCIP data structure */
763  	   SCIP_EXPR*            expr,               /**< expression from which information needs to be retrieved */
764  	   SYM_EXPRDATA**        symdata             /**< buffer to store symmetry data */
765  	   );
766  	
767  	/** replaces common sub-expressions in a given expression graph by using a hash key for each expression
768  	 *
769  	 *  The algorithm consists of two steps:
770  	 *
771  	 *  1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash
772  	 *
773  	 *  2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a
774  	 *     structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the
775  	 *     hash table, otherwise we add it to the hash table
776  	 *
777  	 *  @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions
778  	 *  (with the same hash) are structurally the same we use the function SCIPexprCompare().
779  	 */
780  	SCIP_EXPORT
781  	SCIP_RETCODE SCIPreplaceCommonSubexpressions(
782  	   SCIP*                 scip,               /**< SCIP data structure */
783  	   SCIP_EXPR**           exprs,              /**< expressions (possibly replaced by equivalent on output) */
784  	   int                   nexprs,             /**< total number of expressions */
785  	   SCIP_Bool*            replacedroot        /**< buffer to store whether any root expression (expression in exprs) was replaced */
786  	);
787  	
788  	/** computes the curvature of a given expression and all its subexpressions
789  	 *
790  	 *  @note this function also evaluates all subexpressions w.r.t. current variable bounds
791  	 *  @note this function relies on information from the curvature callback of expression handlers only,
792  	 *    consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity
793  	 */
794  	SCIP_EXPORT
795  	SCIP_RETCODE SCIPcomputeExprCurvature(
796  	   SCIP*                 scip,               /**< SCIP data structure */
797  	   SCIP_EXPR*            expr                /**< expression */
798  	   );
799  	
800  	/** computes integrality information of a given expression and all its subexpressions
801  	 *
802  	 * The integrality information can be accessed via SCIPexprIsIntegral().
803  	 */
804  	SCIP_EXPORT
805  	SCIP_RETCODE SCIPcomputeExprIntegrality(
806  	   SCIP*                 scip,               /**< SCIP data structure */
807  	   SCIP_EXPR*            expr                /**< expression */
808  	   );
809  	
810  	/** returns the total number of variable expressions in an expression
811  	 *
812  	 * The function counts variable expressions in common sub-expressions only once, but
813  	 * counts variables appearing in several variable expressions multiple times.
814  	 */
815  	SCIP_EXPORT
816  	SCIP_RETCODE SCIPgetExprNVars(
817  	   SCIP*                 scip,               /**< SCIP data structure */
818  	   SCIP_EXPR*            expr,               /**< expression */
819  	   int*                  nvars               /**< buffer to store the total number of variables */
820  	   );
821  	
822  	/** returns all variable expressions contained in a given expression
823  	 *
824  	 * The array to store all variable expressions needs to be at least of size
825  	 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars().
826  	 *
827  	 * If every variable is represented by only one variable expression (common subexpression have been removed)
828  	 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars().
829  	 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying,
830  	 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars().
831  	 *
832  	 * @note function captures variable expressions
833  	 */
834  	SCIP_EXPORT
835  	SCIP_RETCODE SCIPgetExprVarExprs(
836  	   SCIP*                 scip,               /**< SCIP data structure */
837  	   SCIP_EXPR*            expr,               /**< expression */
838  	   SCIP_EXPR**           varexprs,           /**< array to store all variable expressions */
839  	   int*                  nvarexprs           /**< buffer to store the total number of variable expressions */
840  	   );
841  	
842  	/** @} */
843  	
844  	/**@name Expression Handler Callbacks
845  	 * @{
846  	 */
847  	
848  	/** calls the print callback for an expression
849  	 *
850  	 * @see SCIP_DECL_EXPRPRINT
851  	 */
852  	SCIP_EXPORT
853  	SCIP_DECL_EXPRPRINT(SCIPcallExprPrint);
854  	
855  	/** calls the curvature callback for an expression
856  	 *
857  	 * @see SCIP_DECL_EXPRCURVATURE
858  	 *
859  	 * Returns unknown curvature if callback not implemented.
860  	 */
861  	SCIP_EXPORT
862  	SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature);
863  	
864  	/** calls the monotonicity callback for an expression
865  	 *
866  	 * @see SCIP_DECL_EXPRMONOTONICITY
867  	 *
868  	 * Returns unknown monotonicity if callback not implemented.
869  	 */
870  	SCIP_EXPORT
871  	SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity);
872  	
873  	/** calls the eval callback for an expression with given values for children
874  	 *
875  	 * Does not iterates over expressions, but requires values for children to be given.
876  	 * Value is not stored in expression, but returned in `val`.
877  	 * If an evaluation error (division by zero, ...) occurs, this value will
878  	 * be set to `SCIP_INVALID`.
879  	 */
880  	SCIP_EXPORT
881  	SCIP_RETCODE SCIPcallExprEval(
882  	   SCIP*                 scip,               /**< SCIP data structure */
883  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
884  	   SCIP_Real*            childrenvalues,     /**< values for children */
885  	   SCIP_Real*            val                 /**< buffer to store evaluated value */
886  	   );
887  	
888  	/** calls the eval and fwdiff callback of an expression with given values for children
889  	 *
890  	 * Does not iterates over expressions, but requires values for children and direction to be given.
891  	 *
892  	 * Value is not stored in expression, but returned in `val`.
893  	 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
894  	 *
895  	 * Direction is not stored in expression, but returned in `dot`.
896  	 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
897  	 */
898  	SCIP_EXPORT
899  	SCIP_RETCODE SCIPcallExprEvalFwdiff(
900  	   SCIP*                 scip,               /**< SCIP data structure */
901  	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
902  	   SCIP_Real*            childrenvalues,     /**< values for children */
903  	   SCIP_Real*            direction,          /**< direction in which to differentiate */
904  	   SCIP_Real*            val,                /**< buffer to store evaluated value */
905  	   SCIP_Real*            dot                 /**< buffer to store derivative value */
906  	   );
907  	
908  	/** calls the interval evaluation callback for an expression
909  	 *
910  	 * @see SCIP_DECL_EXPRINTEVAL
911  	 *
912  	 * Returns entire interval if callback not implemented.
913  	 */
914  	SCIP_EXPORT
915  	SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval);
916  	
917  	/** calls the estimate callback for an expression
918  	 *
919  	 * @see SCIP_DECL_EXPRESTIMATE
920  	 *
921  	 * Returns without success if callback not implemented.
922  	 */
923  	SCIP_EXPORT
924  	SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate);
925  	
926  	/** calls the initial estimators callback for an expression
927  	 *
928  	 * @see SCIP_DECL_EXPRINITESTIMATES
929  	 *
930  	 * Returns no estimators if callback not implemented.
931  	 */
932  	SCIP_EXPORT
933  	SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates);
934  	
935  	/** calls the simplify callback for an expression
936  	 *
937  	 * @see SCIP_DECL_EXPRSIMPLIFY
938  	 *
939  	 * Returns unmodified expression if simplify callback not implemented.
940  	 *
941  	 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that.
942  	 */
943  	SCIP_EXPORT
944  	SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify);
945  	
946  	/** calls the reverse propagation callback for an expression
947  	 *
948  	 * @see SCIP_DECL_EXPRREVERSEPROP
949  	 *
950  	 * Returns unmodified `childrenbounds` if reverseprop callback not implemented.
951  	 */
952  	SCIP_EXPORT
953  	SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop);
954  	
955  	/** calls the symmetry information callback for an expression
956  	 *
957  	 * Returns NULL pointer if not implemented.
958  	 */
959  	SCIP_EXPORT
960  	SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData);
961  	
962  	#ifdef NDEBUG
963  	#define SCIPappendExprChild(scip, expr, child)               SCIPexprAppendChild((scip)->set, (scip)->mem->probmem, expr, child)
964  	#define SCIPreplaceExprChild(scip, expr, childidx, newchild) SCIPexprReplaceChild((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, childidx, newchild)
965  	#define SCIPremoveExprChildren(scip, expr)                   SCIPexprRemoveChildren((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
966  	#define SCIPduplicateExpr(scip, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) SCIPexprCopy((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->set, (scip)->stat, (scip)->mem->probmem, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata)
967  	#define SCIPduplicateExprShallow(scip, expr, copyexpr, ownercreate, ownercreatedata) SCIPexprDuplicateShallow((scip)->set, (scip)->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata)
968  	#define SCIPcaptureExpr(expr)                                SCIPexprCapture(expr)
969  	#define SCIPreleaseExpr(scip, expr)                          SCIPexprRelease((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
970  	#define SCIPisExprVar(scip, expr)                            SCIPexprIsVar((scip)->set, expr)
971  	#define SCIPisExprValue(scip, expr)                          SCIPexprIsValue((scip)->set, expr)
972  	#define SCIPisExprSum(scip, expr)                            SCIPexprIsSum((scip)->set, expr)
973  	#define SCIPisExprProduct(scip, expr)                        SCIPexprIsProduct((scip)->set, expr)
974  	#define SCIPisExprPower(scip, expr)                          SCIPexprIsPower((scip)->set, expr)
975  	#define SCIPprintExpr(scip, expr, file)                      SCIPexprPrint((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->messagehdlr, file, expr)
976  	#define SCIPevalExpr(scip, expr, sol, soltag)                SCIPexprEval((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag)
977  	#define SCIPgetExprNewSoltag(scip)                           (++((scip)->stat->exprlastsoltag))
978  	#define SCIPevalExprGradient(scip, expr, sol, soltag)        SCIPexprEvalGradient((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag)
979  	#define SCIPevalExprHessianDir(scip, expr, sol, soltag, direction) SCIPexprEvalHessianDir((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag, direction)
980  	#define SCIPevalExprActivity(scip, expr)                     SCIPexprEvalActivity((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
981  	#define SCIPcompareExpr(scip, expr1, expr2)                  SCIPexprCompare((scip)->set, expr1, expr2)
982  	#define SCIPsimplifyExpr(scip, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) SCIPexprSimplify((scip)->set, (scip)->stat, (scip)->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata)
983  	#define SCIPcallExprCurvature(scip, expr, exprcurvature, success, childcurv) SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, exprcurvature, success, childcurv)
984  	#define SCIPcallExprMonotonicity(scip, expr, childidx, result) SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, childidx, result)
985  	#define SCIPcallExprEval(scip, expr, childrenvalues, val)    SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, childrenvalues, NULL)
986  	#define SCIPcallExprEvalFwdiff(scip, expr, childrenvalues, direction, val, dot) SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, dot, childrenvalues, NULL, direction, NULL)
987  	#define SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, interval, intevalvar, intevalvardata)
988  	#define SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand) SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand)
989  	#define SCIPcallExprInitestimates(scip, expr, bounds, overestimate, coefs, constant, nreturned)  SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, overestimate, coefs, constant, nreturned)
990  	#define SCIPcallExprSimplify(scip, expr, simplifiedexpr, ownercreate, ownercreatedata)  SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, simplifiedexpr, ownercreate, ownercreatedata)
991  	#define SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, childrenbounds, infeasible)
992  	#define SCIPcallExprGetSymData(scip, expr, symdata) SCIPexprhdlrGetSymdata(SCIPexprGetHdlr(expr), (scip)->set, expr, symdata)
993  	#endif
994  	
995  	/** @} */
996  	
997  	
998  	/**@name Expression Iterator */
999  	/**@{ */
1000 	
1001 	/** creates an expression iterator */
1002 	SCIP_EXPORT
1003 	SCIP_RETCODE SCIPcreateExpriter(
1004 	   SCIP*                 scip,               /**< SCIP data structure */
1005 	   SCIP_EXPRITER**       iterator            /**< buffer to store expression iterator */
1006 	   );
1007 	
1008 	/** frees an expression iterator */
1009 	SCIP_EXPORT
1010 	void SCIPfreeExpriter(
1011 	   SCIP_EXPRITER**       iterator            /**< pointer to the expression iterator */
1012 	   );
1013 	
1014 	#ifdef NDEBUG
1015 	#define SCIPcreateExpriter(scip, iterator)  SCIPexpriterCreate((scip)->stat, (scip)->mem->probmem, iterator)
1016 	#define SCIPfreeExpriter(iterator)          SCIPexpriterFree(iterator)
1017 	#endif
1018 	
1019 	/** @} */
1020 	
1021 	
1022 	/**@name Quadratic Expressions */
1023 	/**@{ */
1024 	
1025 	/** checks whether an expression is quadratic
1026 	 *
1027 	 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions),
1028 	 * or a sum of terms where at least one is a square or a product.
1029 	 *
1030 	 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic.
1031 	 */
1032 	SCIP_EXPORT
1033 	SCIP_RETCODE SCIPcheckExprQuadratic(
1034 	   SCIP*                 scip,               /**< SCIP data structure */
1035 	   SCIP_EXPR*            expr,               /**< expression */
1036 	   SCIP_Bool*            isquadratic         /**< buffer to store result */
1037 	   );
1038 	
1039 	/** frees information on quadratic representation of an expression
1040 	 *
1041 	 * Before doing changes to an expression, it can be useful to call this function.
1042 	 */
1043 	SCIP_EXPORT
1044 	void SCIPfreeExprQuadratic(
1045 	   SCIP*                 scip,               /**< SCIP data structure */
1046 	   SCIP_EXPR*            expr                /**< expression */
1047 	   );
1048 	
1049 	/** evaluates quadratic term in a solution
1050 	 *
1051 	 * \note This requires that every expression used in the quadratic data is a variable expression.
1052 	 */
1053 	SCIP_EXPORT
1054 	SCIP_Real SCIPevalExprQuadratic(
1055 	   SCIP*                 scip,               /**< SCIP data structure */
1056 	   SCIP_EXPR*            expr,               /**< quadratic expression */
1057 	   SCIP_SOL*             sol                 /**< solution to evaluate, or NULL for LP solution */
1058 	   );
1059 	
1060 	/** prints quadratic expression */
1061 	SCIP_EXPORT
1062 	SCIP_RETCODE SCIPprintExprQuadratic(
1063 	   SCIP*                 scip,               /**< SCIP data structure */
1064 	   SCIP_EXPR*            expr                /**< quadratic expression */
1065 	   );
1066 	
1067 	/** checks the curvature of the quadratic expression
1068 	 *
1069 	 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
1070 	 * If Q is
1071 	 * - semidefinite positive -> curv is set to convex,
1072 	 * - semidefinite negative -> curv is set to concave,
1073 	 * - otherwise -> curv is set to unknown.
1074 	 *
1075 	 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
1076 	 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
1077 	 */
1078 	SCIP_EXPORT
1079 	SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(
1080 	   SCIP*                 scip,               /**< SCIP data structure */
1081 	   SCIP_EXPR*            expr,               /**< quadratic expression */
1082 	   SCIP_EXPRCURV*        curv,               /**< pointer to store the curvature of quadratics */
1083 	   SCIP_HASHMAP*         assumevarfixed,     /**< hashmap containing variables that should be assumed to be fixed, or NULL */
1084 	   SCIP_Bool             storeeigeninfo      /**< whether the eigenvalues and eigenvectors should be stored */
1085 	   );
1086 	
1087 	#ifdef NDEBUG
1088 	#define SCIPcheckExprQuadratic(scip, expr, isquadratic)  SCIPexprCheckQuadratic((scip)->set, (scip)->mem->probmem, expr, isquadratic)
1089 	#define SCIPfreeExprQuadratic(scip, expr)                SCIPexprFreeQuadratic((scip)->mem->probmem, expr)
1090 	#define SCIPcomputeExprQuadraticCurvature(scip, expr, curv, assumevarfixed, storeeigeninfo)  SCIPexprComputeQuadraticCurvature((scip)->set, (scip)->mem->probmem, (scip)->mem->buffer, (scip)->messagehdlr, expr, curv, assumevarfixed, storeeigeninfo)
1091 	#endif
1092 	
1093 	/** @} */
1094 	
1095 	/**@name Monomial Expressions */
1096 	/**@{ */
1097 	
1098 	/** returns a monomial representation of a product expression
1099 	 *
1100 	 * The array to store all factor expressions needs to be of size the number of
1101 	 * children in the expression which is given by SCIPexprGetNChildren().
1102 	 *
1103 	 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where
1104 	 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can
1105 	 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents.
1106 	 *
1107 	 * A non-trivial monomial is a product of a least two expressions.
1108 	 */
1109 	SCIP_EXPORT
1110 	SCIP_RETCODE SCIPgetExprMonomialData(
1111 	   SCIP*                 scip,               /**< SCIP data structure */
1112 	   SCIP_EXPR*            expr,               /**< expression */
1113 	   SCIP_Real*            coef,               /**< coefficient \f$c\f$ */
1114 	   SCIP_Real*            exponents,          /**< exponents \f$\alpha\f$ */
1115 	   SCIP_EXPR**           factors             /**< factor expressions \f$x\f$ */
1116 	   );
1117 	
1118 	#ifdef NDEBUG
1119 	#define SCIPgetExprMonomialData(scip, expr, coef, exponents, factors)  SCIPexprGetMonomialData((scip)->set, (scip)->mem->probmem, expr, coef, exponents, factors)
1120 	#endif
1121 	
1122 	/** @} */
1123 	
1124 	/** @} */
1125 	
1126 	#ifdef __cplusplus
1127 	}
1128 	#endif
1129 	
1130 	#endif /* SCIP_SCIP_EXPR_H_ */
1131