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