Scippy

SCIP

Solving Constraint Integer Programs

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