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.c
26   	 * @ingroup OTHER_CFILES
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   	#include <string.h>
35   	#include <ctype.h>
36   	
37   	#include "scip/scip_expr.h"
38   	#include "scip/expr.h"
39   	#include "scip/set.h"
40   	#include "scip/misc.h"
41   	#include "scip/scip_copy.h"
42   	#include "scip/scip_mem.h"
43   	#include "scip/scip_message.h"
44   	#include "scip/scip_prob.h"
45   	#include "scip/scip_var.h"
46   	#include "scip/scip_sol.h"
47   	#include "scip/pub_var.h"
48   	#include "scip/struct_scip.h"
49   	#include "scip/struct_mem.h"
50   	#include "scip/struct_stat.h"
51   	
52   	/* core expression handler plugins */
53   	#include "scip/expr_value.h"
54   	#include "scip/expr_var.h"
55   	#include "scip/expr_sum.h"
56   	#include "scip/expr_product.h"
57   	#include "scip/expr_pow.h"
58   	
59   	/* #define PARSE_DEBUG */
60   	
61   	/*lint -e440*/
62   	/*lint -e441*/
63   	
64   	/*
65   	 * local functions
66   	 */
67   	
68   	/** variable mapping data passed on during copying expressions when copying SCIP instances */
69   	typedef struct
70   	{
71   	   SCIP_HASHMAP*         varmap;             /**< SCIP_HASHMAP mapping variables of the source SCIP to corresponding
72   	                                                  variables of the target SCIP */
73   	   SCIP_HASHMAP*         consmap;            /**< SCIP_HASHMAP mapping constraints of the source SCIP to corresponding
74   	                                                  constraints of the target SCIP */
75   	   SCIP_Bool             global;             /**< should a global or a local copy be created */
76   	   SCIP_Bool             valid;              /**< indicates whether every variable copy was valid */
77   	} COPY_MAPEXPR_DATA;
78   	
79   	/** variable expression mapping callback to call when copying expressions (within same or different SCIPs) */
80   	static
81   	SCIP_DECL_EXPR_MAPEXPR(copyVarExpr)
82   	{
83   	   COPY_MAPEXPR_DATA* data;
84   	   SCIP_Bool valid;
85   	   SCIP_VAR* targetvar;
86   	
87   	   assert(sourcescip != NULL);
88   	   assert(sourceexpr != NULL);
89   	   assert(targetscip != NULL);
90   	   assert(targetexpr != NULL);
91   	   assert(mapexprdata != NULL);
92   	
93   	   *targetexpr = NULL;
94   	
95   	   if( !SCIPisExprVar(sourcescip, sourceexpr) )
96   	      return SCIP_OKAY;
97   	
98   	   data = (COPY_MAPEXPR_DATA*)mapexprdata;
99   	
100  	   SCIP_CALL( SCIPgetVarCopy(sourcescip, targetscip, SCIPgetVarExprVar(sourceexpr), &targetvar, data->varmap,
101  	         data->consmap, data->global, &valid) );
102  	   assert(targetvar != NULL);
103  	
104  	   /* if copy was not valid, store so in mapvar data */
105  	   if( !valid )
106  	      data->valid = FALSE;
107  	
108  	   SCIP_CALL( SCIPcreateExprVar(targetscip, targetexpr, targetvar, ownercreate, ownercreatedata) );
109  	
110  	   return SCIP_OKAY;
111  	}
112  	
113  	
114  	/** @name Parsing methods (internal)
115  	 * @{
116  	 * Here is an attempt at defining the grammar of an expression.
117  	 * We use upper case names for variables (in the grammar sense) and terminals are between "".
118  	 * Loosely speaking, a Base will be any "block", a Factor is a Base to a power, a Term is a product of Factors
119  	 * and an Expression is a sum of terms.
120  	 * The actual definition:
121  	 * <pre>
122  	 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
123  	 * Term       -> Factor { ("*" | "/" ) Factor }
124  	 * Factor     -> Base [ "^" "number" | "^(" "number" ")" ]
125  	 * Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
126  	 * </pre>
127  	 * where [a|b] means a or b or none, (a|b) means a or b, {a} means 0 or more a.
128  	 *
129  	 * Note that Op and OpExpression are undefined. Op corresponds to the name of an expression handler and
130  	 * OpExpression to whatever string the expression handler accepts (through its parse method).
131  	 *
132  	 * parse(Expr|Term|Base) returns an SCIP_EXPR
133  	 *
134  	 * @todo We can change the grammar so that Factor becomes base and we allow a Term to be
135  	 *       <pre> Term       -> Factor { ("*" | "/" | "^") Factor } </pre>
136  	 */
137  	
138  	/*lint -emacro(681,debugParse) */
139  	/*lint -emacro(506,debugParse) */
140  	/*lint -emacro(774,debugParse) */
141  	#ifdef PARSE_DEBUG
142  	#define debugParse                      printf
143  	#else
144  	#define debugParse                      while( FALSE ) printf
145  	#endif
146  	
147  	/* forward declaration */
148  	static
149  	SCIP_RETCODE parseExpr(
150  	   SCIP*                 scip,               /**< SCIP data structure */
151  	   SCIP_HASHMAP*         vartoexprvarmap,    /**< hashmap to map between scip vars and var expressions */
152  	   const char*           expr,               /**< expr that we are parsing */
153  	   const char**          newpos,             /**< buffer to store the position of expr where we finished reading */
154  	   SCIP_EXPR**           exprtree,           /**< buffer to store the expr parsed by Expr */
155  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
156  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
157  	   );
158  	
159  	/** Parses base to build a value, variable, sum, or function-like ("func(...)") expression.
160  	 * <pre>
161  	 * Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
162  	 * </pre>
163  	 */
164  	static
165  	SCIP_RETCODE parseBase(
166  	   SCIP*                 scip,               /**< SCIP data structure */
167  	   SCIP_HASHMAP*         vartoexprvarmap,    /**< hashmap to map between SCIP vars and var expressions */
168  	   const char*           expr,               /**< expr that we are parsing */
169  	   const char**          newpos,             /**< buffer to store the position of expr where we finished reading */
170  	   SCIP_EXPR**           basetree,           /**< buffer to store the expr parsed by Base */
171  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
172  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
173  	   )
174  	{
175  	   debugParse("parsing base from %s\n", expr);
176  	
177  	   /* ignore whitespace */
178  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
179  	
180  	   if( *expr == '\0' )
181  	   {
182  	      SCIPerrorMessage("Unexpected end of expression string\n");
183  	      return SCIP_READERROR;
184  	   }
185  	
186  	   if( *expr == '<' )
187  	   {
188  	      /* parse a variable */
189  	      SCIP_VAR* var;
190  	
191  	      SCIP_CALL( SCIPparseVarName(scip, expr, &var, (char**)newpos) );
192  	
193  	      if( var == NULL )
194  	      {
195  	         SCIPerrorMessage("Could not find variable with name '%s'\n", expr);
196  	         return SCIP_READERROR;
197  	      }
198  	
199  	      expr = *newpos;
200  	
201  	      /* check if we have already created an expression out of this var */
202  	      if( SCIPhashmapExists(vartoexprvarmap, (void*)var) )
203  	      {
204  	         debugParse("Variable <%s> has already been parsed, capturing its expression\n", SCIPvarGetName(var));
205  	         *basetree = (SCIP_EXPR*)SCIPhashmapGetImage(vartoexprvarmap, (void*)var);
206  	         SCIPexprCapture(*basetree);
207  	      }
208  	      else
209  	      {
210  	         debugParse("First time parsing variable <%s>, creating varexpr and adding it to hashmap\n", SCIPvarGetName(var));
211  	         /* intentionally not using createExprVar here, since parsed expressions are not part of a constraint
212  	          * (they will be copied when a constraint is created)
213  	          */
214  	         SCIP_CALL( SCIPcreateExprVar(scip, basetree, var, ownercreate, ownercreatedata) );
215  	         SCIP_CALL( SCIPhashmapInsert(vartoexprvarmap, (void*)var, (void*)(*basetree)) );
216  	      }
217  	   }
218  	   else if( *expr == '(' )
219  	   {
220  	      /* parse expression */
221  	      SCIP_CALL( parseExpr(scip, vartoexprvarmap, ++expr, newpos, basetree, ownercreate, ownercreatedata) );
222  	      expr = *newpos;
223  	
224  	      /* expect ')' */
225  	      if( *expr != ')' )
226  	      {
227  	         SCIPerrorMessage("Read a '(', parsed expression inside --> expecting closing ')'. Got <%c>: rest of string <%s>\n", *expr, expr);
228  	         SCIP_CALL( SCIPreleaseExpr(scip, basetree) );
229  	         return SCIP_READERROR;
230  	      }
231  	      ++expr;
232  	      debugParse("Done parsing expression, continue with <%s>\n", expr);
233  	   }
234  	   else if( isdigit(*expr) )
235  	   {
236  	      /* parse number */
237  	      SCIP_Real value;
238  	      if( !SCIPstrToRealValue(expr, &value, (char**)&expr) )
239  	      {
240  	         SCIPerrorMessage("error parsing number from <%s>\n", expr);
241  	         return SCIP_READERROR;
242  	      }
243  	      debugParse("Parsed value %g, creating a value-expression.\n", value);
244  	      SCIP_CALL( SCIPcreateExprValue(scip, basetree, value, ownercreate, ownercreatedata) );
245  	   }
246  	   else if( isalpha(*expr) )
247  	   {
248  	      /* a (function) name is coming, should find exprhandler with such name */
249  	      int i;
250  	      char operatorname[SCIP_MAXSTRLEN];
251  	      SCIP_EXPRHDLR* exprhdlr;
252  	      SCIP_Bool success;
253  	
254  	      /* get name */
255  	      i = 0;
256  	      while( *expr != '(' && *expr != '\0' && !isspace(*expr)
257  	             && !( *expr == '\\' && *(expr+1) != '\0' && strchr(SCIP_SPACECONTROL, *(expr+1)) ) )
258  	      {
259  	         operatorname[i] = *expr;
260  	         ++expr;
261  	         ++i;
262  	      }
263  	      operatorname[i] = '\0';
264  	
265  	      /* after name we must see a '(' */
266  	      if( *expr != '(' )
267  	      {
268  	         SCIPerrorMessage("Expected '(' after operator name <%s>, but got %s.\n", operatorname, expr);
269  	         return SCIP_READERROR;
270  	      }
271  	
272  	      /* search for expression handler */
273  	      exprhdlr = SCIPfindExprhdlr(scip, operatorname);
274  	
275  	      /* check expression handler exists and has a parsing method */
276  	      if( exprhdlr == NULL )
277  	      {
278  	         SCIPerrorMessage("No expression handler with name <%s> found.\n", operatorname);
279  	         return SCIP_READERROR;
280  	      }
281  	
282  	      ++expr;
283  	      SCIP_CALL( SCIPexprhdlrParseExpr(exprhdlr, scip->set, expr, newpos, basetree, &success, ownercreate, ownercreatedata) );
284  	
285  	      if( !success )
286  	      {
287  	         SCIPerrorMessage("Error while expression handler <%s> was parsing %s\n", operatorname, expr);
288  	         assert(*basetree == NULL);
289  	         return SCIP_READERROR;
290  	      }
291  	      expr = *newpos;
292  	
293  	      /* we should see the ')' of Op "(" OpExpression ") */
294  	      assert(*expr == ')');
295  	
296  	      /* move one character forward */
297  	      ++expr;
298  	   }
299  	   else
300  	   {
301  	      /* Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ") */
302  	      SCIPerrorMessage("Expected a number, (expression), <varname>, Opname(Opexpr), instead got <%c> from %s\n", *expr, expr);
303  	      return SCIP_READERROR;
304  	   }
305  	
306  	   *newpos = expr;
307  	
308  	   return SCIP_OKAY;
309  	}
310  	
311  	/** Parses a factor and builds a product-expression if there is an exponent, otherwise returns the base expression.
312  	 * <pre>
313  	 * Factor -> Base [ "^" "number" | "^(" "number" ")" ]
314  	 * </pre>
315  	 */
316  	static
317  	SCIP_RETCODE parseFactor(
318  	   SCIP*                 scip,               /**< SCIP data structure */
319  	   SCIP_Bool             isdenominator,      /**< whether factor is in the denominator */
320  	   SCIP_HASHMAP*         vartoexprvarmap,    /**< hashmap to map between scip vars and var expressions */
321  	   const char*           expr,               /**< expr that we are parsing */
322  	   const char**          newpos,             /**< buffer to store the position of expr where we finished reading */
323  	   SCIP_EXPR**           factortree,         /**< buffer to store the expr parsed by Factor */
324  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
325  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
326  	   )
327  	{
328  	   SCIP_EXPR*  basetree;
329  	   SCIP_Real exponent;
330  	
331  	   debugParse("parsing factor from %s\n", expr);
332  	
333  	   if( *expr == '\0' )
334  	   {
335  	      SCIPerrorMessage("Unexpected end of expression string.\n");
336  	      return SCIP_READERROR;
337  	   }
338  	
339  	   /* parse Base */
340  	   /* ignore whitespace */
341  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
342  	
343  	   SCIP_CALL( parseBase(scip, vartoexprvarmap, expr, newpos, &basetree, ownercreate, ownercreatedata) );
344  	   expr = *newpos;
345  	
346  	   /* check if there is an exponent */
347  	   /* ignore whitespace */
348  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
349  	
350  	   if( *expr == '^' )
351  	   {
352  	      ++expr;
353  	      SCIP_CALL( SCIPskipSpace((char**)&expr) );
354  	
355  	      if( *expr == '\0' )
356  	      {
357  	         SCIPerrorMessage("Unexpected end of expression string after '^'.\n");
358  	         SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
359  	         return SCIP_READERROR;
360  	      }
361  	
362  	      if( *expr == '(' )
363  	      {
364  	         ++expr;
365  	
366  	         /* it is exponent with parenthesis; expect number possibly starting with + or - */
367  	         if( !SCIPstrToRealValue(expr, &exponent, (char**)&expr) )
368  	         {
369  	            SCIPerrorMessage("error parsing number from <%s>\n", expr);
370  	            SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
371  	            return SCIP_READERROR;
372  	         }
373  	
374  	         /* expect the ')' */
375  	         SCIP_CALL( SCIPskipSpace((char**)&expr) );
376  	         if( *expr != ')' )
377  	         {
378  	            SCIPerrorMessage("error in parsing exponent: expected ')', received <%c> from <%s>\n", *expr,  expr);
379  	            SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
380  	            return SCIP_READERROR;
381  	         }
382  	         ++expr;
383  	      }
384  	      else
385  	      {
386  	         /* no parenthesis, we should see just a positive number */
387  	
388  	         /* expect a digit */
389  	         if( isdigit(*expr) )
390  	         {
391  	            if( !SCIPstrToRealValue(expr, &exponent, (char**)&expr) )
392  	            {
393  	               SCIPerrorMessage("error parsing number from <%s>\n", expr);
394  	               SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
395  	               return SCIP_READERROR;
396  	            }
397  	         }
398  	         else
399  	         {
400  	            SCIPerrorMessage("error in parsing exponent, expected a digit, received <%c> from <%s>\n", *expr,  expr);
401  	            SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
402  	            return SCIP_READERROR;
403  	         }
404  	      }
405  	
406  	      debugParse("parsed the exponent %g\n", exponent); /*lint !e506 !e681*/
407  	   }
408  	   else
409  	   {
410  	      /* there is no explicit exponent */
411  	      exponent = 1.0;
412  	   }
413  	   *newpos = expr;
414  	
415  	   /* multiply with -1 when we are in the denominator */
416  	   if( isdenominator )
417  	      exponent *= -1.0;
418  	
419  	   /* create power */
420  	   if( exponent != 1.0 )
421  	   {
422  	      SCIP_CALL( SCIPcreateExprPow(scip, factortree, basetree, exponent, ownercreate, ownercreatedata) );
423  	      SCIP_CALL( SCIPreleaseExpr(scip, &basetree) );
424  	   }
425  	   else
426  	      /* Factor consists of this unique Base */
427  	      *factortree = basetree;
428  	
429  	   return SCIP_OKAY;
430  	}
431  	
432  	/** Parses a term and builds a product-expression, where each factor is a child.
433  	 * <pre>
434  	 * Term -> Factor { ("*" | "/" ) Factor }
435  	 * </pre>
436  	 */
437  	static
438  	SCIP_RETCODE parseTerm(
439  	   SCIP*                 scip,               /**< SCIP data structure */
440  	   SCIP_HASHMAP*         vartoexprvarmap,    /**< hashmap to map between scip vars and var expressions */
441  	   const char*           expr,               /**< expr that we are parsing */
442  	   const char**          newpos,             /**< buffer to store the position of expr where we finished reading */
443  	   SCIP_EXPR**           termtree,           /**< buffer to store the expr parsed by Term */
444  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
445  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
446  	   )
447  	{
448  	   SCIP_EXPR* factortree;
449  	
450  	   debugParse("parsing term from %s\n", expr);
451  	
452  	   /* parse Factor */
453  	   /* ignore whitespace */
454  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
455  	
456  	   SCIP_CALL( parseFactor(scip, FALSE, vartoexprvarmap, expr, newpos, &factortree, ownercreate, ownercreatedata) );
457  	   expr = *newpos;
458  	
459  	   debugParse("back to parsing Term, continue parsing from %s\n", expr);
460  	
461  	   /* check if Terms has another Factor incoming */
462  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
463  	   if( *expr == '*' || *expr == '/' )
464  	   {
465  	      /* initialize termtree as a product expression with a single term, so we can append the extra Factors */
466  	      SCIP_CALL( SCIPcreateExprProduct(scip, termtree, 1, &factortree, 1.0, ownercreate, ownercreatedata) );
467  	      SCIP_CALL( SCIPreleaseExpr(scip, &factortree) );
468  	
469  	      /* loop: parse Factor, find next symbol */
470  	      do
471  	      {
472  	         SCIP_RETCODE retcode;
473  	         SCIP_Bool isdivision;
474  	
475  	         isdivision = (*expr == '/') ? TRUE : FALSE;
476  	
477  	         debugParse("while parsing term, read char %c\n", *expr); /*lint !e506 !e681*/
478  	
479  	         ++expr;
480  	         retcode = parseFactor(scip, isdivision, vartoexprvarmap, expr, newpos, &factortree, ownercreate, ownercreatedata);
481  	
482  	         /* release termtree, if parseFactor fails with a read-error */
483  	         if( retcode == SCIP_READERROR )
484  	         {
485  	            SCIP_CALL( SCIPreleaseExpr(scip, termtree) );
486  	         }
487  	         SCIP_CALL( retcode );
488  	
489  	         /* append newly created factor */
490  	         SCIP_CALL( SCIPappendExprChild(scip, *termtree, factortree) );
491  	         SCIP_CALL( SCIPreleaseExpr(scip, &factortree) );
492  	
493  	         /* find next symbol */
494  	         expr = *newpos;
495  	         SCIP_CALL( SCIPskipSpace((char**)&expr) );
496  	      }
497  	      while( *expr == '*' || *expr == '/' );
498  	   }
499  	   else
500  	   {
501  	      /* Term consists of this unique factor */
502  	      *termtree = factortree;
503  	   }
504  	
505  	   *newpos = expr;
506  	
507  	   return SCIP_OKAY;
508  	}
509  	
510  	/** parses an expression and builds a sum-expression with children
511  	 *
512  	 * <pre>
513  	 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
514  	 * </pre>
515  	 */
516  	static
517  	SCIP_RETCODE parseExpr(
518  	   SCIP*                 scip,               /**< SCIP data structure */
519  	   SCIP_HASHMAP*         vartoexprvarmap,    /**< hashmap to map between scip vars and var expressions */
520  	   const char*           expr,               /**< expr that we are parsing */
521  	   const char**          newpos,             /**< buffer to store the position of expr where we finished reading */
522  	   SCIP_EXPR**           exprtree,           /**< buffer to store the expr parsed by Expr */
523  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
524  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
525  	   )
526  	{
527  	   SCIP_Real sign;
528  	   SCIP_EXPR* termtree;
529  	
530  	   debugParse("parsing expression %s\n", expr); /*lint !e506 !e681*/
531  	
532  	   /* ignore whitespace */
533  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
534  	
535  	   /* if '+' or '-', store it */
536  	   sign = 1.0;
537  	   if( *expr == '+' || *expr == '-' )
538  	   {
539  	      debugParse("while parsing expression, read char %c\n", *expr); /*lint !e506 !e681*/
540  	      sign = *expr == '+' ? 1.0 : -1.0;
541  	      ++expr;
542  	   }
543  	
544  	   SCIP_CALL( parseTerm(scip, vartoexprvarmap, expr, newpos, &termtree, ownercreate, ownercreatedata) );
545  	   expr = *newpos;
546  	
547  	   debugParse("back to parsing expression (we have the following term), continue parsing from %s\n", expr); /*lint !e506 !e681*/
548  	
549  	   /* check if Expr has another Term incoming */
550  	   SCIP_CALL( SCIPskipSpace((char**)&expr) );
551  	   if( *expr == '+' || *expr == '-' )
552  	   {
553  	      if( SCIPexprIsValue(scip->set, termtree) )
554  	      {
555  	         /* initialize exprtree as a sum expression with a constant only, so we can append the following terms */
556  	         SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 0, NULL, NULL, sign * SCIPgetValueExprValue(termtree), ownercreate, ownercreatedata) );
557  	         SCIP_CALL( SCIPreleaseExpr(scip, &termtree) );
558  	      }
559  	      else
560  	      {
561  	         /* initialize exprtree as a sum expression with a single term, so we can append the following terms */
562  	         SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 1, &termtree, &sign, 0.0, ownercreate, ownercreatedata) );
563  	         SCIP_CALL( SCIPreleaseExpr(scip, &termtree) );
564  	      }
565  	
566  	      /* loop: parse Term, find next symbol */
567  	      do
568  	      {
569  	         SCIP_RETCODE retcode;
570  	         SCIP_Real coef;
571  	
572  	         /* check if we have a "coef * <term>" */
573  	         if( SCIPstrToRealValue(expr, &coef, (char**)newpos) )
574  	         {
575  	            SCIP_CALL( SCIPskipSpace((char**)newpos) );
576  	
577  	            if( **newpos != '*' )
578  	            {
579  	               /* no '*', so fall back to parsing term after sign */
580  	               coef = (*expr == '+') ? 1.0 : -1.0;
581  	               ++expr;
582  	            }
583  	            else
584  	            {
585  	               /* keep coefficient in coef and continue parsing term after coefficient */
586  	               expr = (*newpos)+1;
587  	
588  	               SCIP_CALL( SCIPskipSpace((char**)&expr) );
589  	            }
590  	         }
591  	         else
592  	         {
593  	            coef = (*expr == '+') ? 1.0 : -1.0;
594  	            ++expr;
595  	         }
596  	
597  	         debugParse("while parsing expression, read coefficient %g\n", coef); /*lint !e506 !e681*/
598  	
599  	         retcode = parseTerm(scip, vartoexprvarmap, expr, newpos, &termtree, ownercreate, ownercreatedata);
600  	
601  	         /* release exprtree if parseTerm fails with an read-error */
602  	         if( retcode == SCIP_READERROR )
603  	         {
604  	            SCIP_CALL( SCIPreleaseExpr(scip, exprtree) );
605  	         }
606  	         SCIP_CALL( retcode );
607  	
608  	         /* append newly created term */
609  	         SCIP_CALL( SCIPappendExprSumExpr(scip, *exprtree, termtree, coef) );
610  	         SCIP_CALL( SCIPreleaseExpr(scip, &termtree) );
611  	
612  	         /* find next symbol */
613  	         expr = *newpos;
614  	         SCIP_CALL( SCIPskipSpace((char**)&expr) );
615  	      } while( *expr == '+' || *expr == '-' );
616  	   }
617  	   else
618  	   {
619  	      /* Expr consists of this unique ['+' | '-'] Term */
620  	      if( sign  < 0.0 )
621  	      {
622  	         assert(sign == -1.0);
623  	         SCIP_CALL( SCIPcreateExprSum(scip, exprtree, 1, &termtree, &sign, 0.0, ownercreate, ownercreatedata) );
624  	         SCIP_CALL( SCIPreleaseExpr(scip, &termtree) );
625  	      }
626  	      else
627  	         *exprtree = termtree;
628  	   }
629  	
630  	   *newpos = expr;
631  	
632  	   return SCIP_OKAY;
633  	}
634  	
635  	/** @} */  /* end of parsing methods */
636  	
637  	/** @name Simplify methods (internal)
638  	 * @{
639  	 */
640  	
641  	/** returns an equivalent expression for a given expression if possible
642  	 *
643  	 * it adds the expression to key2expr if the map does not contain the key
644  	 */
645  	static
646  	SCIP_RETCODE findEqualExpr(
647  	   SCIP_SET*             set,                /**< global SCIP settings */
648  	   SCIP_EXPR*            expr,               /**< expression to replace */
649  	   SCIP_MULTIHASH*       key2expr,           /**< mapping of hashes to expressions */
650  	   SCIP_EXPR**           newexpr             /**< pointer to store an equivalent expression (NULL if there is none) */
651  	   )
652  	{  /*lint --e{438}*/
653  	   SCIP_MULTIHASHLIST* multihashlist;
654  	
655  	   assert(set != NULL);
656  	   assert(expr != NULL);
657  	   assert(key2expr != NULL);
658  	   assert(newexpr != NULL);
659  	
660  	   *newexpr = NULL;
661  	   multihashlist = NULL;
662  	   do
663  	   {
664  	      /* search for an equivalent expression */
665  	      *newexpr = (SCIP_EXPR*)(SCIPmultihashRetrieveNext(key2expr, &multihashlist, (void*)expr));
666  	
667  	      if( *newexpr == NULL )
668  	      {
669  	         /* processed all expressions like expr from hash table, so insert expr */
670  	         SCIP_CALL( SCIPmultihashInsert(key2expr, (void*) expr) );
671  	         break;
672  	      }
673  	      else if( expr != *newexpr )
674  	      {
675  	         assert(SCIPexprCompare(set, expr, *newexpr) == 0);
676  	         break;
677  	      }
678  	      else
679  	      {
680  	         /* can not replace expr since it is already contained in the hashtablelist */
681  	         assert(expr == *newexpr);
682  	         *newexpr = NULL;
683  	         break;
684  	      }
685  	   }
686  	   while( TRUE ); /*lint !e506*/
687  	
688  	   return SCIP_OKAY;
689  	}
690  	
691  	/** userdata for multihash for common subexpression */
692  	typedef struct
693  	{
694  	   SCIP_SET*      set;
695  	   SCIP_EXPRITER* hashiterator;
696  	} COMMONSUBEXPR_HASH_DATA;
697  	
698  	/** get key of hash element */
699  	static
700  	SCIP_DECL_HASHGETKEY(hashCommonSubexprGetKey)
701  	{
702  	   return elem;
703  	}  /*lint !e715*/
704  	
705  	/** checks if two expressions are structurally the same */
706  	static
707  	SCIP_DECL_HASHKEYEQ(hashCommonSubexprEq)
708  	{
709  	   COMMONSUBEXPR_HASH_DATA* data;
710  	   SCIP_EXPR* expr1;
711  	   SCIP_EXPR* expr2;
712  	
713  	   data = (COMMONSUBEXPR_HASH_DATA*)userptr;
714  	   assert(data != NULL);
715  	
716  	   expr1 = (SCIP_EXPR*)key1;
717  	   expr2 = (SCIP_EXPR*)key2;
718  	   assert(expr1 != NULL);
719  	   assert(expr2 != NULL);
720  	
721  	   return expr1 == expr2 || SCIPexprCompare(data->set, expr1, expr2) == 0;
722  	}  /*lint !e715*/
723  	
724  	/** get value of hash element when comparing with another expression */
725  	static
726  	SCIP_DECL_HASHKEYVAL(hashCommonSubexprKeyval)
727  	{
728  	   COMMONSUBEXPR_HASH_DATA* data;
729  	   SCIP_EXPR* expr;
730  	
731  	   expr = (SCIP_EXPR*) key;
732  	   assert(expr != NULL);
733  	
734  	   data = (COMMONSUBEXPR_HASH_DATA*) userptr;
735  	   assert(data != NULL);
736  	
737  	   return SCIPexpriterGetExprUserData(data->hashiterator, expr).uintval;
738  	}  /*lint !e715*/
739  	
740  	/** hashes an expression using an already existing iterator
741  	 *
742  	 * The iterator must by of type DFS with allowrevisit=FALSE and only the leaveexpr stage enabled.
743  	 * The hashes of all visited expressions will be stored in the iterators expression data.
744  	 */
745  	static
746  	SCIP_RETCODE hashExpr(
747  	   SCIP_SET*             set,                /**< global SCIP settings */
748  	   BMS_BUFMEM*           bufmem,             /**< buffer memory */
749  	   SCIP_EXPR*            expr,               /**< expression to hash */
750  	   SCIP_EXPRITER*        hashiterator,       /**< iterator to use for hashing */
751  	   int*                  nvisitedexprs       /**< counter to increment by the number of expressions visited, or NULL */
752  	   )
753  	{
754  	   SCIP_EXPRITER_USERDATA iterdata;
755  	   unsigned int* childrenhashes;
756  	   int childrenhashessize;
757  	   int i;
758  	
759  	   assert(set != NULL);
760  	   assert(expr != NULL);
761  	   assert(hashiterator != NULL);
762  	
763  	   childrenhashessize = 5;
764  	   SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &childrenhashes, childrenhashessize) );
765  	
766  	   for( expr = SCIPexpriterRestartDFS(hashiterator, expr); !SCIPexpriterIsEnd(hashiterator); expr = SCIPexpriterGetNext(hashiterator) ) /*lint !e441*/
767  	   {
768  	      assert(SCIPexpriterGetStageDFS(hashiterator) == SCIP_EXPRITER_LEAVEEXPR);
769  	
770  	      if( nvisitedexprs != NULL )
771  	         ++*nvisitedexprs;
772  	
773  	      /* collect hashes of children */
774  	      if( childrenhashessize < SCIPexprGetNChildren(expr) )
775  	      {
776  	         childrenhashessize = SCIPsetCalcMemGrowSize(set, SCIPexprGetNChildren(expr));
777  	         SCIP_ALLOC( BMSreallocBufferMemoryArray(bufmem, &childrenhashes, childrenhashessize) );
778  	      }
779  	      for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
780  	         childrenhashes[i] = SCIPexpriterGetExprUserData(hashiterator, SCIPexprGetChildren(expr)[i]).uintval;
781  	
782  	      SCIP_CALL( SCIPexprhdlrHashExpr(SCIPexprGetHdlr(expr), set, expr, &iterdata.uintval, childrenhashes) );
783  	
784  	      SCIPexpriterSetCurrentUserData(hashiterator, iterdata);
785  	   }
786  	
787  	   BMSfreeBufferMemoryArray(bufmem, &childrenhashes);
788  	
789  	   return SCIP_OKAY;
790  	}
791  	
792  	/** @} */  /* end of simplify methods */
793  	
794  	/*
795  	 * public functions
796  	 */
797  	
798  	/**@addtogroup PublicExprHandlerMethods
799  	 * @{
800  	 */
801  	
802  	#ifdef NDEBUG
803  	#undef SCIPgetExprhdlrs
804  	#undef SCIPgetNExprhdlrs
805  	#undef SCIPfindExprhdlr
806  	#undef SCIPgetExprhdlrVar
807  	#undef SCIPgetExprhdlrValue
808  	#undef SCIPgetExprhdlrSum
809  	#undef SCIPgetExprhdlrProduct
810  	#undef SCIPgetExprhdlrPower
811  	#endif
812  	
813  	/** creates the handler for an expression handler and includes it into SCIP */
814  	SCIP_RETCODE SCIPincludeExprhdlr(
815  	   SCIP*                 scip,               /**< SCIP data structure */
816  	   SCIP_EXPRHDLR**       exprhdlr,           /**< buffer where to store created expression handler */
817  	   const char*           name,               /**< name of expression handler (must not be NULL) */
818  	   const char*           desc,               /**< description of expression handler (can be NULL) */
819  	   unsigned int          precedence,         /**< precedence of expression operation (used for printing) */
820  	   SCIP_DECL_EXPREVAL((*eval)),              /**< point evaluation callback (must not be NULL) */
821  	   SCIP_EXPRHDLRDATA*    data                /**< data of expression handler (can be NULL) */
822  	   )
823  	{
824  	   assert(scip != NULL);
825  	   assert(scip->mem != NULL);
826  	   assert(exprhdlr != NULL);
827  	
828  	   SCIP_CALL( SCIPexprhdlrCreate(scip->mem->setmem, exprhdlr, name, desc, precedence, eval, data) );
829  	   assert(*exprhdlr != NULL);
830  	
831  	   SCIP_CALL( SCIPsetIncludeExprhdlr(scip->set, *exprhdlr) );
832  	
833  	   return SCIP_OKAY;
834  	}
835  	
836  	/** gives expression handlers */
837  	SCIP_EXPRHDLR** SCIPgetExprhdlrs(
838  	   SCIP*                 scip                /**< SCIP data structure */
839  	   )
840  	{
841  	   assert(scip != NULL);
842  	   assert(scip->set != NULL);
843  	
844  	   return scip->set->exprhdlrs;
845  	}
846  	
847  	/** gives number of expression handlers */
848  	int SCIPgetNExprhdlrs(
849  	   SCIP*                 scip                /**< SCIP data structure */
850  	   )
851  	{
852  	   assert(scip != NULL);
853  	   assert(scip->set != NULL);
854  	
855  	   return scip->set->nexprhdlrs;
856  	}
857  	
858  	/** returns an expression handler of a given name (or NULL if not found) */
859  	SCIP_EXPRHDLR* SCIPfindExprhdlr(
860  	   SCIP*                 scip,               /**< SCIP data structure */
861  	   const char*           name                /**< name of expression handler */
862  	   )
863  	{
864  	   assert(scip != NULL);
865  	   assert(scip->set != NULL);
866  	
867  	   return SCIPsetFindExprhdlr(scip->set, name);
868  	}
869  	
870  	/** returns expression handler for variable expressions (or NULL if not included) */
871  	SCIP_EXPRHDLR* SCIPgetExprhdlrVar(
872  	   SCIP*                 scip                /**< SCIP data structure */
873  	   )
874  	{
875  	   assert(scip != NULL);
876  	   assert(scip->set != NULL);
877  	
878  	   return scip->set->exprhdlrvar;
879  	}
880  	
881  	/** returns expression handler for constant value expressions (or NULL if not included) */
882  	SCIP_EXPRHDLR* SCIPgetExprhdlrValue(
883  	   SCIP*                 scip                /**< SCIP data structure */
884  	   )
885  	{
886  	   assert(scip != NULL);
887  	   assert(scip->set != NULL);
888  	
889  	   return scip->set->exprhdlrval;
890  	}
891  	
892  	/** returns expression handler for sum expressions (or NULL if not included) */
893  	SCIP_EXPRHDLR* SCIPgetExprhdlrSum(
894  	   SCIP*                 scip                /**< SCIP data structure */
895  	   )
896  	{
897  	   assert(scip != NULL);
898  	   assert(scip->set != NULL);
899  	
900  	   return scip->set->exprhdlrsum;
901  	}
902  	
903  	/** returns expression handler for product expressions (or NULL if not included) */
904  	SCIP_EXPRHDLR* SCIPgetExprhdlrProduct(
905  	   SCIP*                 scip                /**< SCIP data structure */
906  	   )
907  	{
908  	   assert(scip != NULL);
909  	   assert(scip->set != NULL);
910  	
911  	   return scip->set->exprhdlrproduct;
912  	}
913  	
914  	/** returns expression handler for power expressions (or NULL if not included) */
915  	SCIP_EXPRHDLR* SCIPgetExprhdlrPower(
916  	   SCIP*                 scip                /**< SCIP data structure */
917  	   )
918  	{
919  	   assert(scip != NULL);
920  	   assert(scip->set != NULL);
921  	
922  	   return scip->set->exprhdlrpow;
923  	}
924  	
925  	/**@} */
926  	
927  	
928  	/**@name Expression Methods */
929  	/**@{ */
930  	
931  	#ifdef NDEBUG
932  	#undef SCIPappendExprChild
933  	#undef SCIPreplaceExprChild
934  	#undef SCIPremoveExprChildren
935  	#undef SCIPduplicateExpr
936  	#undef SCIPduplicateExprShallow
937  	#undef SCIPcaptureExpr
938  	#undef SCIPreleaseExpr
939  	#undef SCIPisExprVar
940  	#undef SCIPisExprValue
941  	#undef SCIPisExprSum
942  	#undef SCIPisExprProduct
943  	#undef SCIPisExprPower
944  	#undef SCIPprintExpr
945  	#undef SCIPevalExpr
946  	#undef SCIPgetExprNewSoltag
947  	#undef SCIPevalExprGradient
948  	#undef SCIPevalExprHessianDir
949  	#undef SCIPevalExprActivity
950  	#undef SCIPcompareExpr
951  	#undef SCIPsimplifyExpr
952  	#undef SCIPcallExprCurvature
953  	#undef SCIPcallExprMonotonicity
954  	#undef SCIPcallExprEval
955  	#undef SCIPcallExprEvalFwdiff
956  	#undef SCIPcallExprInteval
957  	#undef SCIPcallExprEstimate
958  	#undef SCIPcallExprInitestimates
959  	#undef SCIPcallExprSimplify
960  	#undef SCIPcallExprReverseprop
961  	#undef SCIPcallExprGetSymData
962  	#endif
963  	
964  	/** creates and captures an expression with given expression data and children */
965  	SCIP_RETCODE SCIPcreateExpr(
966  	   SCIP*                 scip,               /**< SCIP data structure */
967  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
968  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
969  	   SCIP_EXPRDATA*        exprdata,           /**< expression data (expression assumes ownership) */
970  	   int                   nchildren,          /**< number of children */
971  	   SCIP_EXPR**           children,           /**< children (can be NULL if nchildren is 0) */
972  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
973  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
974  	   )
975  	{
976  	   assert(scip != NULL);
977  	   assert(scip->set != NULL);
978  	
979  	   SCIP_CALL( SCIPexprCreate(scip->set, scip->mem->probmem, expr, exprhdlr, exprdata, nchildren, children, ownercreate,
980  	         ownercreatedata) );
981  	
982  	   return SCIP_OKAY;
983  	}
984  	
985  	/** creates and captures an expression with given expression data and up to two children */
986  	SCIP_RETCODE SCIPcreateExpr2(
987  	   SCIP*                 scip,               /**< SCIP data structure */
988  	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
989  	   SCIP_EXPRHDLR*        exprhdlr,           /**< expression handler */
990  	   SCIP_EXPRDATA*        exprdata,           /**< expression data */
991  	   SCIP_EXPR*            child1,             /**< first child (can be NULL) */
992  	   SCIP_EXPR*            child2,             /**< second child (can be NULL) */
993  	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
994  	   void*                 ownercreatedata     /**< data to pass to ownercreate */
995  	   )
996  	{
997  	   assert(scip != NULL);
998  	   assert(expr != NULL);
999  	   assert(exprhdlr != NULL);
1000 	
1001 	   if( child1 != NULL && child2 != NULL )
1002 	   {
1003 	      SCIP_EXPR* pair[2];
1004 	      pair[0] = child1;
1005 	      pair[1] = child2;
1006 	
1007 	      SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 2, pair, ownercreate, ownercreatedata) );
1008 	   }
1009 	   else if( child2 == NULL )
1010 	   {
1011 	      SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, child1 == NULL ? 0 : 1, &child1, ownercreate,
1012 	            ownercreatedata) );
1013 	   }
1014 	   else
1015 	   {
1016 	      /* child2 != NULL, child1 == NULL */
1017 	      SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child2, ownercreate, ownercreatedata) );
1018 	   }
1019 	
1020 	   return SCIP_OKAY;
1021 	}
1022 	
1023 	/** creates and captures an expression representing a quadratic function */
1024 	SCIP_RETCODE SCIPcreateExprQuadratic(
1025 	   SCIP*                 scip,               /**< SCIP data structure */
1026 	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
1027 	   int                   nlinvars,           /**< number of linear terms */
1028 	   SCIP_VAR**            linvars,            /**< array with variables in linear part */
1029 	   SCIP_Real*            lincoefs,           /**< array with coefficients of variables in linear part */
1030 	   int                   nquadterms,         /**< number of quadratic terms */
1031 	   SCIP_VAR**            quadvars1,          /**< array with first variables in quadratic terms */
1032 	   SCIP_VAR**            quadvars2,          /**< array with second variables in quadratic terms */
1033 	   SCIP_Real*            quadcoefs,          /**< array with coefficients of quadratic terms */
1034 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1035 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1036 	   )
1037 	{
1038 	   SCIP_EXPR** children;
1039 	   SCIP_Real* coefs;
1040 	   int i;
1041 	
1042 	   assert(scip != NULL);
1043 	   assert(expr != NULL);
1044 	   assert(nlinvars == 0 || (linvars != NULL && lincoefs != NULL));
1045 	   assert(nquadterms == 0 || (quadvars1 != NULL && quadvars2 != NULL && quadcoefs != NULL));
1046 	
1047 	   /* allocate memory */
1048 	   SCIP_CALL( SCIPallocBufferArray(scip, &children, nquadterms + nlinvars) );
1049 	   SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nquadterms + nlinvars) );
1050 	
1051 	   /* create children for quadratic terms */
1052 	   for( i = 0; i < nquadterms; ++i )
1053 	   {
1054 	      assert(quadvars1 != NULL && quadvars1[i] != NULL);
1055 	      assert(quadvars2 != NULL && quadvars2[i] != NULL);
1056 	
1057 	      /* quadratic term */
1058 	      if( quadvars1[i] == quadvars2[i] )
1059 	      {
1060 	         SCIP_EXPR* xexpr;
1061 	
1062 	         /* create variable expression; intentionally not using createExprVar here,
1063 	          * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1064 	          */
1065 	         SCIP_CALL( SCIPcreateExprVar(scip, &xexpr, quadvars1[i], ownercreate, ownercreatedata) );
1066 	
1067 	         /* create pow expression */
1068 	         SCIP_CALL( SCIPcreateExprPow(scip, &children[i], xexpr, 2.0, ownercreate, ownercreatedata) );
1069 	
1070 	         /* release variable expression; note that the variable expression is still captured by children[i] */
1071 	         SCIP_CALL( SCIPreleaseExpr(scip, &xexpr) );
1072 	      }
1073 	      else /* bilinear term */
1074 	      {
1075 	         SCIP_EXPR* exprs[2];
1076 	
1077 	         /* create variable expressions; intentionally not using createExprVar here,
1078 	          * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1079 	          */
1080 	         SCIP_CALL( SCIPcreateExprVar(scip, &exprs[0], quadvars1[i], ownercreate, ownercreatedata) );
1081 	         SCIP_CALL( SCIPcreateExprVar(scip, &exprs[1], quadvars2[i], ownercreate, ownercreatedata) );
1082 	
1083 	         /* create product expression */
1084 	         SCIP_CALL( SCIPcreateExprProduct(scip, &children[i], 2, exprs, 1.0, ownercreate, ownercreatedata) );
1085 	
1086 	         /* release variable expressions; note that the variable expressions are still captured by children[i] */
1087 	         SCIP_CALL( SCIPreleaseExpr(scip, &exprs[1]) );
1088 	         SCIP_CALL( SCIPreleaseExpr(scip, &exprs[0]) );
1089 	      }
1090 	
1091 	      /* store coefficient */
1092 	      coefs[i] = quadcoefs[i];
1093 	   }
1094 	
1095 	   /* create children for linear terms */
1096 	   for( i = 0; i < nlinvars; ++i )
1097 	   {
1098 	      assert(linvars != NULL && linvars[i] != NULL);
1099 	
1100 	      /* create variable expression; intentionally not using createExprVar here,
1101 	       * since expression created here is not part of a constraint (they will be copied when a constraint is created);
1102 	       * release variable expression after the sum expression has been created
1103 	       */
1104 	      SCIP_CALL( SCIPcreateExprVar(scip, &children[nquadterms + i], linvars[i], ownercreate, ownercreatedata) );
1105 	
1106 	      /* store coefficient */
1107 	      coefs[nquadterms + i] = lincoefs[i];
1108 	   }
1109 	
1110 	   /* create sum expression */
1111 	   SCIP_CALL( SCIPcreateExprSum(scip, expr, nquadterms + nlinvars, children, coefs, 0.0, ownercreate, ownercreatedata) );
1112 	
1113 	   /* release children */
1114 	   for( i = 0; i < nquadterms + nlinvars; ++i )
1115 	   {
1116 	      assert(children[i] != NULL);
1117 	      SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1118 	   }
1119 	
1120 	   /* free memory */
1121 	   SCIPfreeBufferArray(scip, &coefs);
1122 	   SCIPfreeBufferArray(scip, &children);
1123 	
1124 	   return SCIP_OKAY;
1125 	}
1126 	
1127 	/** creates and captures an expression representing a monomial
1128 	 *
1129 	 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents.
1130 	 * So this function actually creates an expression for a signomial that has exactly one term.
1131 	 */
1132 	SCIP_RETCODE SCIPcreateExprMonomial(
1133 	   SCIP*                 scip,               /**< SCIP data structure */
1134 	   SCIP_EXPR**           expr,               /**< pointer where to store expression */
1135 	   int                   nfactors,           /**< number of factors in monomial */
1136 	   SCIP_VAR**            vars,               /**< variables in the monomial */
1137 	   SCIP_Real*            exponents,          /**< exponent in each factor, or NULL if all 1.0 */
1138 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1139 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1140 	   )
1141 	{
1142 	   assert(scip != NULL);
1143 	   assert(expr != NULL);
1144 	   assert(nfactors >= 0);
1145 	
1146 	   /* return 1 as constant expression if there are no factors */
1147 	   if( nfactors == 0 )
1148 	   {
1149 	      SCIP_CALL( SCIPcreateExprValue(scip, expr, 1.0, ownercreate, ownercreatedata) );
1150 	   }
1151 	   else if( nfactors == 1 )
1152 	   {
1153 	      /* only one factor and exponent is 1 => return factors[0] */
1154 	      if( exponents == NULL || exponents[0] == 1.0 )
1155 	      {
1156 	         /* intentionally not using createExprVar here, since expression created here is not part of
1157 	          * a constraint (they will be copied when a constraint is created)
1158 	          */
1159 	         SCIP_CALL( SCIPcreateExprVar(scip, expr, vars[0], ownercreate, ownercreatedata) );
1160 	      }
1161 	      else
1162 	      {
1163 	         SCIP_EXPR* varexpr;
1164 	
1165 	         /* create variable and power expression; intentionally not using createExprVar here,
1166 	          * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1167 	          */
1168 	         SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[0], ownercreate, ownercreatedata) );
1169 	         SCIP_CALL( SCIPcreateExprPow(scip, expr, varexpr, exponents[0], ownercreate, ownercreatedata) );
1170 	         SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
1171 	      }
1172 	   }
1173 	   else
1174 	   {
1175 	      SCIP_EXPR** children;
1176 	      int i;
1177 	
1178 	      /* allocate memory to store the children */
1179 	      SCIP_CALL( SCIPallocBufferArray(scip, &children, nfactors) );
1180 	
1181 	      /* create children */
1182 	      for( i = 0; i < nfactors; ++i )
1183 	      {
1184 	         /* check whether to create a power expression or not, i.e., exponent == 1 */
1185 	         if( exponents == NULL || exponents[i] == 1.0 )
1186 	         {
1187 	            SCIP_CALL( SCIPcreateExprVar(scip, &children[i], vars[i], ownercreate, ownercreatedata) );
1188 	         }
1189 	         else
1190 	         {
1191 	            SCIP_EXPR* varexpr;
1192 	
1193 	            /* create variable and pow expression */
1194 	            SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[i], ownercreate, ownercreatedata) );
1195 	            SCIP_CALL( SCIPcreateExprPow(scip, &children[i], varexpr, exponents[i], ownercreate, ownercreatedata) );
1196 	            SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
1197 	         }
1198 	      }
1199 	
1200 	      /* create product expression */
1201 	      SCIP_CALL( SCIPcreateExprProduct(scip, expr, nfactors, children, 1.0, ownercreate, ownercreatedata) );
1202 	
1203 	      /* release children */
1204 	      for( i = 0; i < nfactors; ++i )
1205 	      {
1206 	         assert(children[i] != NULL);
1207 	         SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1208 	      }
1209 	
1210 	      /* free memory */
1211 	      SCIPfreeBufferArray(scip, &children);
1212 	   }
1213 	
1214 	   return SCIP_OKAY;
1215 	}
1216 	
1217 	/** appends child to the children list of expr
1218 	 *
1219 	 * @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.
1220 	 */
1221 	SCIP_RETCODE SCIPappendExprChild(
1222 	   SCIP*                 scip,               /**< SCIP data structure */
1223 	   SCIP_EXPR*            expr,               /**< expression */
1224 	   SCIP_EXPR*            child               /**< expression to be appended */
1225 	   )
1226 	{
1227 	   assert(scip != NULL);
1228 	   assert(scip->mem != NULL);
1229 	
1230 	   SCIP_CALL( SCIPexprAppendChild(scip->set, scip->mem->probmem, expr, child) );
1231 	
1232 	   return SCIP_OKAY;
1233 	}
1234 	
1235 	/** overwrites/replaces a child of an expressions
1236 	 *
1237 	 * The old child is released and the newchild is captured, unless they are the same (=same pointer).
1238 	 */
1239 	SCIP_RETCODE SCIPreplaceExprChild(
1240 	   SCIP*                 scip,               /**< SCIP data structure */
1241 	   SCIP_EXPR*            expr,               /**< expression which is going to replace a child */
1242 	   int                   childidx,           /**< index of child being replaced */
1243 	   SCIP_EXPR*            newchild            /**< the new child */
1244 	   )
1245 	{
1246 	   assert(scip != NULL);
1247 	   assert(scip->mem != NULL);
1248 	
1249 	   SCIP_CALL( SCIPexprReplaceChild(scip->set, scip->stat, scip->mem->probmem, expr, childidx, newchild) );
1250 	
1251 	   return SCIP_OKAY;
1252 	}
1253 	
1254 	/** remove all children of expr
1255 	 *
1256 	 * @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.
1257 	 */
1258 	SCIP_RETCODE SCIPremoveExprChildren(
1259 	   SCIP*                 scip,               /**< SCIP data structure */
1260 	   SCIP_EXPR*            expr                /**< expression */
1261 	   )
1262 	{
1263 	   assert(scip != NULL);
1264 	   assert(scip->mem != NULL);
1265 	
1266 	   SCIP_CALL( SCIPexprRemoveChildren(scip->set, scip->stat, scip->mem->probmem, expr) );
1267 	
1268 	   return SCIP_OKAY;
1269 	}
1270 	
1271 	/** duplicates the given expression and its children */
1272 	SCIP_RETCODE SCIPduplicateExpr(
1273 	   SCIP*                 scip,               /**< SCIP data structure */
1274 	   SCIP_EXPR*            expr,               /**< original expression */
1275 	   SCIP_EXPR**           copyexpr,           /**< buffer to store duplicate of expr */
1276 	   SCIP_DECL_EXPR_MAPEXPR((*mapexpr)),       /**< expression mapping function, or NULL for creating new expressions */
1277 	   void*                 mapexprdata,        /**< data of expression mapping function */
1278 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1279 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1280 	   )
1281 	{
1282 	   assert(scip != NULL);
1283 	   assert(scip->mem != NULL);
1284 	
1285 	   SCIP_CALL( SCIPexprCopy(scip->set, scip->stat, scip->mem->probmem, scip->set, scip->stat, scip->mem->probmem,
1286 	         expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) );
1287 	
1288 	   return SCIP_OKAY;
1289 	}
1290 	
1291 	/** duplicates the given expression, but reuses its children */
1292 	SCIP_RETCODE SCIPduplicateExprShallow(
1293 	   SCIP*                 scip,               /**< SCIP data structure */
1294 	   SCIP_EXPR*            expr,               /**< original expression */
1295 	   SCIP_EXPR**           copyexpr,           /**< buffer to store (shallow) duplicate of expr */
1296 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1297 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1298 	   )
1299 	{
1300 	   assert(scip != NULL);
1301 	   assert(scip->mem != NULL);
1302 	
1303 	   SCIP_CALL( SCIPexprDuplicateShallow(scip->set, scip->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata) );
1304 	
1305 	   return SCIP_OKAY;
1306 	}
1307 	
1308 	/** copies an expression including children to use in a (possibly different) SCIP instance */
1309 	SCIP_RETCODE SCIPcopyExpr(
1310 	   SCIP*                 sourcescip,         /**< source SCIP data structure */
1311 	   SCIP*                 targetscip,         /**< target SCIP data structure */
1312 	   SCIP_EXPR*            expr,               /**< original expression */
1313 	   SCIP_EXPR**           copyexpr,           /**< buffer to store duplicate of expr */
1314 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1315 	   void*                 ownercreatedata,    /**< data to pass to ownercreate */
1316 	   SCIP_HASHMAP*         varmap,             /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding
1317 	                                              *   variables of the target SCIP, or NULL */
1318 	   SCIP_HASHMAP*         consmap,            /**< a hashmap to store the mapping of source constraints to the corresponding
1319 	                                              *   target constraints, or NULL */
1320 	   SCIP_Bool             global,             /**< create a global or a local copy? */
1321 	   SCIP_Bool*            valid               /**< pointer to store whether all checked or enforced constraints were validly copied */
1322 	   )
1323 	{
1324 	#ifndef _MSC_VER
1325 	   COPY_MAPEXPR_DATA copydata = {
1326 	      .varmap = varmap,
1327 	      .consmap = consmap,
1328 	      .global = global,
1329 	      .valid = TRUE
1330 	   };
1331 	#else  /* MS compiler doesn't have proper C99 support... */
1332 	   COPY_MAPEXPR_DATA copydata;
1333 	   copydata.varmap = varmap;
1334 	   copydata.consmap = consmap;
1335 	   copydata.global = global;
1336 	   copydata.valid = TRUE;
1337 	#endif
1338 	
1339 	   assert(sourcescip != NULL);
1340 	   assert(sourcescip->mem != NULL);
1341 	   assert(targetscip != NULL);
1342 	   assert(targetscip->mem != NULL);
1343 	
1344 	   SCIP_CALL( SCIPexprCopy(sourcescip->set, sourcescip->stat, sourcescip->mem->probmem,
1345 	      targetscip->set, targetscip->stat, targetscip->mem->probmem,
1346 	      expr, copyexpr, copyVarExpr, &copydata, ownercreate, ownercreatedata) );
1347 	
1348 	   *valid = copydata.valid;
1349 	
1350 	   return SCIP_OKAY;
1351 	}
1352 	
1353 	/** creates an expression from a string
1354 	 *
1355 	 * We specify the grammar that defines the syntax of an expression.
1356 	 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power,
1357 	 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`.
1358 	 *
1359 	 * The actual definition:
1360 	 * <pre>
1361 	 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
1362 	 * Term       -> Factor { ("*" | "/" ) Factor }
1363 	 * Factor     -> Base [ "^" "number" | "^(" "number" ")" ]
1364 	 * Base       -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
1365 	 * </pre>
1366 	 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`.
1367 	 *
1368 	 * Note that `Op` and `OpExpression` are undefined.
1369 	 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method).
1370 	 */
1371 	SCIP_RETCODE SCIPparseExpr(
1372 	   SCIP*                 scip,               /**< SCIP data structure */
1373 	   SCIP_EXPR**           expr,               /**< pointer to store the expr parsed */
1374 	   const char*           exprstr,            /**< string with the expr to parse */
1375 	   const char**          finalpos,           /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */
1376 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1377 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1378 	   )
1379 	{
1380 	   const char* finalpos_;
1381 	   SCIP_RETCODE retcode;
1382 	   SCIP_HASHMAP* vartoexprvarmap;
1383 	
1384 	   assert(scip != NULL);
1385 	
1386 	   SCIP_CALL( SCIPhashmapCreate(&vartoexprvarmap, SCIPblkmem(scip), 5 * SCIPgetNVars(scip)) );
1387 	
1388 	   /* if parseExpr fails, we still want to free hashmap */
1389 	   retcode = parseExpr(scip, vartoexprvarmap, exprstr, &finalpos_, expr, ownercreate, ownercreatedata);
1390 	
1391 	   SCIPhashmapFree(&vartoexprvarmap);
1392 	
1393 	   if( finalpos != NULL )
1394 	      *finalpos = finalpos_;
1395 	
1396 	   return retcode;
1397 	}
1398 	
1399 	/** captures an expression (increments usage count) */
1400 	void SCIPcaptureExpr(
1401 	   SCIP_EXPR*            expr                /**< expression to be captured */
1402 	   )
1403 	{
1404 	   SCIPexprCapture(expr);
1405 	}
1406 	
1407 	/** releases an expression (decrements usage count and possibly frees expression) */
1408 	SCIP_RETCODE SCIPreleaseExpr(
1409 	   SCIP*                 scip,               /**< SCIP data structure */
1410 	   SCIP_EXPR**           expr                /**< pointer to expression to be released */
1411 	   )
1412 	{
1413 	   assert(scip != NULL);
1414 	   assert(scip->mem != NULL);
1415 	
1416 	   SCIP_CALL( SCIPexprRelease(scip->set, scip->stat, scip->mem->probmem, expr) );
1417 	
1418 	   return SCIP_OKAY;
1419 	}
1420 	
1421 	/** returns whether an expression is a variable expression */
1422 	SCIP_Bool SCIPisExprVar(
1423 	   SCIP*                 scip,               /**< SCIP data structure */
1424 	   SCIP_EXPR*            expr                /**< expression */
1425 	   )
1426 	{
1427 	   assert(scip != NULL);
1428 	
1429 	   return SCIPexprIsVar(scip->set, expr);
1430 	}
1431 	
1432 	/** returns whether an expression is a value expression */
1433 	SCIP_Bool SCIPisExprValue(
1434 	   SCIP*                 scip,               /**< SCIP data structure */
1435 	   SCIP_EXPR*            expr                /**< expression */
1436 	   )
1437 	{
1438 	   assert(scip != NULL);
1439 	
1440 	   return SCIPexprIsValue(scip->set, expr);
1441 	}
1442 	
1443 	/** returns whether an expression is a sum expression */
1444 	SCIP_Bool SCIPisExprSum(
1445 	   SCIP*                 scip,               /**< SCIP data structure */
1446 	   SCIP_EXPR*            expr                /**< expression */
1447 	   )
1448 	{
1449 	   assert(scip != NULL);
1450 	
1451 	   return SCIPexprIsSum(scip->set, expr);
1452 	}
1453 	
1454 	/** returns whether an expression is a product expression */
1455 	SCIP_Bool SCIPisExprProduct(
1456 	   SCIP*                 scip,               /**< SCIP data structure */
1457 	   SCIP_EXPR*            expr                /**< expression */
1458 	   )
1459 	{
1460 	   assert(scip != NULL);
1461 	
1462 	   return SCIPexprIsProduct(scip->set, expr);
1463 	}
1464 	
1465 	/** returns whether an expression is a power expression */
1466 	SCIP_Bool SCIPisExprPower(
1467 	   SCIP*                 scip,               /**< SCIP data structure */
1468 	   SCIP_EXPR*            expr                /**< expression */
1469 	   )
1470 	{
1471 	   assert(scip != NULL);
1472 	
1473 	   return SCIPexprIsPower(scip->set, expr);
1474 	}
1475 	
1476 	/** print an expression as info-message */
1477 	SCIP_RETCODE SCIPprintExpr(
1478 	   SCIP*                 scip,               /**< SCIP data structure */
1479 	   SCIP_EXPR*            expr,               /**< expression to be printed */
1480 	   FILE*                 file                /**< file to print to, or NULL for stdout */
1481 	   )
1482 	{
1483 	   assert(scip != NULL);
1484 	   assert(scip->mem != NULL);
1485 	
1486 	   SCIP_CALL( SCIPexprPrint(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1487 	
1488 	   return SCIP_OKAY;
1489 	}
1490 	
1491 	/** initializes printing of expressions in dot format to a give FILE* pointer */
1492 	SCIP_RETCODE SCIPprintExprDotInit(
1493 	   SCIP*                 scip,               /**< SCIP data structure */
1494 	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
1495 	   FILE*                 file,               /**< file to print to, or NULL for stdout */
1496 	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
1497 	   )
1498 	{
1499 	   assert(scip != NULL);
1500 	   assert(scip->mem != NULL);
1501 	
1502 	   SCIP_CALL( SCIPexprPrintDotInit(scip->set, scip->stat, scip->mem->probmem, printdata, file, whattoprint) );
1503 	
1504 	   return SCIP_OKAY;
1505 	}
1506 	
1507 	/** initializes printing of expressions in dot format to a file with given filename */
1508 	SCIP_RETCODE SCIPprintExprDotInit2(
1509 	   SCIP*                 scip,               /**< SCIP data structure */
1510 	   SCIP_EXPRPRINTDATA**  printdata,          /**< buffer to store dot printing data */
1511 	   const char*           filename,           /**< name of file to print to */
1512 	   SCIP_EXPRPRINT_WHAT   whattoprint         /**< info on what to print for each expression */
1513 	   )
1514 	{
1515 	   assert(scip != NULL);
1516 	   assert(scip->mem != NULL);
1517 	
1518 	   SCIP_CALL( SCIPexprPrintDotInit2(scip->set, scip->stat, scip->mem->probmem, printdata, filename, whattoprint) );
1519 	
1520 	   return SCIP_OKAY;
1521 	}
1522 	
1523 	/** main part of printing an expression in dot format */
1524 	SCIP_RETCODE SCIPprintExprDot(
1525 	   SCIP*                 scip,               /**< SCIP data structure */
1526 	   SCIP_EXPRPRINTDATA*   printdata,          /**< data as initialized by \ref SCIPprintExprDotInit() */
1527 	   SCIP_EXPR*            expr                /**< expression to be printed */
1528 	   )
1529 	{
1530 	   assert(scip != NULL);
1531 	
1532 	   SCIP_CALL( SCIPexprPrintDot(scip->set, scip->messagehdlr, printdata, expr) );
1533 	
1534 	   return SCIP_OKAY;
1535 	}
1536 	
1537 	/** finishes printing of expressions in dot format */
1538 	SCIP_RETCODE SCIPprintExprDotFinal(
1539 	   SCIP*                 scip,               /**< SCIP data structure */
1540 	   SCIP_EXPRPRINTDATA**  printdata           /**< buffer where dot printing data has been stored */
1541 	   )
1542 	{
1543 	   assert(scip != NULL);
1544 	   assert(scip->mem != NULL);
1545 	
1546 	   SCIP_CALL( SCIPexprPrintDotFinal(scip->set, scip->stat, scip->mem->probmem, printdata) );
1547 	
1548 	   return SCIP_OKAY;
1549 	}
1550 	
1551 	/** shows a single expression by use of dot and gv
1552 	 *
1553 	 * This function is meant for debugging purposes.
1554 	 * It's signature is kept as simple as possible to make it
1555 	 * easily callable from gdb, for example.
1556 	 *
1557 	 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file,
1558 	 * then calls ghostview (gv) to show the file. SCIP will hold until ghostscript is closed.
1559 	 */
1560 	SCIP_RETCODE SCIPshowExpr(
1561 	   SCIP*                 scip,               /**< SCIP data structure */
1562 	   SCIP_EXPR*            expr                /**< expression to be printed */
1563 	   )
1564 	{
1565 	   /* this function is for developers, so don't bother with C variants that don't have popen() */
1566 	#if _POSIX_C_SOURCE < 2
1567 	   SCIPerrorMessage("No POSIX version 2. Try http://distrowatch.com/.");
1568 	   return SCIP_ERROR;
1569 	#else
1570 	   SCIP_EXPRPRINTDATA* dotdata;
1571 	   FILE* f;
1572 	   SCIP_RETCODE retcode = SCIP_OKAY;
1573 	
1574 	   assert(scip != NULL);
1575 	   assert(expr != NULL);
1576 	
1577 	   /* call dot to generate postscript output and show it via ghostview */
1578 	   f = popen("dot -Tps | gv --media=a3 -", "w");
1579 	   if( f == NULL )
1580 	   {
1581 	      SCIPerrorMessage("Calling popen() failed");
1582 	      return SCIP_FILECREATEERROR;
1583 	   }
1584 	
1585 	   /* print all of the expression into the pipe */
1586 	   SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotInit(scip, &dotdata, f, SCIP_EXPRPRINT_ALL), TERMINATE );
1587 	   SCIP_CALL_TERMINATE( retcode, SCIPprintExprDot(scip, dotdata, expr), TERMINATE );
1588 	   SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotFinal(scip, &dotdata), TERMINATE );
1589 	
1590 	 TERMINATE:
1591 	   /* close the pipe */
1592 	   (void) pclose(f);
1593 	
1594 	   return retcode;
1595 	#endif
1596 	}
1597 	
1598 	/** prints structure of an expression a la Maple's dismantle */
1599 	SCIP_RETCODE SCIPdismantleExpr(
1600 	   SCIP*                 scip,               /**< SCIP data structure */
1601 	   FILE*                 file,               /**< file to print to, or NULL for stdout */
1602 	   SCIP_EXPR*            expr                /**< expression to dismantle */
1603 	   )
1604 	{
1605 	   assert(scip != NULL);
1606 	   assert(scip->mem != NULL);
1607 	
1608 	   SCIP_CALL( SCIPexprDismantle(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1609 	
1610 	   return SCIP_OKAY;
1611 	}
1612 	
1613 	/** evaluate an expression in a point
1614 	 *
1615 	 * Iterates over expressions to also evaluate children, if necessary.
1616 	 * Value can be received via SCIPexprGetEvalValue().
1617 	 * If an evaluation error (division by zero, ...) occurs, this value will
1618 	 * be set to SCIP_INVALID.
1619 	 *
1620 	 * If a nonzero \p soltag is passed, then only (sub)expressions are
1621 	 * reevaluated that have a different solution tag. If a soltag of 0
1622 	 * is passed, then subexpressions are always reevaluated.
1623 	 * The tag is stored together with the value and can be received via
1624 	 * SCIPexprGetEvalTag().
1625 	 */
1626 	SCIP_RETCODE SCIPevalExpr(
1627 	   SCIP*                 scip,               /**< SCIP data structure */
1628 	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
1629 	   SCIP_SOL*             sol,                /**< solution to be evaluated */
1630 	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
1631 	   )
1632 	{
1633 	   assert(scip != NULL);
1634 	   assert(scip->mem != NULL);
1635 	
1636 	   SCIP_CALL( SCIPexprEval(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1637 	
1638 	   return SCIP_OKAY;
1639 	}
1640 	
1641 	/** returns a previously unused solution tag for expression evaluation */
1642 	SCIP_Longint SCIPgetExprNewSoltag(
1643 	   SCIP*                 scip                /**< SCIP data structure */
1644 	   )
1645 	{
1646 	   assert(scip != NULL);
1647 	
1648 	   return ++(scip->stat->exprlastsoltag);
1649 	}
1650 	
1651 	/** evaluates gradient of an expression for a given point
1652 	 *
1653 	 * Initiates an expression walk to also evaluate children, if necessary.
1654 	 * Value can be received via SCIPgetExprPartialDiffNonlinear().
1655 	 * If an error (division by zero, ...) occurs, this value will
1656 	 * be set to SCIP_INVALID.
1657 	 */
1658 	SCIP_RETCODE SCIPevalExprGradient(
1659 	   SCIP*                 scip,               /**< SCIP data structure */
1660 	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
1661 	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
1662 	   SCIP_Longint          soltag              /**< tag that uniquely identifies the solution (with its values), or 0. */
1663 	   )
1664 	{
1665 	   assert(scip != NULL);
1666 	   assert(scip->mem != NULL);
1667 	
1668 	   SCIP_CALL( SCIPexprEvalGradient(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1669 	
1670 	   return SCIP_OKAY;
1671 	}
1672 	
1673 	/** evaluates Hessian-vector product of an expression for a given point and direction
1674 	 *
1675 	 * Evaluates children, if necessary.
1676 	 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear().
1677 	 * If an error (division by zero, ...) occurs, this value will
1678 	 * be set to SCIP_INVALID.
1679 	 */
1680 	SCIP_RETCODE SCIPevalExprHessianDir(
1681 	   SCIP*                 scip,               /**< SCIP data structure */
1682 	   SCIP_EXPR*            expr,               /**< expression to be differentiated */
1683 	   SCIP_SOL*             sol,                /**< solution to be evaluated (NULL for the current LP solution) */
1684 	   SCIP_Longint          soltag,             /**< tag that uniquely identifies the solution (with its values), or 0. */
1685 	   SCIP_SOL*             direction           /**< direction */
1686 	   )
1687 	{
1688 	   assert(scip != NULL);
1689 	   assert(scip->mem != NULL);
1690 	
1691 	   SCIP_CALL( SCIPexprEvalHessianDir(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag, direction) );
1692 	
1693 	   return SCIP_OKAY;
1694 	}
1695 	
1696 	/** possibly reevaluates and then returns the activity of the expression
1697 	 *
1698 	 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation).
1699 	 *
1700 	 * The owner of the expression may overwrite the methods used to evaluate the activity,
1701 	 * including whether the local or global domain of variables is used.
1702 	 * By default (no owner, or owner doesn't overwrite activity evaluation),
1703 	 * the local domain of variables is used.
1704 	 *
1705 	 * @note If expression is set to be integral, then activities are tightened to integral values.
1706 	 *   Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
1707 	 */
1708 	SCIP_RETCODE SCIPevalExprActivity(
1709 	   SCIP*                 scip,               /**< SCIP data structure */
1710 	   SCIP_EXPR*            expr                /**< expression */
1711 	   )
1712 	{
1713 	   assert(scip != NULL);
1714 	   assert(scip->mem != NULL);
1715 	
1716 	   SCIP_CALL( SCIPexprEvalActivity(scip->set, scip->stat, scip->mem->probmem, expr) );
1717 	
1718 	   return SCIP_OKAY;
1719 	}
1720 	
1721 	/** compare expressions
1722 	 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
1723 	 * @note The given expressions are assumed to be simplified.
1724 	 */
1725 	int SCIPcompareExpr(
1726 	   SCIP*                 scip,               /**< SCIP data structure */
1727 	   SCIP_EXPR*            expr1,              /**< first expression */
1728 	   SCIP_EXPR*            expr2               /**< second expression */
1729 	   )
1730 	{
1731 	   assert(scip != NULL);
1732 	
1733 	   return SCIPexprCompare(scip->set, expr1, expr2);
1734 	}
1735 	
1736 	/** compute the hash value of an expression */
1737 	SCIP_RETCODE SCIPhashExpr(
1738 	   SCIP*                 scip,               /**< SCIP data structure */
1739 	   SCIP_EXPR*            expr,               /**< expression */
1740 	   unsigned int*         hashval             /**< pointer to store the hash value */
1741 	   )
1742 	{
1743 	   SCIP_EXPRITER* it;
1744 	
1745 	   assert(scip != NULL);
1746 	   assert(scip->mem != NULL);
1747 	   assert(expr != NULL);
1748 	   assert(hashval != NULL);
1749 	
1750 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1751 	   SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
1752 	   SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR);
1753 	
1754 	   SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, expr, it, NULL) );
1755 	
1756 	   *hashval = SCIPexpriterGetExprUserData(it, expr).uintval;
1757 	
1758 	   SCIPexpriterFree(&it);
1759 	
1760 	   return SCIP_OKAY;
1761 	}
1762 	
1763 	/** simplifies an expression (duplication of long doxygen comment omitted here) */
1764 	SCIP_RETCODE SCIPsimplifyExpr(
1765 	   SCIP*                 scip,               /**< SCIP data structure */
1766 	   SCIP_EXPR*            rootexpr,           /**< expression to be simplified */
1767 	   SCIP_EXPR**           simplified,         /**< buffer to store simplified expression */
1768 	   SCIP_Bool*            changed,            /**< buffer to store if rootexpr actually changed */
1769 	   SCIP_Bool*            infeasible,         /**< buffer to store whether infeasibility has been detected */
1770 	   SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1771 	   void*                 ownercreatedata     /**< data to pass to ownercreate */
1772 	   )
1773 	{
1774 	   assert(scip != NULL);
1775 	   assert(scip->mem != NULL);
1776 	
1777 	   SCIP_CALL( SCIPexprSimplify(scip->set, scip->stat, scip->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) );
1778 	
1779 	   return SCIP_OKAY;
1780 	}
1781 	
1782 	/** retrieves symmetry information from an expression */
1783 	SCIP_RETCODE SCIPgetSymDataExpr(
1784 	   SCIP*                 scip,               /**< SCIP data structure */
1785 	   SCIP_EXPR*            expr,               /**< expression from which information needs to be retrieved */
1786 	   SYM_EXPRDATA**        symdata             /**< buffer to store symmetry data */
1787 	   )
1788 	{
1789 	   assert(scip != NULL);
1790 	   assert(expr != NULL);
1791 	   assert(symdata != NULL);
1792 	
1793 	   SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) );
1794 	
1795 	   return SCIP_OKAY;
1796 	}
1797 	
1798 	/** replaces common sub-expressions in a given expression graph by using a hash key for each expression
1799 	 *
1800 	 *  The algorithm consists of two steps:
1801 	 *
1802 	 *  1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash
1803 	 *
1804 	 *  2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a
1805 	 *     structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the
1806 	 *     hash table, otherwise we add it to the hash table
1807 	 *
1808 	 *  @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions
1809 	 *  (with the same hash) are structurally the same we use the function SCIPexprCompare().
1810 	 */
1811 	SCIP_RETCODE SCIPreplaceCommonSubexpressions(
1812 	   SCIP*                 scip,               /**< SCIP data structure */
1813 	   SCIP_EXPR**           exprs,              /**< expressions (possibly replaced by equivalent on output) */
1814 	   int                   nexprs,             /**< total number of expressions */
1815 	   SCIP_Bool*            replacedroot        /**< buffer to store whether any root expression (expression in exprs) was replaced */
1816 	   )
1817 	{
1818 	   COMMONSUBEXPR_HASH_DATA hashdata;
1819 	   SCIP_EXPRITER* hashiterator;
1820 	   SCIP_EXPRITER* repliterator;
1821 	   SCIP_MULTIHASH* key2expr;
1822 	   int i;
1823 	   int nvisitedexprs = 0;
1824 	
1825 	   assert(scip != NULL);
1826 	   assert(scip->mem != NULL);
1827 	   assert(exprs != NULL);
1828 	   assert(nexprs >= 0);
1829 	   assert(replacedroot != NULL);
1830 	
1831 	   *replacedroot = FALSE;
1832 	
1833 	   if( nexprs == 0 )
1834 	      return SCIP_OKAY;
1835 	
1836 	   SCIP_CALL( SCIPcreateExpriter(scip, &hashiterator) );
1837 	   SCIP_CALL( SCIPexpriterInit(hashiterator, NULL, SCIP_EXPRITER_DFS, FALSE) );
1838 	   SCIPexpriterSetStagesDFS(hashiterator, SCIP_EXPRITER_LEAVEEXPR);
1839 	
1840 	   /* compute all hashes for each sub-expression */
1841 	   for( i = 0; i < nexprs; ++i )
1842 	   {
1843 	      assert(exprs[i] != NULL);
1844 	      SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, exprs[i], hashiterator, &nvisitedexprs) );
1845 	   }
1846 	
1847 	   /* replace equivalent sub-expressions */
1848 	   hashdata.hashiterator = hashiterator;
1849 	   hashdata.set = scip->set;
1850 	   SCIP_CALL( SCIPmultihashCreate(&key2expr, scip->mem->probmem, nvisitedexprs,
1851 	         hashCommonSubexprGetKey, hashCommonSubexprEq, hashCommonSubexprKeyval, (void*)&hashdata) );
1852 	
1853 	   SCIP_CALL( SCIPcreateExpriter(scip, &repliterator) );
1854 	
1855 	   for( i = 0; i < nexprs; ++i )
1856 	   {
1857 	      SCIP_EXPR* newroot;
1858 	      SCIP_EXPR* newchild;
1859 	      SCIP_EXPR* child;
1860 	
1861 	      /* check the root for equivalence separately first */
1862 	      SCIP_CALL( findEqualExpr(scip->set, exprs[i], key2expr, &newroot) );
1863 	
1864 	      if( newroot != NULL )
1865 	      {
1866 	         assert(newroot != exprs[i]);
1867 	         assert(SCIPexprCompare(scip->set, exprs[i], newroot) == 0);
1868 	
1869 	         SCIPdebugMsg(scip, "replacing common root expression of %dth expr: %p -> %p\n", i, (void*)exprs[i], (void*)newroot);
1870 	
1871 	         SCIP_CALL( SCIPreleaseExpr(scip, &exprs[i]) );
1872 	
1873 	         exprs[i] = newroot;
1874 	         SCIPexprCapture(newroot);
1875 	
1876 	         *replacedroot = TRUE;
1877 	
1878 	         continue;
1879 	      }
1880 	
1881 	      /* replace equivalent sub-expressions in the tree */
1882 	      SCIP_CALL( SCIPexpriterInit(repliterator, exprs[i], SCIP_EXPRITER_DFS, FALSE) );
1883 	      SCIPexpriterSetStagesDFS(repliterator, SCIP_EXPRITER_VISITINGCHILD);
1884 	
1885 	      while( !SCIPexpriterIsEnd(repliterator) )
1886 	      {
1887 	         child = SCIPexpriterGetChildExprDFS(repliterator);
1888 	         assert(child != NULL);
1889 	
1890 	         /* try to find an equivalent expression */
1891 	         SCIP_CALL( findEqualExpr(scip->set, child, key2expr, &newchild) );
1892 	
1893 	         /* replace child with newchild */
1894 	         if( newchild != NULL )
1895 	         {
1896 	            assert(child != newchild);
1897 	            assert(SCIPexprCompare(scip->set, child, newchild) == 0);
1898 	
1899 	            SCIPdebugMsg(scip, "replacing common child expression %p -> %p\n", (void*)child, (void*)newchild);
1900 	
1901 	            SCIP_CALL( SCIPreplaceExprChild(scip, SCIPexpriterGetCurrent(repliterator), SCIPexpriterGetChildIdxDFS(repliterator), newchild) );
1902 	
1903 	            (void) SCIPexpriterSkipDFS(repliterator);
1904 	         }
1905 	         else
1906 	         {
1907 	            (void) SCIPexpriterGetNext(repliterator);
1908 	         }
1909 	      }
1910 	   }
1911 	
1912 	   /* free memory */
1913 	   SCIPexpriterFree(&repliterator);
1914 	   SCIPmultihashFree(&key2expr);
1915 	   SCIPexpriterFree(&hashiterator);
1916 	
1917 	   return SCIP_OKAY;
1918 	}
1919 	
1920 	/** computes the curvature of a given expression and all its subexpressions
1921 	 *
1922 	 *  @note this function also evaluates all subexpressions w.r.t. current variable bounds
1923 	 *  @note this function relies on information from the curvature callback of expression handlers only,
1924 	 *    consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity
1925 	 */
1926 	SCIP_RETCODE SCIPcomputeExprCurvature(
1927 	   SCIP*                 scip,               /**< SCIP data structure */
1928 	   SCIP_EXPR*            expr                /**< expression */
1929 	   )
1930 	{
1931 	   SCIP_EXPRITER* it;
1932 	   SCIP_EXPRCURV curv;
1933 	   SCIP_EXPRCURV* childcurv;
1934 	   int childcurvsize;
1935 	   SCIP_Bool success;
1936 	   SCIP_EXPRCURV trialcurv[3] = { SCIP_EXPRCURV_LINEAR, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_CONCAVE };
1937 	   int i, c;
1938 	
1939 	   assert(scip != NULL);
1940 	   assert(scip->mem != NULL);
1941 	   assert(expr != NULL);
1942 	
1943 	   childcurvsize = 5;
1944 	   SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, childcurvsize) );
1945 	
1946 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1947 	   SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
1948 	   SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR);
1949 	
1950 	   for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
1951 	   {
1952 	      curv = SCIP_EXPRCURV_UNKNOWN;
1953 	
1954 	      if( !SCIPexprhdlrHasCurvature(SCIPexprGetHdlr(expr)) )
1955 	      {
1956 	         /* set curvature in expression */
1957 	         SCIPexprSetCurvature(expr, curv);
1958 	         continue;
1959 	      }
1960 	
1961 	      if( SCIPexprGetNChildren(expr) > childcurvsize )
1962 	      {
1963 	         childcurvsize = SCIPcalcMemGrowSize(scip, SCIPexprGetNChildren(expr));
1964 	         SCIP_CALL( SCIPreallocBufferArray(scip, &childcurv, childcurvsize) );
1965 	      }
1966 	
1967 	      for( i = 0; i < 3; ++i )
1968 	      {
1969 	         /* check if expression can have a curvature trialcurv[i] */
1970 	         SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, trialcurv[i], &success, childcurv) );
1971 	         if( !success )
1972 	            continue;
1973 	
1974 	         /* check if conditions on children are satisfied */
1975 	         for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1976 	         {
1977 	            if( (childcurv[c] & SCIPexprGetCurvature(SCIPexprGetChildren(expr)[c])) != childcurv[c] )
1978 	            {
1979 	               success = FALSE;
1980 	               break;
1981 	            }
1982 	         }
1983 	
1984 	         if( success )
1985 	         {
1986 	            curv = trialcurv[i];
1987 	            break;
1988 	         }
1989 	      }
1990 	
1991 	      /* set curvature in expression */
1992 	      SCIPexprSetCurvature(expr, curv);
1993 	   }
1994 	
1995 	   SCIPexpriterFree(&it);
1996 	
1997 	   SCIPfreeBufferArray(scip, &childcurv);
1998 	
1999 	   return SCIP_OKAY;
2000 	}
2001 	
2002 	/** computes integrality information of a given expression and all its subexpressions
2003 	 *
2004 	 * The integrality information can be accessed via SCIPexprIsIntegral().
2005 	 */
2006 	SCIP_RETCODE SCIPcomputeExprIntegrality(
2007 	   SCIP*                 scip,               /**< SCIP data structure */
2008 	   SCIP_EXPR*            expr                /**< expression */
2009 	   )
2010 	{
2011 	   SCIP_EXPRITER* it;
2012 	   SCIP_Bool isintegral;
2013 	
2014 	   assert(scip != NULL);
2015 	   assert(scip->mem != NULL);
2016 	   assert(expr != NULL);
2017 	
2018 	   /* shortcut for expr without children */
2019 	   if( SCIPexprGetNChildren(expr) == 0 )
2020 	   {
2021 	      /* compute integrality information */
2022 	      SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2023 	      SCIPexprSetIntegrality(expr, isintegral);
2024 	
2025 	      return SCIP_OKAY;
2026 	   }
2027 	
2028 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2029 	   SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
2030 	   SCIPexpriterSetStagesDFS(it, SCIP_EXPRITER_LEAVEEXPR);
2031 	
2032 	   for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2033 	   {
2034 	      /* compute integrality information */
2035 	      SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2036 	      SCIPexprSetIntegrality(expr, isintegral);
2037 	   }
2038 	
2039 	   SCIPexpriterFree(&it);
2040 	
2041 	   return SCIP_OKAY;
2042 	}
2043 	
2044 	/** returns the total number of variable expressions in an expression
2045 	 *
2046 	 * The function counts variable expressions in common sub-expressions only once, but
2047 	 * counts variables appearing in several variable expressions multiple times.
2048 	 */
2049 	SCIP_RETCODE SCIPgetExprNVars(
2050 	   SCIP*                 scip,               /**< SCIP data structure */
2051 	   SCIP_EXPR*            expr,               /**< expression */
2052 	   int*                  nvars               /**< buffer to store the total number of variables */
2053 	   )
2054 	{
2055 	   SCIP_EXPRITER* it;
2056 	
2057 	   assert(scip != NULL);
2058 	   assert(scip->mem != NULL);
2059 	   assert(expr != NULL);
2060 	   assert(nvars != NULL);
2061 	
2062 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2063 	   SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
2064 	
2065 	   *nvars = 0;
2066 	   for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2067 	      if( SCIPexprIsVar(scip->set, expr) )
2068 	         ++(*nvars);
2069 	
2070 	   SCIPexpriterFree(&it);
2071 	
2072 	   return SCIP_OKAY;
2073 	}
2074 	
2075 	/** returns all variable expressions contained in a given expression
2076 	 *
2077 	 * The array to store all variable expressions needs to be at least of size
2078 	 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars().
2079 	 *
2080 	 * If every variable is represented by only one variable expression (common subexpression have been removed)
2081 	 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars().
2082 	 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying,
2083 	 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars().
2084 	 *
2085 	 * @note function captures variable expressions
2086 	 */
2087 	SCIP_RETCODE SCIPgetExprVarExprs(
2088 	   SCIP*                 scip,               /**< SCIP data structure */
2089 	   SCIP_EXPR*            expr,               /**< expression */
2090 	   SCIP_EXPR**           varexprs,           /**< array to store all variable expressions */
2091 	   int*                  nvarexprs           /**< buffer to store the total number of variable expressions */
2092 	   )
2093 	{
2094 	   SCIP_EXPRITER* it;
2095 	
2096 	   assert(scip != NULL);
2097 	   assert(scip->mem != NULL);
2098 	   assert(expr != NULL);
2099 	   assert(varexprs != NULL);
2100 	   assert(nvarexprs != NULL);
2101 	
2102 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2103 	   SCIP_CALL( SCIPexpriterInit(it, expr, SCIP_EXPRITER_DFS, FALSE) );
2104 	
2105 	   *nvarexprs = 0;
2106 	   for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2107 	   {
2108 	      assert(expr != NULL);
2109 	
2110 	      if( SCIPexprIsVar(scip->set, expr) )
2111 	      {
2112 	         varexprs[(*nvarexprs)++] = expr;
2113 	
2114 	         /* capture expression */
2115 	         SCIPcaptureExpr(expr);
2116 	      }
2117 	   }
2118 	
2119 	   /* @todo sort variable expressions here? */
2120 	
2121 	   SCIPexpriterFree(&it);
2122 	
2123 	   return SCIP_OKAY;
2124 	}
2125 	
2126 	/** calls the print callback for an expression
2127 	 *
2128 	 * @see SCIP_DECL_EXPRPRINT
2129 	 */
2130 	SCIP_DECL_EXPRPRINT(SCIPcallExprPrint)
2131 	{
2132 	   assert(scip != NULL);
2133 	
2134 	   SCIP_CALL( SCIPexprhdlrPrintExpr(SCIPexprGetHdlr(expr), scip->set, scip->messagehdlr, expr, stage, currentchild, parentprecedence, file) );
2135 	
2136 	   return SCIP_OKAY;
2137 	}
2138 	
2139 	/** calls the curvature callback for an expression
2140 	 *
2141 	 * @see SCIP_DECL_EXPRCURVATURE
2142 	 *
2143 	 * Returns unknown curvature if callback not implemented.
2144 	 */
2145 	SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature)
2146 	{
2147 	   assert(scip != NULL);
2148 	
2149 	   SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, exprcurvature, success, childcurv) );
2150 	
2151 	   return SCIP_OKAY;
2152 	}
2153 	
2154 	/** calls the monotonicity callback for an expression
2155 	 *
2156 	 * @see SCIP_DECL_EXPRMONOTONICITY
2157 	 *
2158 	 * Returns unknown monotonicity if callback not implemented.
2159 	 */
2160 	SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity)
2161 	{
2162 	   assert(scip != NULL);
2163 	
2164 	   SCIP_CALL( SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), scip->set, expr, childidx, result) );
2165 	
2166 	   return SCIP_OKAY;
2167 	}
2168 	
2169 	/** calls the eval callback for an expression with given values for children
2170 	 *
2171 	 * Does not iterates over expressions, but requires values for children to be given.
2172 	 * Value is not stored in expression, but returned in `val`.
2173 	 * If an evaluation error (division by zero, ...) occurs, this value will
2174 	 * be set to `SCIP_INVALID`.
2175 	 */
2176 	SCIP_RETCODE SCIPcallExprEval(
2177 	   SCIP*                 scip,               /**< SCIP data structure */
2178 	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
2179 	   SCIP_Real*            childrenvalues,     /**< values for children */
2180 	   SCIP_Real*            val                 /**< buffer to store evaluated value */
2181 	   )
2182 	{
2183 	   assert(scip != NULL);
2184 	   assert(scip->mem != NULL);
2185 	   assert(childrenvalues != NULL);
2186 	   assert(val != NULL);
2187 	
2188 	   SCIP_CALL( SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, childrenvalues, NULL) );
2189 	
2190 	   return SCIP_OKAY;
2191 	}
2192 	
2193 	/** calls the eval and fwdiff callback of an expression with given values for children
2194 	 *
2195 	 * Does not iterates over expressions, but requires values for children and direction to be given.
2196 	 *
2197 	 * Value is not stored in expression, but returned in `val`.
2198 	 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2199 	 *
2200 	 * Direction is not stored in expression, but returned in `dot`.
2201 	 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2202 	 */
2203 	SCIP_RETCODE SCIPcallExprEvalFwdiff(
2204 	   SCIP*                 scip,               /**< SCIP data structure */
2205 	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
2206 	   SCIP_Real*            childrenvalues,     /**< values for children */
2207 	   SCIP_Real*            direction,          /**< direction in which to differentiate */
2208 	   SCIP_Real*            val,                /**< buffer to store evaluated value */
2209 	   SCIP_Real*            dot                 /**< buffer to store derivative value */
2210 	   )
2211 	{
2212 	   assert(scip != NULL);
2213 	   assert(scip->mem != NULL);
2214 	
2215 	   SCIP_CALL( SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, dot,
2216 	         childrenvalues, NULL, direction, NULL) );
2217 	
2218 	   return SCIP_OKAY;
2219 	}
2220 	
2221 	/** calls the interval evaluation callback for an expression
2222 	 *
2223 	 * @see SCIP_DECL_EXPRINTEVAL
2224 	 *
2225 	 * Returns entire interval if callback not implemented.
2226 	 */
2227 	SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval)
2228 	{
2229 	   assert(scip != NULL);
2230 	
2231 	   SCIP_CALL( SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), scip->set, expr, interval, intevalvar, intevalvardata) );
2232 	
2233 	   return SCIP_OKAY;
2234 	}
2235 	
2236 	/** calls the estimate callback for an expression
2237 	 *
2238 	 * @see SCIP_DECL_EXPRESTIMATE
2239 	 *
2240 	 * Returns without success if callback not implemented.
2241 	 */
2242 	SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate)
2243 	{
2244 	   assert(scip != NULL);
2245 	
2246 	   SCIP_CALL( SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), scip->set, expr, localbounds, globalbounds, refpoint,
2247 	         overestimate, targetvalue, coefs, constant, islocal, success, branchcand) );
2248 	
2249 	   return SCIP_OKAY;
2250 	}
2251 	
2252 	/** calls the initial estimators callback for an expression
2253 	 *
2254 	 * @see SCIP_DECL_EXPRINITESTIMATES
2255 	 *
2256 	 * Returns no estimators if callback not implemented.
2257 	 */
2258 	SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates)
2259 	{
2260 	   assert(scip != NULL);
2261 	
2262 	   SCIP_CALL( SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, overestimate, coefs,
2263 	         constant, nreturned) );
2264 	
2265 	   return SCIP_OKAY;
2266 	}
2267 	
2268 	/** calls the simplify callback for an expression
2269 	 *
2270 	 * @see SCIP_DECL_EXPRSIMPLIFY
2271 	 *
2272 	 * Returns unmodified expression if simplify callback not implemented.
2273 	 *
2274 	 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that.
2275 	 */
2276 	SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify)
2277 	{
2278 	   assert(scip != NULL);
2279 	
2280 	   /* use simplification of expression handlers */
2281 	   SCIP_CALL( SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), scip->set, expr, simplifiedexpr, ownercreate,
2282 	         ownercreatedata) );
2283 	
2284 	   return SCIP_OKAY;
2285 	}
2286 	
2287 	/** calls the reverse propagation callback for an expression
2288 	 *
2289 	 * @see SCIP_DECL_EXPRREVERSEPROP
2290 	 *
2291 	 * Returns unmodified childrenbounds if reverseprop callback not implemented.
2292 	 */
2293 	SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop)
2294 	{
2295 	   assert(scip != NULL);
2296 	
2297 	   SCIP_CALL( SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, childrenbounds, infeasible) );
2298 	
2299 	   return SCIP_OKAY;
2300 	}
2301 	
2302 	/** calls the symmetry data callback for an expression
2303 	 *
2304 	 * Returns no information if not implemented.
2305 	 */
2306 	SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData)
2307 	{
2308 	   assert(scip != NULL);
2309 	   assert(expr != NULL);
2310 	   assert(symdata != NULL);
2311 	
2312 	   SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) );
2313 	
2314 	   return SCIP_OKAY;
2315 	}
2316 	
2317 	/**@} */
2318 	
2319 	/**@name Expression Iterator Methods */
2320 	/**@{ */
2321 	
2322 	#ifdef NDEBUG
2323 	#undef SCIPcreateExpriter
2324 	#undef SCIPfreeExpriter
2325 	#endif
2326 	
2327 	/** creates an expression iterator */
2328 	SCIP_RETCODE SCIPcreateExpriter(
2329 	   SCIP*                 scip,               /**< SCIP data structure */
2330 	   SCIP_EXPRITER**       iterator            /**< buffer to store expression iterator */
2331 	   )
2332 	{
2333 	   assert(scip != NULL);
2334 	   assert(scip->mem != NULL);
2335 	
2336 	   SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, iterator) );
2337 	
2338 	   return SCIP_OKAY;
2339 	}
2340 	
2341 	/** frees an expression iterator */
2342 	void SCIPfreeExpriter(
2343 	   SCIP_EXPRITER**       iterator            /**< pointer to the expression iterator */
2344 	   )
2345 	{
2346 	   SCIPexpriterFree(iterator);
2347 	}
2348 	
2349 	/**@} */
2350 	
2351 	
2352 	/**@name Quadratic expression functions */
2353 	/**@{ */
2354 	
2355 	#ifdef NDEBUG
2356 	#undef SCIPcheckExprQuadratic
2357 	#undef SCIPfreeExprQuadratic
2358 	#undef SCIPcomputeExprQuadraticCurvature
2359 	#endif
2360 	
2361 	/** checks whether an expression is quadratic
2362 	 *
2363 	 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions),
2364 	 * or a sum of terms where at least one is a square or a product.
2365 	 *
2366 	 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic.
2367 	 */
2368 	SCIP_RETCODE SCIPcheckExprQuadratic(
2369 	   SCIP*                 scip,               /**< SCIP data structure */
2370 	   SCIP_EXPR*            expr,               /**< expression */
2371 	   SCIP_Bool*            isquadratic         /**< buffer to store result */
2372 	   )
2373 	{
2374 	   assert(scip != NULL);
2375 	   assert(scip->mem != NULL);
2376 	
2377 	   SCIP_CALL( SCIPexprCheckQuadratic(scip->set, scip->mem->probmem, expr, isquadratic) );
2378 	
2379 	   return SCIP_OKAY;
2380 	}
2381 	
2382 	/** frees information on quadratic representation of an expression
2383 	 *
2384 	 * Before doing changes to an expression, it can be useful to call this function.
2385 	 */
2386 	void SCIPfreeExprQuadratic(
2387 	   SCIP*                 scip,               /**< SCIP data structure */
2388 	   SCIP_EXPR*            expr                /**< expression */
2389 	   )
2390 	{
2391 	   assert(scip != NULL);
2392 	   assert(scip->mem != NULL);
2393 	
2394 	   SCIPexprFreeQuadratic(scip->mem->probmem, expr);
2395 	}
2396 	
2397 	/** evaluates quadratic term in a solution
2398 	 *
2399 	 * \note This requires that every expression used in the quadratic data is a variable expression.
2400 	 */
2401 	SCIP_Real SCIPevalExprQuadratic(
2402 	   SCIP*                 scip,               /**< SCIP data structure */
2403 	   SCIP_EXPR*            expr,               /**< quadratic expression */
2404 	   SCIP_SOL*             sol                 /**< solution to evaluate, or NULL for LP solution */
2405 	   )
2406 	{
2407 	   SCIP_Real auxvalue;
2408 	   int nlinexprs;
2409 	   SCIP_Real* lincoefs;
2410 	   SCIP_EXPR** linexprs;
2411 	   int nquadexprs;
2412 	   int nbilinexprs;
2413 	   int i;
2414 	
2415 	   assert(scip != NULL);
2416 	   assert(expr != NULL);
2417 	
2418 	   SCIPexprGetQuadraticData(expr, &auxvalue, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2419 	
2420 	   /* linear terms */
2421 	   for( i = 0; i < nlinexprs; ++i )
2422 	   {
2423 	      assert(SCIPexprIsVar(scip->set, linexprs[i]));
2424 	      auxvalue += lincoefs[i] * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(linexprs[i]));
2425 	   }
2426 	
2427 	   /* quadratic terms */
2428 	   for( i = 0; i < nquadexprs; ++i )
2429 	   {
2430 	      SCIP_EXPR* quadexprterm;
2431 	      SCIP_Real lincoef;
2432 	      SCIP_Real sqrcoef;
2433 	      SCIP_Real solval;
2434 	
2435 	      SCIPexprGetQuadraticQuadTerm(expr, i, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2436 	
2437 	      assert(SCIPexprIsVar(scip->set, quadexprterm));
2438 	
2439 	      solval = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(quadexprterm));
2440 	      auxvalue += (lincoef + sqrcoef * solval) * solval;
2441 	   }
2442 	
2443 	   /* bilinear terms */
2444 	   for( i = 0; i < nbilinexprs; ++i )
2445 	   {
2446 	      SCIP_EXPR* expr1;
2447 	      SCIP_EXPR* expr2;
2448 	      SCIP_Real coef;
2449 	
2450 	      SCIPexprGetQuadraticBilinTerm(expr, i, &expr1, &expr2, &coef, NULL, NULL);
2451 	
2452 	      assert(SCIPexprIsVar(scip->set, expr1));
2453 	      assert(SCIPexprIsVar(scip->set, expr2));
2454 	      auxvalue += coef * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr1)) * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr2));
2455 	   }
2456 	
2457 	   return auxvalue;
2458 	}
2459 	
2460 	/** prints quadratic expression */
2461 	SCIP_RETCODE SCIPprintExprQuadratic(
2462 	   SCIP*                 scip,               /**< SCIP data structure */
2463 	   SCIP_EXPR*            expr                /**< quadratic expression */
2464 	   )
2465 	{
2466 	   SCIP_Real constant;
2467 	   int nlinexprs;
2468 	   SCIP_Real* lincoefs;
2469 	   SCIP_EXPR** linexprs;
2470 	   int nquadexprs;
2471 	   int nbilinexprs;
2472 	   int c;
2473 	
2474 	   assert(scip != NULL);
2475 	   assert(expr != NULL);
2476 	
2477 	   SCIPexprGetQuadraticData(expr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2478 	
2479 	   SCIPinfoMessage(scip, NULL, "Constant: %g\n", constant);
2480 	
2481 	   SCIPinfoMessage(scip, NULL, "Linear: ");
2482 	   for( c = 0; c < nlinexprs; ++c )
2483 	   {
2484 	      SCIPinfoMessage(scip, NULL, "%g * ", lincoefs[c]);
2485 	      SCIP_CALL( SCIPprintExpr(scip, linexprs[c], NULL) );
2486 	      if( c < nlinexprs - 1 )
2487 	         SCIPinfoMessage(scip, NULL, " + ");
2488 	   }
2489 	   SCIPinfoMessage(scip, NULL, "\n");
2490 	
2491 	   SCIPinfoMessage(scip, NULL, "Quadratic: ");
2492 	   for( c = 0; c < nquadexprs; ++c )
2493 	   {
2494 	      SCIP_EXPR* quadexprterm;
2495 	      SCIP_Real lincoef;
2496 	      SCIP_Real sqrcoef;
2497 	
2498 	      SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2499 	      SCIPinfoMessage(scip, NULL, "(%g * sqr(", sqrcoef);
2500 	      SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2501 	      SCIPinfoMessage(scip, NULL, ") + %g) * ", lincoef);
2502 	      SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2503 	      if( c < nquadexprs - 1 )
2504 	         SCIPinfoMessage(scip, NULL, " + ");
2505 	   }
2506 	   SCIPinfoMessage(scip, NULL, "\n");
2507 	
2508 	   if( nbilinexprs == 0 )
2509 	   {
2510 	      SCIPinfoMessage(scip, NULL, "Bilinear: none\n");
2511 	      return SCIP_OKAY;
2512 	   }
2513 	
2514 	   SCIPinfoMessage(scip, NULL, "Bilinear: ");
2515 	   for( c = 0; c < nbilinexprs; ++c )
2516 	   {
2517 	      SCIP_EXPR* expr1;
2518 	      SCIP_EXPR* expr2;
2519 	      SCIP_Real coef;
2520 	
2521 	      SCIPexprGetQuadraticBilinTerm(expr, c, &expr1, &expr2, &coef, NULL, NULL);
2522 	
2523 	      SCIPinfoMessage(scip, NULL, "%g * ", coef);
2524 	      SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2525 	      SCIPinfoMessage(scip, NULL, " * ");
2526 	      SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2527 	      if( c < nbilinexprs - 1 )
2528 	         SCIPinfoMessage(scip, NULL, " + ");
2529 	   }
2530 	   SCIPinfoMessage(scip, NULL, "\n");
2531 	
2532 	   SCIPinfoMessage(scip, NULL, "Bilinear of quadratics: \n");
2533 	   for( c = 0; c < nquadexprs; ++c )
2534 	   {
2535 	      SCIP_EXPR* quadexprterm;
2536 	      int nadjbilin;
2537 	      int* adjbilin;
2538 	      int i;
2539 	
2540 	      SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, NULL, NULL, &nadjbilin, &adjbilin, NULL);
2541 	
2542 	      SCIPinfoMessage(scip, NULL, "  For ");
2543 	      SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2544 	      SCIPinfoMessage(scip, NULL, " we see: ");
2545 	      for( i = 0; i < nadjbilin; ++i )
2546 	      {
2547 	         SCIP_EXPR* expr1;
2548 	         SCIP_EXPR* expr2;
2549 	         SCIP_Real coef;
2550 	
2551 	         SCIPexprGetQuadraticBilinTerm(expr, adjbilin[i], &expr1, &expr2, &coef, NULL, NULL);
2552 	
2553 	         SCIPinfoMessage(scip, NULL, "%g * ", coef);
2554 	         SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2555 	         SCIPinfoMessage(scip, NULL, " * ");
2556 	         SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2557 	         if( i < nadjbilin - 1 )
2558 	            SCIPinfoMessage(scip, NULL, " + ");
2559 	      }
2560 	      SCIPinfoMessage(scip, NULL, "\n");
2561 	   }
2562 	
2563 	   return SCIP_OKAY;
2564 	}
2565 	
2566 	/** checks the curvature of the quadratic expression
2567 	 *
2568 	 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
2569 	 * If Q is
2570 	 * - semidefinite positive -> curv is set to convex,
2571 	 * - semidefinite negative -> curv is set to concave,
2572 	 * - otherwise -> curv is set to unknown.
2573 	 *
2574 	 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
2575 	 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
2576 	 */
2577 	SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(
2578 	   SCIP*                 scip,               /**< SCIP data structure */
2579 	   SCIP_EXPR*            expr,               /**< quadratic expression */
2580 	   SCIP_EXPRCURV*        curv,               /**< pointer to store the curvature of quadratics */
2581 	   SCIP_HASHMAP*         assumevarfixed,     /**< hashmap containing variables that should be assumed to be fixed, or NULL */
2582 	   SCIP_Bool             storeeigeninfo      /**< whether the eigenvalues and eigenvectors should be stored */
2583 	   )
2584 	{
2585 	   assert(scip != NULL);
2586 	   assert(scip->mem != NULL);
2587 	
2588 	   SCIP_CALL( SCIPexprComputeQuadraticCurvature(scip->set, scip->mem->probmem, scip->mem->buffer, scip->messagehdlr,
2589 	         expr, curv, assumevarfixed, storeeigeninfo) );
2590 	
2591 	   return SCIP_OKAY;
2592 	}
2593 	
2594 	/**@} */
2595 	
2596 	/**@name Monomial expression functions */
2597 	/**@{ */
2598 	
2599 	#ifdef NDEBUG
2600 	#undef SCIPgetExprMonomialData
2601 	#endif
2602 	
2603 	/** returns a monomial representation of a product expression
2604 	 *
2605 	 * The array to store all factor expressions needs to be of size the number of
2606 	 * children in the expression which is given by SCIPexprGetNChildren().
2607 	 *
2608 	 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where
2609 	 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can
2610 	 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents.
2611 	 *
2612 	 * A non-trivial monomial is a product of a least two expressions.
2613 	 */
2614 	SCIP_RETCODE SCIPgetExprMonomialData(
2615 	   SCIP*                 scip,               /**< SCIP data structure */
2616 	   SCIP_EXPR*            expr,               /**< expression */
2617 	   SCIP_Real*            coef,               /**< coefficient \f$c\f$ */
2618 	   SCIP_Real*            exponents,          /**< exponents \f$\alpha\f$ */
2619 	   SCIP_EXPR**           factors             /**< factor expressions \f$x\f$ */
2620 	   )
2621 	{
2622 	   assert(scip != NULL);
2623 	   assert(scip->mem != NULL);
2624 	
2625 	   SCIP_CALL( SCIPexprGetMonomialData(scip->set, scip->mem->probmem, expr, coef, exponents, factors) );
2626 	
2627 	   return SCIP_OKAY;
2628 	}
2629 	
2630 	/**@} */
2631