Scippy

SCIP

Solving Constraint Integer Programs

expr.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file expr.c
26  * @ingroup OTHER_CFILES
27  * @brief functions for algebraic expressions
28  * @author Ksenia Bestuzheva
29  * @author Benjamin Mueller
30  * @author Felipe Serrano
31  * @author Stefan Vigerske
32  */
33 
34 #include <assert.h>
35 #include <ctype.h>
36 
37 #include "scip/expr.h"
38 #include "scip/struct_expr.h"
39 #include "scip/pub_misc.h"
40 #include "scip/clock.h"
41 #include "scip/set.h"
42 #include "scip/pub_var.h"
43 #include "scip/pub_message.h"
44 #include "scip/sol.h"
45 #include "scip/tree.h"
46 #include "scip/struct_set.h"
47 #include "scip/struct_stat.h"
48 #include "scip/lapack_calls.h"
49 
50 /*lint -e440*/
51 /*lint -e441*/
52 /*lint -e777*/
53 
54 /*
55  * Data structures
56  */
57 
58 /** printing to file data */
59 struct SCIP_ExprPrintData
60 {
61  FILE* file; /**< file to print to */
62  SCIP_EXPRITER* iterator; /**< iterator to use */
63  SCIP_Bool closefile; /**< whether file need to be closed when finished printing */
64  SCIP_HASHMAP* leaveexprs; /**< hashmap storing leave (no children) expressions */
65  SCIP_EXPRPRINT_WHAT whattoprint; /**< flags that indicate what to print for each expression */
66 };
67 
68 /*
69  * Local methods
70  */
71 
72 /** frees an expression */
73 static
75  BMS_BLKMEM* blkmem, /**< block memory */
76  SCIP_EXPR** expr /**< pointer to free the expression */
77  )
78 {
79  assert(expr != NULL);
80  assert(*expr != NULL);
81  assert((*expr)->nuses == 1);
82  assert((*expr)->quaddata == NULL);
83  assert((*expr)->ownerdata == NULL);
84 
85  /* free children array, if any */
86  BMSfreeBlockMemoryArrayNull(blkmem, &(*expr)->children, (*expr)->childrensize);
87 
88  BMSfreeBlockMemory(blkmem, expr);
89  assert(*expr == NULL);
90 
91  return SCIP_OKAY;
92 }
93 
94 /*
95  * quadratic representation of expression
96  */
97 
98 /** first time seen quadratically and
99  * seen before linearly --> --nlinterms; assign 2; ++nquadterms
100  * not seen before linearly --> assing 1; ++nquadterms
101  *
102  * seen before --> assign += 1
103  */
104 static
106  SCIP_EXPR* expr, /**< the expression */
107  SCIP_HASHMAP* seenexpr, /**< hash map */
108  int* nquadterms, /**< number of quadratic terms */
109  int* nlinterms /**< number of linear terms */
110  )
111 {
112  if( SCIPhashmapExists(seenexpr, (void*)expr) )
113  {
114  int nseen = SCIPhashmapGetImageInt(seenexpr, (void*)expr);
115 
116  if( nseen < 0 )
117  {
118  /* only seen linearly before */
119  assert(nseen == -1);
120 
121  --*nlinterms;
122  ++*nquadterms;
123  SCIP_CALL( SCIPhashmapSetImageInt(seenexpr, (void*)expr, 2) );
124  }
125  else
126  {
127  assert(nseen > 0);
128  SCIP_CALL( SCIPhashmapSetImageInt(seenexpr, (void*)expr, nseen + 1) );
129  }
130  }
131  else
132  {
133  ++*nquadterms;
134  SCIP_CALL( SCIPhashmapInsertInt(seenexpr, (void*)expr, 1) );
135  }
136 
137  return SCIP_OKAY;
138 }
139 
140 /** returns a quadexprterm that contains the expr
141  *
142  * it either finds one that already exists or creates a new one
143  */
144 static
146  BMS_BLKMEM* blkmem, /**< block memory */
147  SCIP_EXPR* expr, /**< the expression */
148  SCIP_HASHMAP* expr2idx, /**< map: expr to index in quadexpr->quadexprterms */
149  SCIP_HASHMAP* seenexpr, /**< map: expr to number of times it was seen */
150  SCIP_QUADEXPR* quadexpr, /**< data of quadratic representation of expression */
151  SCIP_QUADEXPR_QUADTERM** quadexprterm /**< buffer to store quadexprterm */
152  )
153 {
154  assert(expr != NULL);
155  assert(expr2idx != NULL);
156  assert(quadexpr != NULL);
157  assert(quadexprterm != NULL);
158 
159  if( SCIPhashmapExists(expr2idx, (void*)expr) )
160  {
161  *quadexprterm = &quadexpr->quadexprterms[SCIPhashmapGetImageInt(expr2idx, (void*)expr)];
162  assert((*quadexprterm)->expr == expr);
163  }
164  else
165  {
166  SCIP_CALL( SCIPhashmapInsertInt(expr2idx, expr, quadexpr->nquadexprs) );
167  *quadexprterm = &quadexpr->quadexprterms[quadexpr->nquadexprs];
168  ++quadexpr->nquadexprs;
169 
170  (*quadexprterm)->expr = expr;
171  (*quadexprterm)->sqrcoef = 0.0;
172  (*quadexprterm)->sqrexpr = NULL;
173  (*quadexprterm)->lincoef = 0.0;
174  (*quadexprterm)->nadjbilin = 0;
175  (*quadexprterm)->adjbilinsize = SCIPhashmapGetImageInt(seenexpr, (void*)expr);
176  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*quadexprterm)->adjbilin, (*quadexprterm)->adjbilinsize) );
177  }
178 
179  return SCIP_OKAY;
180 }
181 
182 
183 /** evaluate and forward-differentiate expression
184  *
185  * also initializes derivative and bardot to 0.0
186  */
187 static
189  SCIP_SET* set, /**< global SCIP settings */
190  SCIP_STAT* stat, /**< dynamic problem statistics */
191  BMS_BLKMEM* blkmem, /**< block memory */
192  SCIP_EXPR* expr, /**< expression to be evaluated */
193  SCIP_SOL* sol, /**< solution to be evaluated */
194  SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */
195  SCIP_SOL* direction /**< direction for directional derivative */
196  )
197 {
198  SCIP_EXPRITER* it;
199 
200  assert(set != NULL);
201  assert(stat != NULL);
202  assert(blkmem != NULL);
203  assert(expr != NULL);
204 
205  /* assume we'll get a domain error, so we don't have to get this expr back if we abort the iteration
206  * if there is no domain error, then we will overwrite the evalvalue in the last leaveexpr stage
207  */
208  expr->evalvalue = SCIP_INVALID;
209  expr->evaltag = soltag;
210  expr->dot = SCIP_INVALID;
211 
212  /* start a new difftag */
213  ++stat->exprlastdifftag;
214 
215  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
218 
219  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
220  {
221  /* evaluate expression only if necessary */
222  if( soltag == 0 || expr->evaltag != soltag )
223  {
224  SCIP_CALL( SCIPexprhdlrEvalExpr(expr->exprhdlr, set, NULL, expr, &expr->evalvalue, NULL, sol) );
225 
226  expr->evaltag = soltag;
227  }
228 
229  if( expr->evalvalue == SCIP_INVALID )
230  break;
231 
232  if( expr->difftag != stat->exprlastdifftag )
233  {
234  /* compute forward diff */
235  SCIP_CALL( SCIPexprhdlrFwDiffExpr(expr->exprhdlr, set, expr, &expr->dot, direction) );
236 
237  if( expr->dot == SCIP_INVALID )
238  break;
239 
240  expr->derivative = 0.0;
241  expr->bardot = 0.0;
242  expr->difftag = stat->exprlastdifftag;
243  }
244  }
245 
246  SCIPexpriterFree(&it);
247 
248  return SCIP_OKAY;
249 }
250 
251 
252 /*
253  * Public methods
254  */
255 
256 /* Undo the defines from pub_expr.h, which exist if NDEBUG is defined. */
257 #ifdef NDEBUG
258 #undef SCIPexprhdlrSetCopyFreeHdlr
259 #undef SCIPexprhdlrSetCopyFreeData
260 #undef SCIPexprhdlrSetPrint
261 #undef SCIPexprhdlrSetParse
262 #undef SCIPexprhdlrSetCurvature
263 #undef SCIPexprhdlrSetMonotonicity
264 #undef SCIPexprhdlrSetIntegrality
265 #undef SCIPexprhdlrSetHash
266 #undef SCIPexprhdlrSetCompare
267 #undef SCIPexprhdlrSetDiff
268 #undef SCIPexprhdlrSetIntEval
269 #undef SCIPexprhdlrSetSimplify
270 #undef SCIPexprhdlrSetReverseProp
271 #undef SCIPexprhdlrSetEstimate
272 #undef SCIPexprhdlrSetGetSymdata
273 #undef SCIPexprhdlrGetName
274 #undef SCIPexprhdlrGetDescription
275 #undef SCIPexprhdlrGetPrecedence
276 #undef SCIPexprhdlrGetData
277 #undef SCIPexprhdlrHasPrint
278 #undef SCIPexprhdlrHasBwdiff
279 #undef SCIPexprhdlrHasFwdiff
280 #undef SCIPexprhdlrHasIntEval
281 #undef SCIPexprhdlrHasEstimate
282 #undef SCIPexprhdlrHasInitEstimates
283 #undef SCIPexprhdlrHasSimplify
284 #undef SCIPexprhdlrHasCurvature
285 #undef SCIPexprhdlrHasMonotonicity
286 #undef SCIPexprhdlrHasReverseProp
287 #undef SCIPexprhdlrGetNCreated
288 #undef SCIPexprhdlrGetNIntevalCalls
289 #undef SCIPexprhdlrGetIntevalTime
290 #undef SCIPexprhdlrGetNReversepropCalls
291 #undef SCIPexprhdlrGetReversepropTime
292 #undef SCIPexprhdlrGetNCutoffs
293 #undef SCIPexprhdlrGetNDomainReductions
294 #undef SCIPexprhdlrIncrementNDomainReductions
295 #undef SCIPexprhdlrGetNEstimateCalls
296 #undef SCIPexprhdlrGetEstimateTime
297 #undef SCIPexprhdlrGetNBranchings
298 #undef SCIPexprhdlrIncrementNBranchings
299 #undef SCIPexprhdlrGetNSimplifyCalls
300 #undef SCIPexprhdlrGetSimplifyTime
301 #undef SCIPexprhdlrGetNSimplifications
302 #endif
303 
304 /** create expression handler */
306  BMS_BLKMEM* blkmem, /**< block memory */
307  SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */
308  const char* name, /**< name of expression handler (must not be NULL) */
309  const char* desc, /**< description of expression handler (can be NULL) */
310  unsigned int precedence, /**< precedence of expression operation (used for printing) */
311  SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */
312  SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */
313  )
314 {
315  assert(exprhdlr != NULL);
316  assert(name != NULL);
317 
318  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, exprhdlr) );
319 
320  SCIP_ALLOC( BMSduplicateMemoryArray(&(*exprhdlr)->name, name, strlen(name)+1) );
321  if( desc != NULL )
322  {
323  SCIP_ALLOC( BMSduplicateMemoryArray(&(*exprhdlr)->desc, desc, strlen(desc)+1) );
324  }
325 
326  (*exprhdlr)->precedence = precedence;
327  (*exprhdlr)->eval = eval;
328  (*exprhdlr)->data = data;
329 
330  /* create clocks */
331  SCIP_CALL( SCIPclockCreate(&(*exprhdlr)->estimatetime, SCIP_CLOCKTYPE_DEFAULT) );
332  SCIP_CALL( SCIPclockCreate(&(*exprhdlr)->intevaltime, SCIP_CLOCKTYPE_DEFAULT) );
333  SCIP_CALL( SCIPclockCreate(&(*exprhdlr)->proptime, SCIP_CLOCKTYPE_DEFAULT) );
334  SCIP_CALL( SCIPclockCreate(&(*exprhdlr)->simplifytime, SCIP_CLOCKTYPE_DEFAULT) );
335 
336  return SCIP_OKAY;
337 }
338 
339 /** frees expression handler */
341  SCIP_EXPRHDLR** exprhdlr, /**< pointer to expression handler to be freed */
342  SCIP_SET* set, /**< global SCIP settings */
343  BMS_BLKMEM* blkmem /**< block memory */
344  )
345 {
346  if( (*exprhdlr)->freehdlr != NULL )
347  {
348  SCIP_CALL( (*exprhdlr)->freehdlr(set->scip, *exprhdlr, &(*exprhdlr)->data) );
349  }
350 
351  /* free clocks */
352  SCIPclockFree(&(*exprhdlr)->simplifytime);
353  SCIPclockFree(&(*exprhdlr)->intevaltime);
354  SCIPclockFree(&(*exprhdlr)->proptime);
355  SCIPclockFree(&(*exprhdlr)->estimatetime);
356 
357  BMSfreeMemoryArrayNull(&(*exprhdlr)->desc);
358  BMSfreeMemoryArray(&(*exprhdlr)->name);
359 
360  BMSfreeBlockMemory(blkmem, exprhdlr);
361 
362  return SCIP_OKAY;
363 }
364 
365 /**@addtogroup PublicExprHandlerMethods
366  * @{
367  */
368 
369 /** set the expression handler callbacks to copy and free an expression handler */
371  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
372  SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), /**< handler copy callback (can be NULL) */
373  SCIP_DECL_EXPRFREEHDLR((*freehdlr)) /**< handler free callback (can be NULL) */
374  )
375 {
376  assert(exprhdlr != NULL);
377 
378  exprhdlr->copyhdlr = copyhdlr;
379  exprhdlr->freehdlr = freehdlr;
380 }
381 
382 /** set the expression handler callbacks to copy and free expression data */
384  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
385  SCIP_DECL_EXPRCOPYDATA((*copydata)), /**< expression data copy callback (can be NULL for expressions without data) */
386  SCIP_DECL_EXPRFREEDATA((*freedata)) /**< expression data free callback (can be NULL if data does not need to be freed) */
387  )
388 { /*lint --e{715}*/
389  assert(exprhdlr != NULL);
390 
391  exprhdlr->copydata = copydata;
392  exprhdlr->freedata = freedata;
393 }
394 
395 /** set the print callback of an expression handler */
397  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
398  SCIP_DECL_EXPRPRINT((*print)) /**< print callback (can be NULL) */
399  )
400 {
401  assert(exprhdlr != NULL);
402 
403  exprhdlr->print = print;
404 }
405 
406 /** set the parse callback of an expression handler */
408  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
409  SCIP_DECL_EXPRPARSE((*parse)) /**< parse callback (can be NULL) */
410  )
411 {
412  assert(exprhdlr != NULL);
413 
414  exprhdlr->parse = parse;
415 }
416 
417 /** set the curvature detection callback of an expression handler */
419  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
420  SCIP_DECL_EXPRCURVATURE((*curvature)) /**< curvature detection callback (can be NULL) */
421  )
422 {
423  assert(exprhdlr != NULL);
424 
425  exprhdlr->curvature = curvature;
426 }
427 
428 /** set the monotonicity detection callback of an expression handler */
430  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
431  SCIP_DECL_EXPRMONOTONICITY((*monotonicity)) /**< monotonicity detection callback (can be NULL) */
432  )
433 {
434  assert(exprhdlr != NULL);
435 
436  exprhdlr->monotonicity = monotonicity;
437 }
438 
439 /** set the integrality detection callback of an expression handler */
441  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
442  SCIP_DECL_EXPRINTEGRALITY((*integrality)) /**< integrality detection callback (can be NULL) */
443  )
444 {
445  assert(exprhdlr != NULL);
446 
447  exprhdlr->integrality = integrality;
448 }
449 
450 /** set the hash callback of an expression handler */
452  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
453  SCIP_DECL_EXPRHASH((*hash)) /**< hash callback (can be NULL) */
454  )
455 {
456  assert(exprhdlr != NULL);
457 
458  exprhdlr->hash = hash;
459 }
460 
461 /** set the compare callback of an expression handler */
463  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
464  SCIP_DECL_EXPRCOMPARE((*compare)) /**< compare callback (can be NULL) */
465  )
466 {
467  assert(exprhdlr != NULL);
468 
469  exprhdlr->compare = compare;
470 }
471 
472 /** set differentiation callbacks of an expression handler */
474  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
475  SCIP_DECL_EXPRBWDIFF((*bwdiff)), /**< backward derivative evaluation callback (can be NULL) */
476  SCIP_DECL_EXPRFWDIFF((*fwdiff)), /**< forward derivative evaluation callback (can be NULL) */
477  SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)) /**< backward-forward derivative evaluation callback (can be NULL) */
478  )
479 {
480  assert(exprhdlr != NULL);
481 
482  exprhdlr->bwdiff = bwdiff;
483  exprhdlr->fwdiff = fwdiff;
484  exprhdlr->bwfwdiff = bwfwdiff;
485 }
486 
487 /** set the interval evaluation callback of an expression handler */
489  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
490  SCIP_DECL_EXPRINTEVAL((*inteval)) /**< interval evaluation callback (can be NULL) */
491  )
492 {
493  assert(exprhdlr != NULL);
494 
495  exprhdlr->inteval = inteval;
496 }
497 
498 /** set the simplify callback of an expression handler */
500  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
501  SCIP_DECL_EXPRSIMPLIFY((*simplify)) /**< simplify callback (can be NULL) */
502  )
503 {
504  assert(exprhdlr != NULL);
505 
506  exprhdlr->simplify = simplify;
507 }
508 
509 /** set the reverse propagation callback of an expression handler */
511  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
512  SCIP_DECL_EXPRREVERSEPROP((*reverseprop)) /**< reverse propagation callback (can be NULL) */
513  )
514 {
515  assert(exprhdlr != NULL);
516 
517  exprhdlr->reverseprop = reverseprop;
518 }
519 
520 /** set the symmetry information callback of an expression handler */
522  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
523  SCIP_DECL_EXPRGETSYMDATA((*getsymdata)) /**< symmetry information callback (can be NULL) */
524  )
525 {
526  assert(exprhdlr != NULL);
527 
528  exprhdlr->getsymdata = getsymdata;
529 }
530 
531 /** set the estimation callbacks of an expression handler */
533  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
534  SCIP_DECL_EXPRINITESTIMATES((*initestimates)), /**< initial estimators callback (can be NULL) */
535  SCIP_DECL_EXPRESTIMATE((*estimate)) /**< estimator callback (can be NULL) */
536  )
537 {
538  assert(exprhdlr != NULL);
539 
540  exprhdlr->initestimates = initestimates;
541  exprhdlr->estimate = estimate;
542 }
543 
544 /** gives the name of an expression handler */
546  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
547  )
548 {
549  assert(exprhdlr != NULL);
550 
551  return exprhdlr->name;
552 }
553 
554 /** gives the description of an expression handler (can be NULL) */
556  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
557  )
558 {
559  assert(exprhdlr != NULL);
560 
561  return exprhdlr->desc;
562 }
563 
564 /** gives the precedence of an expression handler */
566  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
567  )
568 {
569  assert(exprhdlr != NULL);
570 
571  return exprhdlr->precedence;
572 }
573 
574 /** gives the data of an expression handler */
576  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
577  )
578 {
579  assert(exprhdlr != NULL);
580 
581  return exprhdlr->data;
582 }
583 
584 /** returns whether expression handler implements the print callback */
586  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
587  )
588 {
589  assert(exprhdlr != NULL);
590 
591  return exprhdlr->print != NULL;
592 }
593 
594 /** returns whether expression handler implements the backward differentiation callback */
596  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
597  )
598 {
599  assert(exprhdlr != NULL);
600 
601  return exprhdlr->bwdiff != NULL;
602 }
603 
604 /** returns whether expression handler implements the forward differentiation callback */
606  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
607  )
608 {
609  assert(exprhdlr != NULL);
610 
611  return exprhdlr->fwdiff != NULL;
612 }
613 
614 /** returns whether expression handler implements the interval evaluation callback */
616  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
617  )
618 {
619  assert(exprhdlr != NULL);
620 
621  return exprhdlr->inteval != NULL;
622 }
623 
624 /** returns whether expression handler implements the estimator callback */
626  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
627  )
628 {
629  assert(exprhdlr != NULL);
630 
631  return exprhdlr->estimate != NULL;
632 }
633 
634 /** returns whether expression handler implements the initial estimators callback */
636  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
637  )
638 {
639  assert(exprhdlr != NULL);
640 
641  return exprhdlr->initestimates != NULL;
642 }
643 
644 /** returns whether expression handler implements the simplification callback */
646  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
647  )
648 {
649  assert(exprhdlr != NULL);
650 
651  return exprhdlr->simplify != NULL;
652 }
653 
654 /** returns whether expression handler implements the curvature callback */
656  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
657  )
658 {
659  assert(exprhdlr != NULL);
660 
661  return exprhdlr->curvature != NULL;
662 }
663 
664 /** returns whether expression handler implements the monotonicity callback */
666  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
667  )
668 {
669  assert(exprhdlr != NULL);
670 
671  return exprhdlr->monotonicity != NULL;
672 }
673 
674 /** returns whether expression handler implements the reverse propagation callback */
676  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
677  )
678 {
679  assert(exprhdlr != NULL);
680 
681  return exprhdlr->reverseprop != NULL;
682 }
683 
684 /** returns whether expression handler implements the symmetry information callback */
686  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
687  )
688 {
689  assert(exprhdlr != NULL);
690 
691  return exprhdlr->getsymdata != NULL;
692 }
693 
694 /** compares two expression handler w.r.t. their name */
695 SCIP_DECL_SORTPTRCOMP(SCIPexprhdlrComp)
696 {
697  return strcmp(((SCIP_EXPRHDLR*)elem1)->name, ((SCIP_EXPRHDLR*)elem2)->name);
698 }
699 
700 /** gets number of times an expression has been created with given expression handler */
702  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
703  )
704 {
705  assert(exprhdlr != NULL);
706 
707  return exprhdlr->ncreated;
708 }
709 
710 /** gets number of times the interval evaluation callback was called */
712  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
713  )
714 {
715  assert(exprhdlr != NULL);
716 
717  return exprhdlr->nintevalcalls;
718 }
719 
720 /** gets time spend in interval evaluation callback */
722  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
723  )
724 {
725  assert(exprhdlr != NULL);
726 
727  return SCIPclockGetTime(exprhdlr->intevaltime);
728 }
729 
730 /** gets number of times the reverse propagation callback was called */
732  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
733  )
734 {
735  assert(exprhdlr != NULL);
736 
737  return exprhdlr->npropcalls;
738 }
739 
740 /** gets time spend in reverse propagation callback */
742  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
743  )
744 {
745  assert(exprhdlr != NULL);
746 
747  return SCIPclockGetTime(exprhdlr->proptime);
748 }
749 
750 /** gets number of times an empty interval was found in reverse propagation */
752  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
753  )
754 {
755  assert(exprhdlr != NULL);
756 
757  return exprhdlr->ncutoffs;
758 }
759 
760 /** gets number of times a bound reduction was found in reverse propagation (and accepted by caller) */
762  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
763  )
764 {
765  assert(exprhdlr != NULL);
766 
767  return exprhdlr->ndomreds;
768 }
769 
770 /** increments the domain reductions count of an expression handler */
772  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
773  int nreductions /**< number of reductions to add to counter */
774  )
775 {
776  assert(exprhdlr != NULL);
777  assert(nreductions >= 0);
778 
779  exprhdlr->ndomreds += nreductions;
780 }
781 
782 /** gets number of times the estimation callback was called */
784  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
785  )
786 {
787  assert(exprhdlr != NULL);
788 
789  return exprhdlr->nestimatecalls;
790 }
791 
792 /** gets time spend in estimation callback */
794  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
795  )
796 {
797  assert(exprhdlr != NULL);
798 
799  return SCIPclockGetTime(exprhdlr->estimatetime);
800 }
801 
802 /** gets number of times branching candidates reported by of this expression handler were used to
803  * assemble branching candidates
804  *
805  * that is, how often did we consider branching on a child of this expression
806  */
808  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
809  )
810 {
811  assert(exprhdlr != NULL);
812 
813  return exprhdlr->nbranchscores;
814 }
815 
816 /** increments the branching candidates count of an expression handler */
818  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
819  )
820 {
821  assert(exprhdlr != NULL);
822 
823  ++exprhdlr->nbranchscores;
824 }
825 
826 /** gets number of times the simplify callback was called */
828  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
829  )
830 {
831  assert(exprhdlr != NULL);
832 
833  return exprhdlr->nsimplifycalls;
834 }
835 
836 /** gets time spend in simplify callback */
838  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
839  )
840 {
841  assert(exprhdlr != NULL);
842 
843  return SCIPclockGetTime(exprhdlr->simplifytime);
844 }
845 
846 /** gets number of times the simplify callback found a simplification */
848  SCIP_EXPRHDLR* exprhdlr /**< expression handler */
849  )
850 {
851  assert(exprhdlr != NULL);
852 
853  return exprhdlr->nsimplified;
854 }
855 
856 /** @} */
857 
858 /** copies the given expression handler to a new scip */
860  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
861  SCIP_SET* targetset /**< SCIP_SET of SCIP to copy to */
862  )
863 {
864  assert(exprhdlr != NULL);
865  assert(targetset != NULL);
866  assert(targetset->scip != NULL);
867 
868  if( exprhdlr->copyhdlr != NULL )
869  {
870  SCIPsetDebugMsg(targetset, "including expression handler <%s> in subscip %p\n",
871  SCIPexprhdlrGetName(exprhdlr), (void*)targetset->scip);
872  SCIP_CALL( exprhdlr->copyhdlr(targetset->scip, exprhdlr) );
873  }
874  else
875  {
876  SCIPsetDebugMsg(targetset, "expression handler <%s> cannot be copied to subscip %p due "
877  "to missing copyhdlr callback\n", SCIPexprhdlrGetName(exprhdlr), (void*)targetset->scip);
878  }
879 
880  return SCIP_OKAY;
881 }
882 
883 /** initialization of expression handler (resets statistics) */
885  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
886  SCIP_SET* set /**< global SCIP settings */
887  )
888 {
889  assert(exprhdlr != NULL);
890 
891  if( set->misc_resetstat )
892  {
893  exprhdlr->ncreated = 0;
894  exprhdlr->nestimatecalls = 0;
895  exprhdlr->nintevalcalls = 0;
896  exprhdlr->npropcalls = 0;
897  exprhdlr->ncutoffs = 0;
898  exprhdlr->ndomreds = 0;
899  exprhdlr->nbranchscores = 0;
900  exprhdlr->nsimplifycalls = 0;
901  exprhdlr->nsimplified = 0;
902 
903  SCIPclockReset(exprhdlr->estimatetime);
904  SCIPclockReset(exprhdlr->intevaltime);
905  SCIPclockReset(exprhdlr->proptime);
906  SCIPclockReset(exprhdlr->simplifytime);
907  }
908 }
909 
910 /** calls the print callback of an expression handler
911  *
912  * The method prints an expression.
913  * It is called while iterating over the expression graph at different stages.
914  *
915  * @see SCIP_DECL_EXPRPRINT
916  */
918  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
919  SCIP_SET* set, /**< global SCIP settings */
920  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
921  SCIP_EXPR* expr, /**< expression */
922  SCIP_EXPRITER_STAGE stage, /**< stage of expression iteration */
923  int currentchild, /**< index of current child if in stage visitingchild or visitedchild */
924  unsigned int parentprecedence, /**< precedence of parent */
925  FILE* file /**< the file to print to */
926  )
927 {
928  assert(exprhdlr != NULL);
929  assert(set != NULL);
930  assert(expr != NULL);
931  assert(expr->exprhdlr == exprhdlr);
932  assert(messagehdlr != NULL);
933 
934  if( SCIPexprhdlrHasPrint(exprhdlr) )
935  {
936  SCIP_CALL( exprhdlr->print(set->scip, expr, stage, currentchild, parentprecedence, file) );
937  }
938  else
939  {
940  /* default: <hdlrname>(<child1>, <child2>, ...) */
941  switch( stage )
942  {
944  {
945  SCIPmessageFPrintInfo(messagehdlr, file, "%s", SCIPexprhdlrGetName(expr->exprhdlr));
946  if( expr->nchildren > 0 )
947  {
948  SCIPmessageFPrintInfo(messagehdlr, file, "(");
949  }
950  break;
951  }
952 
954  {
955  assert(currentchild >= 0);
956  assert(currentchild < expr->nchildren);
957  if( currentchild < expr->nchildren-1 )
958  {
959  SCIPmessageFPrintInfo(messagehdlr, file, ", ");
960  }
961  else
962  {
963  SCIPmessageFPrintInfo(messagehdlr, file, ")");
964  }
965 
966  break;
967  }
968 
971  default:
972  break;
973  }
974  }
975 
976  return SCIP_OKAY;
977 }
978 
979 /** calls the parse callback of an expression handler
980  *
981  * The method parses an expression.
982  * It should be called when parsing an expression and an operator with the expr handler name is found.
983  *
984  * @see SCIP_DECL_EXPRPARSE
985  */
987  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
988  SCIP_SET* set, /**< global SCIP settings */
989  const char* string, /**< string containing expression to be parse */
990  const char** endstring, /**< buffer to store the position of string after parsing */
991  SCIP_EXPR** expr, /**< buffer to store the parsed expression */
992  SCIP_Bool* success, /**< buffer to store whether the parsing was successful or not */
993  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
994  void* ownercreatedata /**< data to pass to ownercreate */
995  )
996 {
997  assert(exprhdlr != NULL);
998  assert(set != NULL);
999  assert(expr != NULL);
1000 
1001  *expr = NULL;
1002 
1003  if( exprhdlr->parse == NULL )
1004  {
1005  /* TODO we could just look for a comma separated list of operands and try to initialize the expr with this one?
1006  * That would be sufficient for sin, cos, exp, log, abs, for example.
1007  */
1008  SCIPdebugMessage("Expression handler <%s> has no parsing method.\n", SCIPexprhdlrGetName(exprhdlr));
1009  *success = FALSE;
1010  return SCIP_OKAY;
1011  }
1012 
1013  /* give control to exprhdlr's parser */
1014  SCIP_CALL( exprhdlr->parse(set->scip, exprhdlr, string, endstring, expr, success, ownercreate, ownercreatedata) );
1015 
1016  assert(*success || (*expr == NULL));
1017 
1018  return SCIP_OKAY;
1019 }
1020 
1021 /** calls the curvature check callback of an expression handler
1022  *
1023  * @see SCIP_DECL_EXPRCURVATURE
1024  */
1026  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1027  SCIP_SET* set, /**< global SCIP settings */
1028  SCIP_EXPR* expr, /**< expression to check the curvature for */
1029  SCIP_EXPRCURV exprcurvature, /**< desired curvature of this expression */
1030  SCIP_Bool* success, /**< buffer to store whether the desired curvature be obtained */
1031  SCIP_EXPRCURV* childcurv /**< array to store required curvature for each child */
1032  )
1033 {
1034  assert(exprhdlr != NULL);
1035  assert(set != NULL);
1036  assert(expr != NULL);
1037  assert(expr->exprhdlr == exprhdlr);
1038  assert(success != NULL);
1039 
1040  *success = FALSE;
1041 
1042  if( exprhdlr->curvature != NULL )
1043  {
1044  SCIP_CALL( exprhdlr->curvature(set->scip, expr, exprcurvature, success, childcurv) );
1045  }
1046 
1047  return SCIP_OKAY;
1048 }
1049 
1050 /** calls the monotonicity check callback of an expression handler
1051  *
1052  * @see SCIP_DECL_EXPRMONOTONICITY
1053  */
1055  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1056  SCIP_SET* set, /**< global SCIP settings */
1057  SCIP_EXPR* expr, /**< expression to check the monotonicity for */
1058  int childidx, /**< index of the considered child expression */
1059  SCIP_MONOTONE* result /**< buffer to store the monotonicity */
1060  )
1061 {
1062  assert(exprhdlr != NULL);
1063  assert(set != NULL);
1064  assert(expr != NULL);
1065  assert(expr->exprhdlr == exprhdlr);
1066  assert(result != NULL);
1067 
1068  *result = SCIP_MONOTONE_UNKNOWN;
1069 
1070  /* check whether the expression handler implements the monotonicity callback */
1071  if( exprhdlr->monotonicity != NULL )
1072  {
1073  SCIP_CALL( exprhdlr->monotonicity(set->scip, expr, childidx, result) );
1074  }
1075 
1076  return SCIP_OKAY;
1077 }
1078 
1079 /** calls the integrality check callback of an expression handler
1080  *
1081  * @see SCIP_DECL_EXPRINTEGRALITY
1082  */
1084  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1085  SCIP_SET* set, /**< global SCIP settings */
1086  SCIP_EXPR* expr, /**< expression to check integrality for */
1087  SCIP_Bool* isintegral /**< buffer to store whether expression is integral */
1088  )
1089 {
1090  assert(exprhdlr != NULL);
1091  assert(set != NULL);
1092  assert(expr != NULL);
1093  assert(expr->exprhdlr == exprhdlr);
1094  assert(isintegral != NULL);
1095 
1096  *isintegral = FALSE;
1097 
1098  /* check whether the expression handler implements the monotonicity callback */
1099  if( exprhdlr->integrality != NULL )
1100  {
1101  SCIP_CALL( exprhdlr->integrality(set->scip, expr, isintegral) );
1102  }
1103 
1104  return SCIP_OKAY;
1105 }
1106 
1107 /** calls the hash callback of an expression handler
1108  *
1109  * The method hashes an expression by taking the hashes of its children into account.
1110  *
1111  * @see SCIP_DECL_EXPRHASH
1112  */
1114  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1115  SCIP_SET* set, /**< global SCIP settings */
1116  SCIP_EXPR* expr, /**< expression to be hashed */
1117  unsigned int* hashkey, /**< buffer to store the hash value */
1118  unsigned int* childrenhashes /**< array with hash values of children */
1119  )
1120 {
1121  assert(exprhdlr != NULL);
1122  assert(set != NULL);
1123  assert(expr != NULL);
1124  assert(expr->exprhdlr == exprhdlr);
1125  assert(hashkey != NULL);
1126  assert(childrenhashes != NULL || expr->nchildren == 0);
1127 
1128  if( expr->exprhdlr->hash != NULL )
1129  {
1130  SCIP_CALL( expr->exprhdlr->hash(set->scip, expr, hashkey, childrenhashes) );
1131  }
1132  else
1133  {
1134  int i;
1135 
1136  /* compute initial hash from expression handler name if callback is not implemented
1137  * this can lead to more collisions and thus a larger number of expensive expression compare calls
1138  */
1139  *hashkey = 0;
1140  for( i = 0; expr->exprhdlr->name[i] != '\0'; i++ )
1141  *hashkey += (unsigned int) expr->exprhdlr->name[i]; /*lint !e571*/
1142 
1143  *hashkey = SCIPcalcFibHash((SCIP_Real)*hashkey);
1144 
1145  /* now make use of the hashkeys of the children */
1146  for( i = 0; i < expr->nchildren; ++i )
1147  *hashkey ^= childrenhashes[i];
1148  }
1149 
1150  return SCIP_OKAY;
1151 }
1152 
1153 /** calls the compare callback of an expression handler
1154  *
1155  * The method receives two expressions, expr1 and expr2, and returns
1156  * - -1 if expr1 < expr2,
1157  * - 0 if expr1 = expr2,
1158  * - 1 if expr1 > expr2.
1159  *
1160  * @see SCIP_DECL_EXPRCOMPARE
1161  */
1163  SCIP_SET* set, /**< global SCIP settings */
1164  SCIP_EXPR* expr1, /**< first expression in comparison */
1165  SCIP_EXPR* expr2 /**< second expression in comparison */
1166  )
1167 {
1168  int i;
1169 
1170  assert(expr1 != NULL);
1171  assert(expr2 != NULL);
1172  assert(expr1->exprhdlr == expr2->exprhdlr);
1173 
1174  if( expr1->exprhdlr->compare != NULL )
1175  {
1176  /* enforces OR1-OR4 */
1177  return expr1->exprhdlr->compare(set->scip, expr1, expr2);
1178  }
1179 
1180  /* enforces OR5: default comparison method of expressions of the same type:
1181  * expr1 < expr2 if and only if expr1_i = expr2_i for all i < k and expr1_k < expr2_k.
1182  * if there is no such k, use number of children to decide
1183  * if number of children is equal, both expressions are equal
1184  * @note: Warning, this method doesn't know about expression data. So if your expressions have special data,
1185  * you must implement the compare callback: SCIP_DECL_EXPRCOMPARE
1186  */
1187  for( i = 0; i < expr1->nchildren && i < expr2->nchildren; ++i )
1188  {
1189  int compareresult = SCIPexprCompare(set, expr1->children[i], expr2->children[i]);
1190  if( compareresult != 0 )
1191  return compareresult;
1192  }
1193 
1194  return expr1->nchildren == expr2->nchildren ? 0 : expr1->nchildren < expr2->nchildren ? -1 : 1;
1195 }
1196 
1197 /** calls the evaluation callback of an expression handler
1198  *
1199  * The method evaluates an expression by taking the values of its children into account.
1200  *
1201  * Further, allows to evaluate w.r.t. given expression and children values instead of those stored in children expressions.
1202  *
1203  * @see SCIP_DECL_EXPREVAL
1204  */
1206  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1207  SCIP_SET* set, /**< global SCIP settings */
1208  BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */
1209  SCIP_EXPR* expr, /**< expression to be evaluated */
1210  SCIP_Real* val, /**< buffer to store value of expression */
1211  SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */
1212  SCIP_SOL* sol /**< solution that is evaluated (can be NULL) */
1213  )
1214 {
1215  SCIP_Real* origvals = NULL;
1216 
1217  assert(exprhdlr != NULL);
1218  assert(set != NULL);
1219  assert(expr != NULL);
1220  assert(expr->exprhdlr == exprhdlr);
1221  assert(exprhdlr->eval != NULL);
1222  assert(val != NULL);
1223 
1224  /* temporarily overwrite the evalvalue in all children with values from childrenvals */
1225  if( childrenvals != NULL && expr->nchildren > 0 )
1226  {
1227  int c;
1228 
1229  assert(bufmem != NULL);
1230 
1231  SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &origvals, expr->nchildren) );
1232 
1233  for( c = 0; c < expr->nchildren; ++c )
1234  {
1235  origvals[c] = expr->children[c]->evalvalue;
1236  expr->children[c]->evalvalue = childrenvals[c];
1237  }
1238  }
1239 
1240  /* call expression eval callback */
1241  SCIP_CALL( exprhdlr->eval(set->scip, expr, val, sol) );
1242 
1243  /* if there was some evaluation error (e.g., overflow) that hasn't been caught yet, then do so now */
1244  if( !SCIPisFinite(*val) )
1245  *val = SCIP_INVALID;
1246 
1247  /* restore original evalvalues in children */
1248  if( origvals != NULL )
1249  {
1250  int c;
1251  for( c = 0; c < expr->nchildren; ++c )
1252  expr->children[c]->evalvalue = origvals[c];
1253 
1254  BMSfreeBufferMemoryArray(bufmem, &origvals);
1255  }
1256 
1257  return SCIP_OKAY;
1258 }
1259 
1260 /** calls the backward derivative evaluation callback of an expression handler
1261  *
1262  * The method should compute the partial derivative of expr w.r.t its child at childidx.
1263  * That is, it returns
1264  * \f[
1265  * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}}
1266  * \f]
1267  *
1268  * Further, allows to differentiate w.r.t. given expression and children values instead of those stored in children expressions.
1269  *
1270  * @see SCIP_DECL_EXPRBWDIFF
1271  */
1273  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1274  SCIP_SET* set, /**< global SCIP settings */
1275  BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */
1276  SCIP_EXPR* expr, /**< expression to be differentiated */
1277  int childidx, /**< index of the child */
1278  SCIP_Real* derivative, /**< buffer to store the partial derivative w.r.t. the i-th children */
1279  SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */
1280  SCIP_Real exprval /**< value for expression, used only if childrenvals is not NULL */
1281  )
1282 {
1283  SCIP_Real* origchildrenvals;
1284  SCIP_Real origexprval = SCIP_INVALID;
1285  int c;
1286 
1287  assert(exprhdlr != NULL);
1288  assert(set != NULL);
1289  assert(expr != NULL);
1290  assert(expr->exprhdlr == exprhdlr);
1291  assert(derivative != NULL);
1292 
1293  if( exprhdlr->bwdiff == NULL )
1294  {
1295  *derivative = SCIP_INVALID;
1296  return SCIP_OKAY;
1297  }
1298 
1299  if( childrenvals != NULL )
1300  {
1301  /* temporarily overwrite the evalvalue in all children and expr with values from childrenvals and exprval, resp. */
1302  if( expr->nchildren > 0 )
1303  {
1304  assert(bufmem != NULL);
1305  SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &origchildrenvals, expr->nchildren) );
1306 
1307  for( c = 0; c < expr->nchildren; ++c )
1308  {
1309  origchildrenvals[c] = expr->children[c]->evalvalue;
1310  expr->children[c]->evalvalue = childrenvals[c];
1311  }
1312  }
1313 
1314  origexprval = expr->evalvalue;
1315  expr->evalvalue = exprval;
1316  }
1317 
1318  SCIP_CALL( expr->exprhdlr->bwdiff(set->scip, expr, childidx, derivative) );
1319 
1320  /* if there was some evaluation error (e.g., overflow) that hasn't been caught yet, then do so now */
1321  if( !SCIPisFinite(*derivative) )
1322  *derivative = SCIP_INVALID;
1323 
1324  /* restore original evalvalues in children */
1325  if( childrenvals != NULL )
1326  {
1327  if( expr->nchildren > 0 )
1328  {
1329  for( c = 0; c < expr->nchildren; ++c )
1330  expr->children[c]->evalvalue = origchildrenvals[c]; /*lint !e644*/
1331 
1332  BMSfreeBufferMemoryArray(bufmem, &origchildrenvals);
1333  }
1334 
1335  expr->evalvalue = origexprval;
1336  }
1337 
1338  return SCIP_OKAY;
1339 }
1340 
1341 /** calls the forward differentiation callback of an expression handler
1342  *
1343  * @see SCIP_DECL_EXPRFWDIFF
1344  */
1346  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1347  SCIP_SET* set, /**< global SCIP settings */
1348  SCIP_EXPR* expr, /**< expression to be differentiated */
1349  SCIP_Real* dot, /**< buffer to store derivative value */
1350  SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions) */
1351  )
1352 {
1353  assert(exprhdlr != NULL);
1354  assert(set != NULL);
1355  assert(expr != NULL);
1356  assert(expr->exprhdlr == exprhdlr);
1357  assert(dot != NULL);
1358 
1359  if( exprhdlr->fwdiff == NULL )
1360  {
1361  *dot = SCIP_INVALID;
1362  return SCIP_OKAY;
1363  }
1364 
1365  SCIP_CALL( exprhdlr->fwdiff(set->scip, expr, dot, direction) );
1366 
1367  /* if there was some evaluation error (e.g., overflow) that hasn't been caught yet, then do so now */
1368  if( !SCIPisFinite(*dot) )
1369  *dot = SCIP_INVALID;
1370 
1371  return SCIP_OKAY;
1372 }
1373 
1374 /** calls the evaluation and forward-differentiation callback of an expression handler
1375  *
1376  * The method evaluates an expression by taking the values of its children into account.
1377  * The method differentiates an expression by taking the values and directional derivatives of its children into account.
1378  *
1379  * Further, allows to evaluate and differentiate w.r.t. given values for children instead of those stored in children expressions.
1380  *
1381  * It probably doesn't make sense to call this function for a variable-expression if sol and/or direction are not given.
1382  *
1383  * @see SCIP_DECL_EXPREVAL
1384  * @see SCIP_DECL_EXPRFWDIFF
1385  */
1387  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1388  SCIP_SET* set, /**< global SCIP settings */
1389  BMS_BUFMEM* bufmem, /**< buffer memory, can be NULL if childrenvals is NULL */
1390  SCIP_EXPR* expr, /**< expression to be evaluated */
1391  SCIP_Real* val, /**< buffer to store value of expression */
1392  SCIP_Real* dot, /**< buffer to store derivative value */
1393  SCIP_Real* childrenvals, /**< values for children, or NULL if values stored in children should be used */
1394  SCIP_SOL* sol, /**< solution that is evaluated (can be NULL) */
1395  SCIP_Real* childrendirs, /**< directional derivatives for children, or NULL if dot-values stored in children should be used */
1396  SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions, can be NULL if childrendirs is given) */
1397  )
1398 {
1399  SCIP_Real origval;
1400  SCIP_Real* origvals = NULL;
1401  SCIP_Real* origdots = NULL;
1402 
1403  assert(exprhdlr != NULL);
1404  assert(set != NULL);
1405  assert(expr != NULL);
1406  assert(expr->exprhdlr == exprhdlr);
1407  assert(exprhdlr->eval != NULL);
1408  assert(val != NULL);
1409  assert(dot != NULL);
1410 
1411  /* temporarily overwrite the evalvalue in all children with values from childrenvals */
1412  if( childrenvals != NULL && expr->nchildren > 0 )
1413  {
1414  int c;
1415 
1416  assert(bufmem != NULL);
1417 
1418  SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &origvals, expr->nchildren) );
1419 
1420  for( c = 0; c < expr->nchildren; ++c )
1421  {
1422  origvals[c] = expr->children[c]->evalvalue;
1423  expr->children[c]->evalvalue = childrenvals[c];
1424  }
1425  }
1426 
1427  /* temporarily overwrite the dot in all children with values from childrendirs */
1428  if( childrendirs != NULL && expr->nchildren > 0 )
1429  {
1430  int c;
1431 
1432  assert(bufmem != NULL);
1433 
1434  SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &origdots, expr->nchildren) );
1435 
1436  for( c = 0; c < expr->nchildren; ++c )
1437  {
1438  origdots[c] = expr->children[c]->dot;
1439  expr->children[c]->dot = childrendirs[c];
1440  }
1441  }
1442 
1443  /* remember original value */
1444  origval = expr->evalvalue;
1445 
1446  /* call expression eval callback */
1447  SCIP_CALL( exprhdlr->eval(set->scip, expr, val, sol) );
1448 
1449  /* if there was some evaluation error (e.g., overflow) that hasn't been caught yet, then do so now */
1450  if( !SCIPisFinite(*val) )
1451  *val = SCIP_INVALID;
1452 
1453  /* temporarily overwrite evalvalue of expr, since some exprhdlr (e.g., product) access this value in fwdiff */
1454  expr->evalvalue = *val;
1455 
1456  /* call forward-differentiation callback (if available) */
1457  SCIP_CALL( SCIPexprhdlrFwDiffExpr(exprhdlr, set, expr, dot, direction) );
1458 
1459  /* restore original value */
1460  expr->evalvalue = origval;
1461 
1462  /* restore original dots in children */
1463  if( origdots != NULL )
1464  {
1465  int c;
1466  for( c = 0; c < expr->nchildren; ++c )
1467  expr->children[c]->dot = origdots[c];
1468 
1469  BMSfreeBufferMemoryArray(bufmem, &origdots);
1470  }
1471 
1472  /* restore original evalvalues in children */
1473  if( origvals != NULL )
1474  {
1475  int c;
1476  for( c = 0; c < expr->nchildren; ++c )
1477  expr->children[c]->evalvalue = origvals[c];
1478 
1479  BMSfreeBufferMemoryArray(bufmem, &origvals);
1480  }
1481 
1482  return SCIP_OKAY;
1483 }
1484 
1485 /** calls the evaluation callback for Hessian directions (backward over forward) of an expression handler
1486  *
1487  * @see SCIP_DECL_EXPRBWFWDIFF
1488  */
1490  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1491  SCIP_SET* set, /**< global SCIP settings */
1492  SCIP_EXPR* expr, /**< expression to be differentiated */
1493  int childidx, /**< index of the child */
1494  SCIP_Real* bardot, /**< buffer to store derivative value */
1495  SCIP_SOL* direction /**< direction of the derivative (useful only for var expressions) */
1496  )
1497 {
1498  assert(exprhdlr != NULL);
1499  assert(set != NULL);
1500  assert(expr != NULL);
1501  assert(expr->exprhdlr == exprhdlr);
1502  assert(childidx >= 0);
1503  assert(childidx < expr->nchildren);
1504  assert(bardot != NULL);
1505 
1506  if( exprhdlr->bwfwdiff == NULL )
1507  {
1508  *bardot = SCIP_INVALID;
1509  return SCIP_OKAY;
1510  }
1511 
1512  SCIP_CALL( expr->exprhdlr->bwfwdiff(set->scip, expr, childidx, bardot, direction) );
1513 
1514  /* if there was some evaluation error (e.g., overflow) that hasn't been caught yet, then do so now */
1515  if( !SCIPisFinite(*bardot) )
1516  *bardot = SCIP_INVALID;
1517 
1518  return SCIP_OKAY;
1519 }
1520 
1521 /** calls the interval evaluation callback of an expression handler
1522  *
1523  * @see SCIP_DECL_EXPRINTEVAL
1524  */
1526  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1527  SCIP_SET* set, /**< global SCIP settings */
1528  SCIP_EXPR* expr, /**< expression to be evaluated */
1529  SCIP_INTERVAL* interval, /**< buffer where to store interval */
1530  SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), /**< callback to be called when interval-evaluating a variable */
1531  void* intevalvardata /**< data to be passed to intevalvar callback */
1532  )
1533 {
1534  assert(exprhdlr != NULL);
1535  assert(set != NULL);
1536  assert(expr != NULL);
1537  assert(expr->exprhdlr == exprhdlr);
1538  assert(interval != NULL);
1539 
1540  if( exprhdlr->inteval != NULL )
1541  {
1542  SCIPclockStart(exprhdlr->intevaltime, set);
1543  SCIP_CALL( exprhdlr->inteval(set->scip, expr, interval, intevalvar, intevalvardata) );
1544  SCIPclockStop(exprhdlr->intevaltime, set);
1545 
1546  ++exprhdlr->nintevalcalls;
1547  }
1548 
1549  return SCIP_OKAY;
1550 }
1551 
1552 /** calls the estimator callback of an expression handler
1553  *
1554  * @see SCIP_DECL_EXPRESTIMATE
1555  */
1557  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1558  SCIP_SET* set, /**< global SCIP settings */
1559  SCIP_EXPR* expr, /**< expression to be estimated */
1560  SCIP_INTERVAL* localbounds, /**< current bounds for children */
1561  SCIP_INTERVAL* globalbounds, /**< global bounds for children */
1562  SCIP_Real* refpoint, /**< children values for the reference point where to estimate */
1563  SCIP_Bool overestimate, /**< whether the expression needs to be over- or underestimated */
1564  SCIP_Real targetvalue, /**< a value that the estimator shall exceed, can be +/-infinity */
1565  SCIP_Real* coefs, /**< array to store coefficients of estimator */
1566  SCIP_Real* constant, /**< buffer to store constant part of estimator */
1567  SCIP_Bool* islocal, /**< buffer to store whether estimator is valid locally only */
1568  SCIP_Bool* success, /**< buffer to indicate whether an estimator could be computed */
1569  SCIP_Bool* branchcand /**< array to indicate which children (not) to consider for branching */
1570  )
1571 {
1572  assert(exprhdlr != NULL);
1573  assert(set != NULL);
1574  assert(expr != NULL);
1575  assert(expr->exprhdlr == exprhdlr);
1576  assert(coefs != NULL);
1577  assert(islocal != NULL);
1578  assert(success != NULL);
1579 
1580  *success = FALSE;
1581 
1582  if( exprhdlr->estimate != NULL )
1583  {
1584  SCIPclockStart(exprhdlr->estimatetime, set);
1585  SCIP_CALL( exprhdlr->estimate(set->scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue,
1586  coefs, constant, islocal, success, branchcand) );
1587  SCIPclockStop(exprhdlr->estimatetime, set);
1588 
1589  /* update statistics */
1590  ++exprhdlr->nestimatecalls;
1591  }
1592 
1593  return SCIP_OKAY;
1594 }
1595 
1596 /** calls the intitial estimators callback of an expression handler
1597  *
1598  * @see SCIP_DECL_EXPRINITESTIMATES
1599  */
1601  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1602  SCIP_SET* set, /**< global SCIP settings */
1603  SCIP_EXPR* expr, /**< expression to be estimated */
1604  SCIP_INTERVAL* bounds, /**< bounds for children */
1605  SCIP_Bool overestimate, /**< whether the expression shall be overestimated or underestimated */
1606  SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store coefficients of computed estimators */
1607  SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], /**< buffer to store constant of computed estimators */
1608  int* nreturned /**< buffer to store number of estimators that have been computed */
1609  )
1610 {
1611  assert(exprhdlr != NULL);
1612  assert(set != NULL);
1613  assert(expr != NULL);
1614  assert(expr->exprhdlr == exprhdlr);
1615  assert(nreturned != NULL);
1616 
1617  *nreturned = 0;
1618 
1619  if( exprhdlr->initestimates )
1620  {
1621  SCIPclockStart(expr->exprhdlr->estimatetime, set);
1622  SCIP_CALL( exprhdlr->initestimates(set->scip, expr, bounds, overestimate, coefs, constant, nreturned) );
1623  SCIPclockStop(expr->exprhdlr->estimatetime, set);
1624 
1625  ++exprhdlr->nestimatecalls;
1626  }
1627 
1628  return SCIP_OKAY;
1629 }
1630 
1631 /** calls the simplification callback of an expression handler
1632  *
1633  * @see SCIP_DECL_EXPRSIMPLIFY
1634  */
1636  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1637  SCIP_SET* set, /**< global SCIP settings */
1638  SCIP_EXPR* expr, /**< expression to simplify */
1639  SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
1640  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1641  void* ownercreatedata /**< data to pass to ownercreate */
1642  )
1643 {
1644  assert(exprhdlr != NULL);
1645  assert(set != NULL);
1646  assert(expr != NULL);
1647  assert(expr->exprhdlr == exprhdlr);
1648  assert(simplifiedexpr != NULL);
1649 
1650  if( exprhdlr->simplify != NULL )
1651  {
1652  SCIPclockStart(expr->exprhdlr->simplifytime, set);
1653  SCIP_CALL( exprhdlr->simplify(set->scip, expr, simplifiedexpr, ownercreate, ownercreatedata) );
1654  SCIPclockStop(expr->exprhdlr->simplifytime, set);
1655 
1656  /* update statistics */
1657  ++exprhdlr->nsimplifycalls;
1658  if( expr != *simplifiedexpr )
1659  ++exprhdlr->nsimplified;
1660  }
1661  else
1662  {
1663  *simplifiedexpr = expr;
1664 
1665  /* if an expression handler doesn't implement simplify, we assume that it is already simplified
1666  * we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created
1667  */
1668  SCIPexprCapture(expr);
1669  }
1670 
1671  return SCIP_OKAY;
1672 }
1673 
1674 /** calls the reverse propagation callback of an expression handler
1675  *
1676  * The method propagates given bounds over the children of an expression.
1677  *
1678  * @see SCIP_DECL_EXPRREVERSEPROP
1679  */
1681  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1682  SCIP_SET* set, /**< global SCIP settings */
1683  SCIP_EXPR* expr, /**< expression to propagate */
1684  SCIP_INTERVAL bounds, /**< the bounds on the expression that should be propagated */
1685  SCIP_INTERVAL* childrenbounds, /**< array to store computed bounds for children, initialized with current activity */
1686  SCIP_Bool* infeasible /**< buffer to store whether a children bounds were propagated to an empty interval */
1687  )
1688 {
1689  assert(exprhdlr != NULL);
1690  assert(set != NULL);
1691  assert(expr != NULL);
1692  assert(expr->exprhdlr == exprhdlr);
1693  assert(childrenbounds != NULL || expr->nchildren == 0);
1694  assert(infeasible != NULL);
1695 
1696  *infeasible = FALSE;
1697 
1698  if( exprhdlr->reverseprop != NULL )
1699  {
1700  SCIPclockStart(exprhdlr->proptime, set);
1701  SCIP_CALL( exprhdlr->reverseprop(set->scip, expr, bounds, childrenbounds, infeasible) );
1702  SCIPclockStop(exprhdlr->proptime, set);
1703 
1704  /* update statistics */
1705  if( *infeasible )
1706  ++expr->exprhdlr->ncutoffs;
1707  ++expr->exprhdlr->npropcalls;
1708  }
1709 
1710  return SCIP_OKAY;
1711 }
1712 
1713 /**@name Expression Methods */
1714 /**@{ */
1715 
1716 /* from expr.h */
1717 
1718 #ifdef NDEBUG
1719 #undef SCIPexprCapture
1720 #undef SCIPexprIsVar
1721 #undef SCIPexprIsValue
1722 #undef SCIPexprIsSum
1723 #undef SCIPexprIsProduct
1724 #undef SCIPexprIsPower
1725 #endif
1726 
1727 /** creates and captures an expression with given expression data and children */
1729  SCIP_SET* set, /**< global SCIP settings */
1730  BMS_BLKMEM* blkmem, /**< block memory */
1731  SCIP_EXPR** expr, /**< pointer where to store expression */
1732  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
1733  SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */
1734  int nchildren, /**< number of children */
1735  SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */
1736  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1737  void* ownercreatedata /**< data to pass to ownercreate */
1738  )
1739 {
1740  int c;
1741 
1742  assert(set != NULL);
1743  assert(blkmem != NULL);
1744  assert(expr != NULL);
1745  assert(exprhdlr != NULL);
1746  assert(children != NULL || nchildren == 0);
1747  assert(exprdata == NULL || exprhdlr->copydata != NULL); /* copydata must be available if there is expression data */
1748  assert(exprdata == NULL || exprhdlr->freedata != NULL); /* freedata must be available if there is expression data */
1749 
1750  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, expr) );
1751 
1752  (*expr)->exprhdlr = exprhdlr;
1753  (*expr)->exprdata = exprdata;
1754  (*expr)->activitytag = -1; /* to be less than initial domchgcount */
1755  (*expr)->curvature = SCIP_EXPRCURV_UNKNOWN;
1756 
1757  /* initialize activity to entire interval */
1758  SCIPintervalSetEntire(SCIP_INTERVAL_INFINITY, &(*expr)->activity);
1759 
1760  if( nchildren > 0 )
1761  {
1762  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*expr)->children, children, nchildren) );
1763  (*expr)->nchildren = nchildren;
1764  (*expr)->childrensize = nchildren;
1765 
1766  for( c = 0; c < nchildren; ++c )
1767  SCIPexprCapture((*expr)->children[c]);
1768  }
1769 
1770  SCIPexprCapture(*expr);
1771 
1772  ++exprhdlr->ncreated;
1773 
1774  /* initializes the ownerdata */
1775  if( ownercreate != NULL )
1776  {
1777  SCIP_CALL( ownercreate(set->scip, *expr, &(*expr)->ownerdata, &(*expr)->ownerfree, &(*expr)->ownerprint,
1778  &(*expr)->ownerevalactivity, ownercreatedata) );
1779  }
1780 
1781  return SCIP_OKAY;
1782 }
1783 
1784 /** appends child to the children list of expr */
1786  SCIP_SET* set, /**< global SCIP settings */
1787  BMS_BLKMEM* blkmem, /**< block memory */
1788  SCIP_EXPR* expr, /**< expression */
1789  SCIP_EXPR* child /**< expression to be appended */
1790  )
1791 {
1792  assert(set != NULL);
1793  assert(blkmem != NULL);
1794  assert(child != NULL);
1795  assert(expr->nchildren <= expr->childrensize);
1796 
1797  if( expr->nchildren == expr->childrensize )
1798  {
1799  expr->childrensize = SCIPsetCalcMemGrowSize(set, expr->nchildren+1);
1800  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &expr->children, expr->nchildren, expr->childrensize) );
1801  }
1802 
1803  expr->children[expr->nchildren] = child;
1804  ++expr->nchildren;
1805 
1806  /* capture child */
1807  SCIPexprCapture(child);
1808 
1809  return SCIP_OKAY;
1810 }
1811 
1812 /** overwrites/replaces a child of an expressions
1813  *
1814  * @note the old child is released and the newchild is captured, unless they are the same (=same pointer)
1815  */
1817  SCIP_SET* set, /**< global SCIP settings */
1818  SCIP_STAT* stat, /**< dynamic problem statistics */
1819  BMS_BLKMEM* blkmem, /**< block memory */
1820  SCIP_EXPR* expr, /**< expression where a child is going to be replaced */
1821  int childidx, /**< index of child being replaced */
1822  SCIP_EXPR* newchild /**< the new child */
1823  )
1824 {
1825  assert(set != NULL);
1826  assert(blkmem != NULL);
1827  assert(expr != NULL);
1828  assert(newchild != NULL);
1829  assert(childidx >= 0);
1830  assert(childidx < expr->nchildren);
1831 
1832  /* do nothing if child is not changing */
1833  if( newchild == expr->children[childidx] )
1834  return SCIP_OKAY;
1835 
1836  /* capture new child (do this before releasing the old child in case there are equal */
1837  SCIPexprCapture(newchild);
1838 
1839  SCIP_CALL( SCIPexprRelease(set, stat, blkmem, &(expr->children[childidx])) );
1840  expr->children[childidx] = newchild;
1841 
1842  return SCIP_OKAY;
1843 }
1844 
1845 /** remove all children of expr */
1847  SCIP_SET* set, /**< global SCIP settings */
1848  SCIP_STAT* stat, /**< dynamic problem statistics */
1849  BMS_BLKMEM* blkmem, /**< block memory */
1850  SCIP_EXPR* expr /**< expression */
1851  )
1852 {
1853  int c;
1854 
1855  assert(set != NULL);
1856  assert(blkmem != NULL);
1857  assert(expr != NULL);
1858 
1859  for( c = 0; c < expr->nchildren; ++c )
1860  {
1861  assert(expr->children[c] != NULL);
1862  SCIP_CALL( SCIPexprRelease(set, stat, blkmem, &(expr->children[c])) );
1863  }
1864 
1865  expr->nchildren = 0;
1866 
1867  return SCIP_OKAY;
1868 }
1869 
1870 /** copies an expression including subexpressions
1871  *
1872  * @note If copying fails due to an expression handler not being available in the targetscip, then *targetexpr will be set to NULL.
1873  *
1874  * For all or some expressions, a mapping to an existing expression can be specified via the mapexpr callback.
1875  * The mapped expression (including its children) will not be copied in this case and its ownerdata will not be touched.
1876  * If, however, the mapexpr callback returns NULL for the targetexpr, then the expr will be copied in the usual way.
1877  */
1879  SCIP_SET* set, /**< global SCIP settings */
1880  SCIP_STAT* stat, /**< dynamic problem statistics */
1881  BMS_BLKMEM* blkmem, /**< block memory */
1882  SCIP_SET* targetset, /**< global SCIP settings data structure where target expression will live */
1883  SCIP_STAT* targetstat, /**< dynamic problem statistics in target SCIP */
1884  BMS_BLKMEM* targetblkmem, /**< block memory in target SCIP */
1885  SCIP_EXPR* sourceexpr, /**< expression to be copied */
1886  SCIP_EXPR** targetexpr, /**< buffer to store pointer to copy of source expression */
1887  SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */
1888  void* mapexprdata, /**< data of expression mapping function */
1889  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1890  void* ownercreatedata /**< data to pass to ownercreate */
1891  )
1892 {
1893  SCIP_EXPRITER* it;
1894  SCIP_EXPRITER_USERDATA expriteruserdata;
1895  SCIP_EXPR* expr;
1896  SCIP* sourcescip = set->scip; /* SCIP data structure corresponding to source expression */
1897  SCIP* targetscip = targetset->scip; /* SCIP data structure where target expression will live */
1898 
1899  assert(set != NULL);
1900  assert(stat != NULL);
1901  assert(blkmem != NULL);
1902  assert(targetset != NULL);
1903  assert(sourceexpr != NULL);
1904  assert(targetexpr != NULL);
1905  assert(sourcescip != NULL);
1906  assert(targetscip != NULL);
1907 
1908  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
1909  SCIP_CALL( SCIPexpriterInit(it, sourceexpr, SCIP_EXPRITER_DFS, TRUE) ); /*TODO use FALSE, i.e., don't duplicate common subexpr? */
1911 
1912  expr = sourceexpr;
1913  while( !SCIPexpriterIsEnd(it) )
1914  {
1915  switch( SCIPexpriterGetStageDFS(it) )
1916  {
1918  {
1919  /* create expr that will hold the copy */
1920  SCIP_EXPRHDLR* targetexprhdlr;
1921  SCIP_EXPRDATA* targetexprdata;
1922  SCIP_EXPR* exprcopy = NULL;
1923 
1924  if( mapexpr != NULL )
1925  {
1926  SCIP_CALL( mapexpr(targetscip, &exprcopy, sourcescip, expr, ownercreate, ownercreatedata, mapexprdata) );
1927  if( exprcopy != NULL )
1928  {
1929  /* map callback gave us an expression to use for the copy */
1930  /* store targetexpr */
1931  expriteruserdata.ptrval = exprcopy;
1932  SCIPexpriterSetCurrentUserData(it, expriteruserdata);
1933 
1934  /* skip subexpression (assume that exprcopy is a complete copy) and continue */
1935  expr = SCIPexpriterSkipDFS(it);
1936  continue;
1937  }
1938  }
1939 
1940  /* get the exprhdlr of the target scip */
1941  if( targetscip != sourcescip )
1942  {
1943  targetexprhdlr = SCIPsetFindExprhdlr(targetset, expr->exprhdlr->name);
1944 
1945  if( targetexprhdlr == NULL )
1946  {
1947  /* expression handler not in target scip (probably did not have a copy callback) -> abort */
1948  expriteruserdata.ptrval = NULL;
1949  SCIPexpriterSetCurrentUserData(it, expriteruserdata);
1950 
1951  expr = SCIPexpriterSkipDFS(it);
1952  continue;
1953  }
1954  }
1955  else
1956  {
1957  targetexprhdlr = expr->exprhdlr;
1958  }
1959  assert(targetexprhdlr != NULL);
1960 
1961  /* copy expression data */
1962  if( expr->exprdata != NULL )
1963  {
1964  assert(expr->exprhdlr->copydata != NULL);
1965  SCIP_CALL( expr->exprhdlr->copydata(targetscip, targetexprhdlr, &targetexprdata, sourcescip, expr) );
1966  }
1967  else
1968  {
1969  targetexprdata = NULL;
1970  }
1971 
1972  /* create in targetexpr an expression of the same type as expr, but without children for now */
1973  SCIP_CALL( SCIPexprCreate(targetset, targetblkmem, &exprcopy, targetexprhdlr, targetexprdata, 0, NULL,
1974  ownercreate, ownercreatedata) );
1975 
1976  /* store targetexpr */
1977  expriteruserdata.ptrval = exprcopy;
1978  SCIPexpriterSetCurrentUserData(it, expriteruserdata);
1979 
1980  break;
1981  }
1982 
1984  {
1985  /* just visited child so a copy of himself should be available; append it */
1986  SCIP_EXPR* exprcopy;
1987  SCIP_EXPR* childcopy;
1988 
1990 
1991  /* get copy of child */
1993  if( childcopy == NULL )
1994  {
1995  /* abort */
1996  /* release exprcopy (should free also the already copied children) */
1997  SCIP_CALL( SCIPexprRelease(targetset, targetstat, targetblkmem, (SCIP_EXPR**)&exprcopy) );
1998 
1999  expriteruserdata.ptrval = NULL;
2000  SCIPexpriterSetCurrentUserData(it, expriteruserdata);
2001 
2002  expr = SCIPexpriterSkipDFS(it);
2003  continue;
2004  }
2005 
2006  /* append child to exprcopy */
2007  SCIP_CALL( SCIPexprAppendChild(targetset, targetblkmem, exprcopy, childcopy) );
2008 
2009  /* release childcopy (still captured by exprcopy) */
2010  SCIP_CALL( SCIPexprRelease(targetset, targetstat, targetblkmem, &childcopy) );
2011 
2012  break;
2013  }
2014 
2015  default:
2016  /* we should never be called in this stage */
2017  SCIPABORT();
2018  break;
2019  }
2020 
2021  expr = SCIPexpriterGetNext(it);
2022  }
2023 
2024  /* the target expression should be stored in the userdata of the sourceexpr (can be NULL if aborted) */
2025  *targetexpr = (SCIP_EXPR*)SCIPexpriterGetExprUserData(it, sourceexpr).ptrval;
2026 
2027  SCIPexpriterFree(&it);
2028 
2029  return SCIP_OKAY;
2030 }
2031 
2032 /** duplicates the given expression without its children */
2034  SCIP_SET* set, /**< global SCIP settings */
2035  BMS_BLKMEM* blkmem, /**< block memory */
2036  SCIP_EXPR* expr, /**< original expression */
2037  SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */
2038  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
2039  void* ownercreatedata /**< data to pass to ownercreate */
2040  )
2041 {
2042  SCIP_EXPRDATA* exprdatacopy = NULL;
2043 
2044  assert(set != NULL);
2045  assert(blkmem != NULL);
2046  assert(expr != NULL);
2047  assert(copyexpr != NULL);
2048 
2049  /* copy expression data */
2050  if( expr->exprdata != NULL )
2051  {
2052  assert(expr->exprhdlr->copydata != NULL);
2053  SCIP_CALL( expr->exprhdlr->copydata(set->scip, expr->exprhdlr, &exprdatacopy, set->scip, expr) );
2054  }
2055 
2056  /* create expression with same handler and copied data, but without children */
2057  SCIP_CALL( SCIPexprCreate(set, blkmem, copyexpr, expr->exprhdlr, exprdatacopy, 0, NULL, ownercreate,
2058  ownercreatedata) );
2059 
2060  return SCIP_OKAY;
2061 }
2062 
2063 /** captures an expression (increments usage count) */
2065  SCIP_EXPR* expr /**< expression */
2066  )
2067 {
2068  assert(expr != NULL);
2069 
2070  ++expr->nuses;
2071 }
2072 
2073 /** releases an expression (decrements usage count and possibly frees expression) */
2075  SCIP_SET* set, /**< global SCIP settings */
2076  SCIP_STAT* stat, /**< dynamic problem statistics */
2077  BMS_BLKMEM* blkmem, /**< block memory */
2078  SCIP_EXPR** rootexpr /**< pointer to expression */
2079  )
2080 {
2081  SCIP_EXPRITER* it;
2082  SCIP_EXPR* expr;
2083 
2084  assert(rootexpr != NULL);
2085  assert(*rootexpr != NULL);
2086  assert((*rootexpr)->nuses > 0);
2087 
2088  if( (*rootexpr)->nuses > 1 )
2089  {
2090  --(*rootexpr)->nuses;
2091  *rootexpr = NULL;
2092 
2093  return SCIP_OKAY;
2094  }
2095 
2096  /* handle the root expr separately: free ownerdata, quaddata, and exprdata first */
2097 
2098  /* call ownerfree callback, if given
2099  * we intentially call this also if ownerdata is NULL, so owner can be notified without storing data
2100  */
2101  if( (*rootexpr)->ownerfree != NULL )
2102  {
2103  SCIP_CALL( (*rootexpr)->ownerfree(set->scip, *rootexpr, &(*rootexpr)->ownerdata) );
2104  assert((*rootexpr)->ownerdata == NULL);
2105  }
2106 
2107  /* free quadratic info */
2108  SCIPexprFreeQuadratic(blkmem, *rootexpr);
2109 
2110  /* free expression data */
2111  if( (*rootexpr)->exprdata != NULL )
2112  {
2113  assert((*rootexpr)->exprhdlr->freedata != NULL);
2114  SCIP_CALL( (*rootexpr)->exprhdlr->freedata(set->scip, *rootexpr) );
2115  }
2116 
2117  /* now release and free children, where no longer in use */
2118  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2119  SCIP_CALL( SCIPexpriterInit(it, *rootexpr, SCIP_EXPRITER_DFS, TRUE) );
2121  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it) ; )
2122  {
2123  /* expression should be used by its parent and maybe by the iterator (only the root!)
2124  * in VISITEDCHILD we assert that expression is only used by its parent
2125  */
2126  assert(expr != NULL);
2127  assert(0 <= expr->nuses && expr->nuses <= 2);
2128 
2129  switch( SCIPexpriterGetStageDFS(it) )
2130  {
2132  {
2133  /* check whether a child needs to be visited (nuses == 1)
2134  * if not, then we still have to release it
2135  */
2136  SCIP_EXPR* child;
2137 
2138  child = SCIPexpriterGetChildExprDFS(it);
2139  if( child->nuses > 1 )
2140  {
2141  /* child is not going to be freed: just release it */
2142  SCIP_CALL( SCIPexprRelease(set, stat, blkmem, &child) );
2143  expr = SCIPexpriterSkipDFS(it);
2144  continue;
2145  }
2146 
2147  assert(child->nuses == 1);
2148 
2149  /* free child's quaddata, ownerdata, and exprdata when entering child */
2150  if( child->ownerfree != NULL )
2151  {
2152  SCIP_CALL( child->ownerfree(set->scip, child, &child->ownerdata) );
2153  assert(child->ownerdata == NULL);
2154  }
2155 
2156  /* free quadratic info */
2157  SCIPexprFreeQuadratic(blkmem, child);
2158 
2159  /* free expression data */
2160  if( child->exprdata != NULL )
2161  {
2162  assert(child->exprhdlr->freedata != NULL);
2163  SCIP_CALL( child->exprhdlr->freedata(set->scip, child) );
2164  assert(child->exprdata == NULL);
2165  }
2166 
2167  break;
2168  }
2169 
2171  {
2172  /* free child after visiting it */
2173  SCIP_EXPR* child;
2174 
2175  child = SCIPexpriterGetChildExprDFS(it);
2176  /* child should only be used by its parent */
2177  assert(child->nuses == 1);
2178 
2179  /* child should have no data associated */
2180  assert(child->exprdata == NULL);
2181 
2182  /* free child expression */
2183  SCIP_CALL( freeExpr(blkmem, &child) );
2185 
2186  break;
2187  }
2188 
2189  default:
2190  SCIPABORT(); /* we should never be called in this stage */
2191  break;
2192  }
2193 
2194  expr = SCIPexpriterGetNext(it);
2195  }
2196 
2197  SCIPexpriterFree(&it);
2198 
2199  /* handle the root expr separately: free its children and itself here */
2200  SCIP_CALL( freeExpr(blkmem, rootexpr) );
2201 
2202  return SCIP_OKAY;
2203 }
2204 
2205 /** returns whether an expression is a variable expression */
2207  SCIP_SET* set, /**< global SCIP settings */
2208  SCIP_EXPR* expr /**< expression */
2209  )
2210 {
2211  assert(set != NULL);
2212  assert(expr != NULL);
2213 
2214  return expr->exprhdlr == set->exprhdlrvar;
2215 }
2216 
2217 /** returns whether an expression is a value expression */
2219  SCIP_SET* set, /**< global SCIP settings */
2220  SCIP_EXPR* expr /**< expression */
2221  )
2222 {
2223  assert(set != NULL);
2224  assert(expr != NULL);
2225 
2226  return expr->exprhdlr == set->exprhdlrval;
2227 }
2228 
2229 /** returns whether an expression is a sum expression */
2231  SCIP_SET* set, /**< global SCIP settings */
2232  SCIP_EXPR* expr /**< expression */
2233  )
2234 {
2235  assert(set != NULL);
2236  assert(expr != NULL);
2237 
2238  return expr->exprhdlr == set->exprhdlrsum;
2239 }
2240 
2241 /** returns whether an expression is a product expression */
2243  SCIP_SET* set, /**< global SCIP settings */
2244  SCIP_EXPR* expr /**< expression */
2245  )
2246 {
2247  assert(set != NULL);
2248  assert(expr != NULL);
2249 
2250  return expr->exprhdlr == set->exprhdlrproduct;
2251 }
2252 
2253 /** returns whether an expression is a power expression */
2255  SCIP_SET* set, /**< global SCIP settings */
2256  SCIP_EXPR* expr /**< expression */
2257  )
2258 {
2259  assert(set != NULL);
2260  assert(expr != NULL);
2261 
2262  return expr->exprhdlr == set->exprhdlrpow;
2263 }
2264 
2265 /** print an expression as info-message */
2267  SCIP_SET* set, /**< global SCIP settings */
2268  SCIP_STAT* stat, /**< dynamic problem statistics */
2269  BMS_BLKMEM* blkmem, /**< block memory */
2270  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2271  FILE* file, /**< file to print to, or NULL for stdout */
2272  SCIP_EXPR* expr /**< expression to be printed */
2273  )
2274 {
2275  SCIP_EXPRITER* it;
2276  SCIP_EXPRITER_STAGE stage;
2277  int currentchild;
2278  unsigned int parentprecedence;
2279 
2280  assert(set != NULL);
2281  assert(blkmem != NULL);
2282  assert(expr != NULL);
2283 
2284  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2287 
2288  while( !SCIPexpriterIsEnd(it) )
2289  {
2290  assert(expr->exprhdlr != NULL);
2291  stage = SCIPexpriterGetStageDFS(it);
2292 
2293  if( stage == SCIP_EXPRITER_VISITEDCHILD || stage == SCIP_EXPRITER_VISITINGCHILD )
2294  currentchild = SCIPexpriterGetChildIdxDFS(it);
2295  else
2296  currentchild = -1;
2297 
2298  if( SCIPexpriterGetParentDFS(it) != NULL )
2300  else
2301  parentprecedence = 0;
2302 
2303  SCIP_CALL( SCIPexprhdlrPrintExpr(expr->exprhdlr, set, messagehdlr, expr, stage, currentchild,
2304  parentprecedence, file) );
2305 
2306  expr = SCIPexpriterGetNext(it);
2307  }
2308 
2309  SCIPexpriterFree(&it);
2310 
2311  return SCIP_OKAY;
2312 }
2313 
2314 /** initializes printing of expressions in dot format to a give FILE* pointer */
2316  SCIP_SET* set, /**< global SCIP settings */
2317  SCIP_STAT* stat, /**< dynamic problem statistics */
2318  BMS_BLKMEM* blkmem, /**< block memory */
2319  SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
2320  FILE* file, /**< file to print to, or NULL for stdout */
2321  SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
2322  )
2323 {
2324  assert(set != NULL);
2325  assert(stat != NULL);
2326  assert(blkmem != NULL);
2327  assert(printdata != NULL);
2328 
2329  if( file == NULL )
2330  file = stdout;
2331 
2332  SCIP_ALLOC( BMSallocBlockMemory(blkmem, printdata) );
2333 
2334  (*printdata)->file = file;
2335  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &(*printdata)->iterator) );
2336  (*printdata)->closefile = FALSE;
2337  (*printdata)->whattoprint = whattoprint;
2338  SCIP_CALL( SCIPhashmapCreate(&(*printdata)->leaveexprs, blkmem, 100) );
2339 
2340  fputs("strict digraph exprgraph {\n", file);
2341  fputs("node [fontcolor=white, style=filled, rankdir=LR]\n", file);
2342 
2343  return SCIP_OKAY;
2344 }
2345 
2346 /** initializes printing of expressions in dot format to a file with given filename */
2348  SCIP_SET* set, /**< global SCIP settings */
2349  SCIP_STAT* stat, /**< dynamic problem statistics */
2350  BMS_BLKMEM* blkmem, /**< block memory */
2351  SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
2352  const char* filename, /**< name of file to print to */
2353  SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
2354  )
2355 {
2356  FILE* f;
2357 
2358  assert(set != NULL);
2359  assert(stat != NULL);
2360  assert(blkmem != NULL);
2361  assert(printdata != NULL);
2362  assert(filename != NULL);
2363 
2364  f = fopen(filename, "w");
2365  if( f == NULL )
2366  {
2367  SCIPerrorMessage("could not open file <%s> for writing\n", filename); /* error code would be in errno */
2368  return SCIP_FILECREATEERROR;
2369  }
2370 
2371  SCIP_CALL_FINALLY( SCIPexprPrintDotInit(set, stat, blkmem, printdata, f, whattoprint),
2372  fclose(f) );
2373  (*printdata)->closefile = TRUE;
2374 
2375  return SCIP_OKAY;
2376 } /*lint !e429*/
2377 
2378 /** main part of printing an expression in dot format */
2380  SCIP_SET* set, /**< global SCIP settings */
2381  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2382  SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */
2383  SCIP_EXPR* expr /**< expression to be printed */
2384  )
2385 {
2386  SCIP_Real color;
2387  int c;
2388 
2389  assert(set != NULL);
2390  assert(printdata != NULL);
2391  assert(expr != NULL);
2392  assert(expr->exprhdlr != NULL);
2393 
2394  SCIP_CALL( SCIPexpriterInit(printdata->iterator, expr, SCIP_EXPRITER_DFS, FALSE) );
2395 
2396  while( !SCIPexpriterIsEnd(printdata->iterator) )
2397  {
2398  /* print expression as dot node */
2399 
2400  if( expr->nchildren == 0 )
2401  {
2402  SCIP_CALL( SCIPhashmapInsert(printdata->leaveexprs, (void*)expr, NULL) );
2403  }
2404 
2405  /* make up some color from the expression type (it's name) */
2406  color = 0.0;
2407  for( c = 0; expr->exprhdlr->name[c] != '\0'; ++c )
2408  color += (tolower(expr->exprhdlr->name[c]) - 'a') / 26.0;
2409  color = SCIPsetFrac(set, color);
2410  fprintf(printdata->file, "n%p [fillcolor=\"%g,%g,%g\", label=\"", (void*)expr, color, color, color);
2411 
2412  if( printdata->whattoprint & SCIP_EXPRPRINT_EXPRHDLR )
2413  {
2414  fprintf(printdata->file, "%s\\n", expr->exprhdlr->name);
2415  }
2416 
2417  if( printdata->whattoprint & SCIP_EXPRPRINT_EXPRSTRING )
2418  {
2419  SCIP_CALL( SCIPexprhdlrPrintExpr(expr->exprhdlr, set, messagehdlr, expr, SCIP_EXPRITER_ENTEREXPR, -1, 0,
2420  printdata->file) );
2421  for( c = 0; c < expr->nchildren; ++c )
2422  {
2423  SCIP_CALL( SCIPexprhdlrPrintExpr(expr->exprhdlr, set, messagehdlr, expr, SCIP_EXPRITER_VISITINGCHILD,
2424  c, 0, printdata->file) );
2425  fprintf(printdata->file, "c%d", c);
2426  SCIP_CALL( SCIPexprhdlrPrintExpr(expr->exprhdlr, set, messagehdlr, expr, SCIP_EXPRITER_VISITEDCHILD,
2427  c, 0, printdata->file) );
2428  }
2429  SCIP_CALL( SCIPexprhdlrPrintExpr(expr->exprhdlr, set, messagehdlr, expr, SCIP_EXPRITER_LEAVEEXPR, -1, 0,
2430  printdata->file) );
2431 
2432  fputs("\\n", printdata->file);
2433  }
2434 
2435  if( printdata->whattoprint & SCIP_EXPRPRINT_NUSES )
2436  {
2437  /* print number of uses */
2438  fprintf(printdata->file, "%d uses\\n", expr->nuses);
2439  }
2440 
2441  if( printdata->whattoprint & SCIP_EXPRPRINT_OWNER )
2442  {
2443  /* print ownerdata */
2444  if( expr->ownerprint != NULL )
2445  {
2446  SCIP_CALL( expr->ownerprint(set->scip, printdata->file, expr, expr->ownerdata) );
2447  }
2448  else if( expr->ownerdata != NULL )
2449  {
2450  fprintf(printdata->file, "owner=%p\\n", (void*)expr->ownerdata);
2451  }
2452  }
2453 
2454  if( printdata->whattoprint & SCIP_EXPRPRINT_EVALVALUE )
2455  {
2456  /* print eval value */
2457  fprintf(printdata->file, "val=%g", expr->evalvalue);
2458 
2459  if( (printdata->whattoprint & SCIP_EXPRPRINT_EVALTAG) == SCIP_EXPRPRINT_EVALTAG )
2460  {
2461  /* print also eval tag */
2462  fprintf(printdata->file, " (%" SCIP_LONGINT_FORMAT ")", expr->evaltag);
2463  }
2464  fputs("\\n", printdata->file);
2465  }
2466 
2467  if( printdata->whattoprint & SCIP_EXPRPRINT_ACTIVITY )
2468  {
2469  /* print activity */
2470  fprintf(printdata->file, "[%g,%g]", expr->activity.inf, expr->activity.sup);
2471 
2472  if( (printdata->whattoprint & SCIP_EXPRPRINT_ACTIVITYTAG) == SCIP_EXPRPRINT_ACTIVITYTAG )
2473  {
2474  /* print also activity eval tag */
2475  fprintf(printdata->file, " (%" SCIP_LONGINT_FORMAT ")", expr->activitytag);
2476  }
2477  fputs("\\n", printdata->file);
2478  }
2479 
2480  fputs("\"]\n", printdata->file); /* end of label and end of node */
2481 
2482  /* add edges from expr to its children */
2483  for( c = 0; c < expr->nchildren; ++c )
2484  fprintf(printdata->file, "n%p -> n%p [label=\"c%d\"]\n", (void*)expr, (void*)expr->children[c], c);
2485 
2486  expr = SCIPexpriterGetNext(printdata->iterator);
2487  }
2488 
2489  return SCIP_OKAY;
2490 }
2491 
2492 /** finishes printing of expressions in dot format */
2494  SCIP_SET* set, /**< global SCIP settings */
2495  SCIP_STAT* stat, /**< dynamic problem statistics */
2496  BMS_BLKMEM* blkmem, /**< block memory */
2497  SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */
2498  )
2499 {
2500  SCIP_EXPR* expr;
2501  SCIP_HASHMAPENTRY* entry;
2502  FILE* file;
2503  int i;
2504 
2505  assert(set != NULL);
2506  assert(stat != NULL);
2507  assert(blkmem != NULL);
2508  assert(printdata != NULL);
2509  assert(*printdata != NULL);
2510 
2511  file = (*printdata)->file;
2512  assert(file != NULL);
2513 
2514  /* iterate through all entries of the map */
2515  fputs("{rank=same;", file);
2516  for( i = 0; i < SCIPhashmapGetNEntries((*printdata)->leaveexprs); ++i )
2517  {
2518  entry = SCIPhashmapGetEntry((*printdata)->leaveexprs, i);
2519 
2520  if( entry != NULL )
2521  {
2522  expr = (SCIP_EXPR*) SCIPhashmapEntryGetOrigin(entry);
2523  assert(expr != NULL);
2524  assert(expr->nchildren == 0);
2525 
2526  fprintf(file, " n%p", (void*)expr);
2527  }
2528  }
2529  fprintf(file, "}\n");
2530 
2531  fprintf(file, "}\n");
2532 
2533  SCIPhashmapFree(&(*printdata)->leaveexprs);
2534 
2535  SCIPexpriterFree(&(*printdata)->iterator);
2536 
2537  if( (*printdata)->closefile )
2538  fclose((*printdata)->file);
2539 
2540  BMSfreeBlockMemory(blkmem, printdata);
2541 
2542  return SCIP_OKAY;
2543 }
2544 
2545 /** prints structure of an expression a la Maple's dismantle */
2547  SCIP_SET* set, /**< global SCIP settings */
2548  SCIP_STAT* stat, /**< dynamic problem statistics */
2549  BMS_BLKMEM* blkmem, /**< block memory */
2550  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
2551  FILE* file, /**< file to print to, or NULL for stdout */
2552  SCIP_EXPR* expr /**< expression to dismantle */
2553  )
2554 {
2555  SCIP_EXPRITER* it;
2556  int depth = -1;
2557 
2558  assert(set != NULL);
2559  assert(stat != NULL);
2560  assert(blkmem != NULL);
2561  assert(messagehdlr != NULL);
2562  assert(expr != NULL);
2563 
2564  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2567 
2568  for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2569  {
2570  switch( SCIPexpriterGetStageDFS(it) )
2571  {
2573  {
2574  int nspaces;
2575 
2576  ++depth;
2577  nspaces = 3 * depth;
2578 
2579  /* use depth of expression to align output */
2580  SCIPmessageFPrintInfo(messagehdlr, file, "%*s[%s]: ", nspaces, "", expr->exprhdlr->name);
2581 
2582  if( SCIPexprIsVar(set, expr) )
2583  {
2584  SCIP_VAR* var;
2585 
2586  var = SCIPgetVarExprVar(expr);
2587  SCIPmessageFPrintInfo(messagehdlr, file, "%s in [%g, %g]", SCIPvarGetName(var), SCIPvarGetLbLocal(var),
2588  SCIPvarGetUbLocal(var));
2589  }
2590  else if( SCIPexprIsSum(set, expr) )
2591  SCIPmessageFPrintInfo(messagehdlr, file, "%g", SCIPgetConstantExprSum(expr));
2592  else if( SCIPexprIsProduct(set, expr) )
2593  SCIPmessageFPrintInfo(messagehdlr, file, "%g", SCIPgetCoefExprProduct(expr));
2594  else if( SCIPexprIsValue(set, expr) )
2595  SCIPmessageFPrintInfo(messagehdlr, file, "%g", SCIPgetValueExprValue(expr));
2596  else if( SCIPexprIsPower(set, expr) || strcmp(expr->exprhdlr->name, "signpower") == 0)
2597  SCIPmessageFPrintInfo(messagehdlr, file, "%g", SCIPgetExponentExprPow(expr));
2598 
2599  SCIPmessageFPrintInfo(messagehdlr, file, "\n");
2600 
2601  if( expr->ownerprint != NULL )
2602  {
2603  SCIPmessageFPrintInfo(messagehdlr, file, "%*s ", nspaces, "");
2604  SCIP_CALL( expr->ownerprint(set->scip, file, expr, expr->ownerdata) );
2605  }
2606 
2607  break;
2608  }
2609 
2611  {
2612  int nspaces = 3 * depth;
2613 
2614  if( SCIPexprIsSum(set, expr) )
2615  {
2616  SCIPmessageFPrintInfo(messagehdlr, file, "%*s ", nspaces, "");
2617  SCIPmessageFPrintInfo(messagehdlr, file, "[coef]: %g\n", SCIPgetCoefsExprSum(expr)[SCIPexpriterGetChildIdxDFS(it)]);
2618  }
2619 
2620  break;
2621  }
2622 
2624  {
2625  --depth;
2626  break;
2627  }
2628 
2629  default:
2630  /* shouldn't be here */
2631  SCIPABORT();
2632  break;
2633  }
2634  }
2635 
2636  SCIPexpriterFree(&it);
2637 
2638  return SCIP_OKAY;
2639 }
2640 
2641 /** evaluate an expression in a point
2642  *
2643  * Iterates over expressions to also evaluate children, if necessary.
2644  * Value can be received via SCIPexprGetEvalValue().
2645  * If an evaluation error (division by zero, ...) occurs, this value will
2646  * be set to SCIP_INVALID.
2647  *
2648  * If a nonzero \p soltag is passed, then only (sub)expressions are
2649  * reevaluated that have a different solution tag. If a soltag of 0
2650  * is passed, then subexpressions are always reevaluated.
2651  * The tag is stored together with the value and can be received via
2652  * SCIPexprGetEvalTag().
2653  */
2655  SCIP_SET* set, /**< global SCIP settings */
2656  SCIP_STAT* stat, /**< dynamic problem statistics */
2657  BMS_BLKMEM* blkmem, /**< block memory */
2658  SCIP_EXPR* expr, /**< expression to be evaluated */
2659  SCIP_SOL* sol, /**< solution to be evaluated */
2660  SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
2661  )
2662 {
2663  SCIP_EXPRITER* it;
2664 
2665  assert(set != NULL);
2666  assert(stat != NULL);
2667  assert(blkmem != NULL);
2668  assert(expr != NULL);
2669 
2670  /* if value is up-to-date, then nothing to do */
2671  if( soltag != 0 && expr->evaltag == soltag )
2672  return SCIP_OKAY;
2673 
2674  /* assume we'll get a domain error, so we don't have to get this expr back if we abort the iteration
2675  * if there is no domain error, then we will overwrite the evalvalue in the last leaveexpr stage
2676  */
2677  expr->evalvalue = SCIP_INVALID;
2678  expr->evaltag = soltag;
2679 
2680  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2683 
2684  while( !SCIPexpriterIsEnd(it) )
2685  {
2686  switch( SCIPexpriterGetStageDFS(it) )
2687  {
2689  {
2690  SCIP_EXPR* child;
2691 
2692  if( soltag == 0 )
2693  break;
2694 
2695  /* check whether child has been evaluated for that solution already */
2696  child = SCIPexpriterGetChildExprDFS(it);
2697  if( soltag == child->evaltag )
2698  {
2699  if( child->evalvalue == SCIP_INVALID )
2700  goto TERMINATE;
2701 
2702  /* skip this child
2703  * this already returns the next one, so continue with loop
2704  */
2705  expr = SCIPexpriterSkipDFS(it);
2706  continue;
2707  }
2708 
2709  break;
2710  }
2711 
2713  {
2714  SCIP_CALL( SCIPexprhdlrEvalExpr(expr->exprhdlr, set, NULL , expr, &expr->evalvalue, NULL, sol) );
2715  expr->evaltag = soltag;
2716 
2717  if( expr->evalvalue == SCIP_INVALID )
2718  goto TERMINATE;
2719 
2720  break;
2721  }
2722 
2723  default :
2724  /* we should never be here */
2725  SCIPABORT();
2726  break;
2727  }
2728 
2729  expr = SCIPexpriterGetNext(it);
2730  }
2731 
2732 TERMINATE:
2733  SCIPexpriterFree(&it);
2734 
2735  return SCIP_OKAY;
2736 }
2737 
2738 /** evaluates gradient of an expression for a given point
2739  *
2740  * Initiates an expression walk to also evaluate children, if necessary.
2741  * Value can be received via SCIPgetExprPartialDiffNonlinear().
2742  * If an error (division by zero, ...) occurs, this value will
2743  * be set to SCIP_INVALID.
2744  */
2746  SCIP_SET* set, /**< global SCIP settings */
2747  SCIP_STAT* stat, /**< dynamic problem statistics */
2748  BMS_BLKMEM* blkmem, /**< block memory */
2749  SCIP_EXPR* rootexpr, /**< expression to be evaluated */
2750  SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
2751  SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
2752  )
2753 {
2754  SCIP_EXPRITER* it;
2755  SCIP_EXPR* expr;
2756  SCIP_EXPR* child;
2757  SCIP_Real derivative;
2758  SCIP_Longint difftag;
2759 
2760  assert(set != NULL);
2761  assert(stat != NULL);
2762  assert(blkmem != NULL);
2763  assert(rootexpr != NULL);
2764 
2765  /* ensure expression is evaluated */
2766  SCIP_CALL( SCIPexprEval(set, stat, blkmem, rootexpr, sol, soltag) );
2767 
2768  /* check if expression could not be evaluated */
2769  if( SCIPexprGetEvalValue(rootexpr) == SCIP_INVALID )
2770  {
2771  rootexpr->derivative = SCIP_INVALID;
2772  return SCIP_OKAY;
2773  }
2774 
2775  if( SCIPexprIsValue(set, rootexpr) )
2776  {
2777  rootexpr->derivative = 0.0;
2778  return SCIP_OKAY;
2779  }
2780 
2781  difftag = ++(stat->exprlastdifftag);
2782 
2783  rootexpr->derivative = 1.0;
2784  rootexpr->difftag = difftag;
2785 
2786  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2787  SCIP_CALL( SCIPexpriterInit(it, rootexpr, SCIP_EXPRITER_DFS, TRUE) );
2789 
2790  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2791  {
2792  assert(expr->evalvalue != SCIP_INVALID);
2793 
2794  child = SCIPexpriterGetChildExprDFS(it);
2795  assert(child != NULL);
2796 
2797  /* reset the value of the partial derivative w.r.t. a variable expression if we see it for the first time */
2798  if( child->difftag != difftag && SCIPexprIsVar(set, child) )
2799  child->derivative = 0.0;
2800 
2801  /* update differentiation tag of the child */
2802  child->difftag = difftag;
2803 
2804  /* call backward differentiation callback */
2805  if( SCIPexprIsValue(set, child) )
2806  {
2807  derivative = 0.0;
2808  }
2809  else
2810  {
2811  derivative = SCIP_INVALID;
2813  &derivative, NULL, 0.0) );
2814 
2815  if( derivative == SCIP_INVALID )
2816  {
2817  rootexpr->derivative = SCIP_INVALID;
2818  break;
2819  }
2820  }
2821 
2822  /* update partial derivative stored in the child expression
2823  * for a variable, we have to sum up the partial derivatives of the root w.r.t. this variable over all parents
2824  * for other intermediate expressions, we only store the partial derivative of the root w.r.t. this expression
2825  */
2826  if( !SCIPexprIsVar(set, child) )
2827  child->derivative = expr->derivative * derivative;
2828  else
2829  child->derivative += expr->derivative * derivative;
2830  }
2831 
2832  SCIPexpriterFree(&it);
2833 
2834  return SCIP_OKAY;
2835 }
2836 
2837 /** evaluates Hessian-vector product of an expression for a given point and direction
2838  *
2839  * Evaluates children, if necessary.
2840  * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear()
2841  * If an error (division by zero, ...) occurs, this value will
2842  * be set to SCIP_INVALID.
2843  */
2845  SCIP_SET* set, /**< global SCIP settings */
2846  SCIP_STAT* stat, /**< dynamic problem statistics */
2847  BMS_BLKMEM* blkmem, /**< block memory */
2848  SCIP_EXPR* rootexpr, /**< expression to be evaluated */
2849  SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
2850  SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */
2851  SCIP_SOL* direction /**< direction */
2852  )
2853 {
2854  SCIP_EXPRITER* it;
2855  SCIP_EXPR* expr;
2856  SCIP_EXPR* child;
2857  SCIP_Real derivative;
2858  SCIP_Real hessiandir;
2859 
2860  assert(set != NULL);
2861  assert(stat != NULL);
2862  assert(blkmem != NULL);
2863  assert(rootexpr != NULL);
2864 
2865  if( SCIPexprIsValue(set, rootexpr) )
2866  {
2867  rootexpr->dot = 0.0;
2868  rootexpr->bardot = 0.0;
2869  return SCIP_OKAY;
2870  }
2871 
2872  /* evaluate expression and directional derivative */
2873  SCIP_CALL( evalAndDiff(set, stat, blkmem, rootexpr, sol, soltag, direction) );
2874 
2875  if( rootexpr->evalvalue == SCIP_INVALID )
2876  {
2877  rootexpr->derivative = SCIP_INVALID;
2878  rootexpr->bardot = SCIP_INVALID;
2879  return SCIP_OKAY;
2880  }
2881 
2882  rootexpr->derivative = 1.0;
2883 
2884  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2885  SCIP_CALL( SCIPexpriterInit(it, rootexpr, SCIP_EXPRITER_DFS, TRUE) );
2887 
2888  /* compute reverse diff and bardots: i.e. hessian times direction */
2889  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2890  {
2891  assert(expr->evalvalue != SCIP_INVALID);
2892 
2893  child = SCIPexpriterGetChildExprDFS(it);
2894  assert(child != NULL);
2895 
2896  /* call backward and forward-backward differentiation callback */
2897  if( SCIPexprIsValue(set, child) )
2898  {
2899  derivative = 0.0;
2900  hessiandir = 0.0;
2901  }
2902  else
2903  {
2904  derivative = SCIP_INVALID;
2905  hessiandir = SCIP_INVALID;
2907  &derivative, NULL, SCIP_INVALID) );
2909  &hessiandir, NULL) );
2910 
2911  if( derivative == SCIP_INVALID || hessiandir == SCIP_INVALID )
2912  {
2913  rootexpr->derivative = SCIP_INVALID;
2914  rootexpr->bardot = SCIP_INVALID;
2915  break;
2916  }
2917  }
2918 
2919  /* update partial derivative and hessian stored in the child expression
2920  * for a variable, we have to sum up the partial derivatives of the root w.r.t. this variable over all parents
2921  * for other intermediate expressions, we only store the partial derivative of the root w.r.t. this expression
2922  */
2923  if( !SCIPexprIsVar(set, child) )
2924  {
2925  child->derivative = expr->derivative * derivative;
2926  child->bardot = expr->bardot * derivative + expr->derivative * hessiandir;
2927  }
2928  else
2929  {
2930  child->derivative += expr->derivative * derivative;
2931  child->bardot += expr->bardot * derivative + expr->derivative * hessiandir;
2932  }
2933  }
2934 
2935  SCIPexpriterFree(&it);
2936 
2937  return SCIP_OKAY;
2938 }
2939 
2940 /** possibly reevaluates and then returns the activity of the expression
2941  *
2942  * Reevaluate activity if currently stored is no longer uptodate.
2943  * If the expr owner provided a evalactivity-callback, then call this.
2944  * Otherwise, loop over descendants and compare activitytag with stat's domchgcount, i.e.,
2945  * whether some bound was changed since last evaluation, to check whether exprhdlrs INTEVAL should be called.
2946  *
2947  * @note If expression is set to be integral, then activities are tightened to integral values.
2948  * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
2949  */
2951  SCIP_SET* set, /**< global SCIP settings */
2952  SCIP_STAT* stat, /**< dynamic problem statistics */
2953  BMS_BLKMEM* blkmem, /**< block memory */
2954  SCIP_EXPR* rootexpr /**< expression */
2955  )
2956 {
2957  SCIP_EXPRITER* it;
2958  SCIP_EXPR* expr;
2959 
2960  assert(set != NULL);
2961  assert(stat != NULL);
2962  assert(blkmem != NULL);
2963  assert(rootexpr != NULL);
2964 
2965  if( rootexpr->ownerevalactivity != NULL )
2966  {
2967  /* call owner callback for activity-eval */
2968  SCIP_CALL( rootexpr->ownerevalactivity(set->scip, rootexpr, rootexpr->ownerdata) );
2969 
2970  return SCIP_OKAY;
2971  }
2972 
2973  /* fallback if no callback is given */
2974 
2975  assert(rootexpr->activitytag <= stat->domchgcount);
2976 
2977  /* if value is up-to-date, then nothing to do */
2978  if( rootexpr->activitytag == stat->domchgcount )
2979  {
2980 #ifdef DEBUG_PROP
2981  SCIPsetDebugMsg(set, "activitytag of root expr equals domchgcount (%u), skip evalactivity\n", stat->domchgcount);
2982 #endif
2983 
2984  return SCIP_OKAY;
2985  }
2986 
2987  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
2988  SCIP_CALL( SCIPexpriterInit(it, rootexpr, SCIP_EXPRITER_DFS, TRUE) );
2990 
2991  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); )
2992  {
2993  switch( SCIPexpriterGetStageDFS(it) )
2994  {
2996  {
2997  /* skip child if it has been evaluated already */
2998  SCIP_EXPR* child;
2999 
3000  child = SCIPexpriterGetChildExprDFS(it);
3001  if( child->activitytag == stat->domchgcount )
3002  {
3003  expr = SCIPexpriterSkipDFS(it);
3004  continue;
3005  }
3006 
3007  break;
3008  }
3009 
3011  {
3012  /* we should not have entered this expression if its activity was already uptodate */
3013  assert(expr->activitytag < stat->domchgcount);
3014 
3015  /* reset activity to entire if invalid, so we can use it as starting point below */
3017 
3018 #ifdef DEBUG_PROP
3019  SCIPsetDebugMsg(set, "interval evaluation of expr %p ", (void*)expr);
3020  SCIP_CALL( SCIPprintExpr(set->scip, expr, NULL) );
3021  SCIPsetDebugMsgPrint(set, "\n");
3022 #endif
3023 
3024  /* call the inteval callback of the exprhdlr */
3025  SCIP_CALL( SCIPexprhdlrIntEvalExpr(expr->exprhdlr, set, expr, &expr->activity, NULL, NULL) );
3026 #ifdef DEBUG_PROP
3027  SCIPsetDebugMsg(set, " exprhdlr <%s>::inteval = [%.20g, %.20g]", expr->exprhdlr->name, expr->activity.inf,
3028  expr->activity.sup);
3029 #endif
3030 
3031  /* if expression is integral, then we try to tighten the interval bounds a bit
3032  * this should undo the addition of some unnecessary safety added by use of nextafter() in interval
3033  * arithmetics, e.g., when doing pow() it would be ok to use ceil() and floor(), but for safety we
3034  * use SCIPceil and SCIPfloor for now the default intevalVar does not relax variables, so can omit
3035  * expressions without children (constants should be ok, too)
3036  */
3037  if( expr->isintegral && expr->nchildren > 0 )
3038  {
3039  if( expr->activity.inf > -SCIP_INTERVAL_INFINITY )
3040  expr->activity.inf = SCIPsetCeil(set, expr->activity.inf);
3041  if( expr->activity.sup < SCIP_INTERVAL_INFINITY )
3042  expr->activity.sup = SCIPsetFloor(set, expr->activity.sup);
3043 #ifdef DEBUG_PROP
3044  SCIPsetDebugMsg(set, " applying integrality: [%.20g, %.20g]\n", expr->activity.inf, expr->activity.sup);
3045 #endif
3046  }
3047 
3048  /* mark activity as empty if either the lower/upper bound is above/below +/- SCIPinfinity()
3049  * TODO this is a problem if dual-presolve fixed a variable to +/- infinity
3050  */
3051  if( SCIPsetIsInfinity(set, expr->activity.inf) || SCIPsetIsInfinity(set, -expr->activity.sup) )
3052  {
3053  SCIPsetDebugMsg(set, "treat activity [%g,%g] as empty as beyond infinity\n", expr->activity.inf, expr->activity.sup);
3054  SCIPintervalSetEmpty(&expr->activity);
3055  }
3056 
3057  /* remember that activity is uptodate now */
3058  expr->activitytag = stat->domchgcount;
3059 
3060  break;
3061  }
3062 
3063  default:
3064  /* you should never be here */
3065  SCIPABORT();
3066  break;
3067  }
3068 
3069  expr = SCIPexpriterGetNext(it);
3070  }
3071 
3072  SCIPexpriterFree(&it);
3073 
3074  return SCIP_OKAY;
3075 }
3076 
3077 /** compare expressions
3078  *
3079  * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
3080  * @note The given expressions are assumed to be simplified.
3081  */
3083  SCIP_SET* set, /**< global SCIP settings */
3084  SCIP_EXPR* expr1, /**< first expression */
3085  SCIP_EXPR* expr2 /**< second expression */
3086  )
3087 {
3088  SCIP_EXPRHDLR* exprhdlr1;
3089  SCIP_EXPRHDLR* exprhdlr2;
3090  int retval;
3091 
3092  exprhdlr1 = expr1->exprhdlr;
3093  exprhdlr2 = expr2->exprhdlr;
3094 
3095  /* expressions are of the same kind/type; use compare callback or default method */
3096  if( exprhdlr1 == exprhdlr2 )
3097  return SCIPexprhdlrCompareExpr(set, expr1, expr2);
3098 
3099  /* expressions are of different kind/type */
3100  /* enforces OR6 */
3101  if( SCIPexprIsValue(set, expr1) )
3102  {
3103  return -1;
3104  }
3105  /* enforces OR12 */
3106  if( SCIPexprIsValue(set, expr2) )
3107  return -SCIPexprCompare(set, expr2, expr1);
3108 
3109  /* enforces OR7 */
3110  if( SCIPexprIsSum(set, expr1) )
3111  {
3112  int compareresult;
3113  int nchildren;
3114 
3115  nchildren = expr1->nchildren;
3116  compareresult = SCIPexprCompare(set, expr1->children[nchildren-1], expr2);
3117 
3118  if( compareresult != 0 )
3119  return compareresult;
3120 
3121  /* "base" of the largest expression of the sum is equal to expr2, coefficient might tell us that
3122  * expr2 is larger */
3123  if( SCIPgetCoefsExprSum(expr1)[nchildren-1] < 1.0 )
3124  return -1;
3125 
3126  /* largest expression of sum is larger or equal than expr2 => expr1 > expr2 */
3127  return 1;
3128  }
3129  /* enforces OR12 */
3130  if( SCIPexprIsSum(set, expr2) )
3131  return -SCIPexprCompare(set, expr2, expr1);
3132 
3133  /* enforces OR8 */
3134  if( SCIPexprIsProduct(set, expr1) )
3135  {
3136  int compareresult;
3137  int nchildren;
3138 
3139  nchildren = expr1->nchildren;
3140  compareresult = SCIPexprCompare(set, expr1->children[nchildren-1], expr2);
3141 
3142  if( compareresult != 0 )
3143  return compareresult;
3144 
3145  /* largest expression of product is larger or equal than expr2 => expr1 > expr2 */
3146  return 1;
3147  }
3148  /* enforces OR12 */
3149  if( SCIPexprIsProduct(set, expr2) )
3150  return -SCIPexprCompare(set, expr2, expr1);
3151 
3152  /* enforces OR9 */
3153  if( SCIPexprIsPower(set, expr1) )
3154  {
3155  int compareresult;
3156 
3157  compareresult = SCIPexprCompare(set, expr1->children[0], expr2);
3158 
3159  if( compareresult != 0 )
3160  return compareresult;
3161 
3162  /* base equal to expr2, exponent might tell us that expr2 is larger */
3163  if( SCIPgetExponentExprPow(expr1) < 1.0 )
3164  return -1;
3165 
3166  /* power expression is larger => expr1 > expr2 */
3167  return 1;
3168  }
3169  /* enforces OR12 */
3170  if( SCIPexprIsPower(set, expr2) )
3171  return -SCIPexprCompare(set, expr2, expr1);
3172 
3173  /* enforces OR10 */
3174  if( SCIPexprIsVar(set, expr1) )
3175  return -1;
3176  /* enforces OR12 */
3177  if( SCIPexprIsVar(set, expr2) )
3178  return -SCIPexprCompare(set, expr2, expr1);
3179 
3180  /* enforces OR11 */
3181  retval = strcmp(SCIPexprhdlrGetName(exprhdlr1), SCIPexprhdlrGetName(exprhdlr2));
3182  return retval == 0 ? 0 : retval < 0 ? -1 : 1;
3183 }
3184 
3185 /** simplifies an expression
3186  *
3187  * @see SCIPsimplifyExpr
3188  */
3190  SCIP_SET* set, /**< global SCIP settings */
3191  SCIP_STAT* stat, /**< dynamic problem statistics */
3192  BMS_BLKMEM* blkmem, /**< block memory */
3193  SCIP_EXPR* rootexpr, /**< expression to be simplified */
3194  SCIP_EXPR** simplified, /**< buffer to store simplified expression */
3195  SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */
3196  SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */
3197  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
3198  void* ownercreatedata /**< data to pass to ownercreate */
3199  )
3200 {
3201  SCIP_EXPR* expr;
3202  SCIP_EXPRITER* it;
3203 
3204  assert(rootexpr != NULL);
3205  assert(simplified != NULL);
3206  assert(changed != NULL);
3207  assert(infeasible != NULL);
3208 
3209  /* simplify bottom up
3210  * when leaving an expression it simplifies it and stores the simplified expr in its iterators expression data
3211  * after the child was visited, it is replaced with the simplified expr
3212  */
3213  SCIP_CALL( SCIPexpriterCreate(stat, blkmem, &it) );
3214  SCIP_CALL( SCIPexpriterInit(it, rootexpr, SCIP_EXPRITER_DFS, TRUE) ); /* TODO can we set allowrevisited to FALSE?*/
3216 
3217  *changed = FALSE;
3218  *infeasible = FALSE;
3219  for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
3220  {
3221  switch( SCIPexpriterGetStageDFS(it) )
3222  {
3224  {
3225  SCIP_EXPR* newchild;
3226  SCIP_EXPR* child;
3227 
3229  child = SCIPexpriterGetChildExprDFS(it);
3230  assert(newchild != NULL);
3231 
3232  /* if child got simplified, replace it with the new child */
3233  if( newchild != child )
3234  {
3235  SCIP_CALL( SCIPexprReplaceChild(set, stat, blkmem, expr, SCIPexpriterGetChildIdxDFS(it), newchild) );
3236  }
3237 
3238  /* we do not need to hold newchild anymore */
3239  SCIP_CALL( SCIPexprRelease(set, stat, blkmem, &newchild) );
3240 
3241  break;
3242  }
3243 
3245  {
3246  SCIP_EXPR* refexpr = NULL;
3247  SCIP_EXPRITER_USERDATA iterdata;
3248 
3249  /* TODO we should do constant folding (handle that all children are value-expressions) here in a generic way
3250  * instead of reimplementing it in every handler
3251  */
3252 
3253  /* use simplification of expression handlers */
3254  SCIP_CALL( SCIPexprhdlrSimplifyExpr(expr->exprhdlr, set, expr, &refexpr, ownercreate, ownercreatedata) );
3255  assert(refexpr != NULL);
3256  if( expr != refexpr )
3257  *changed = TRUE;
3258 
3259  iterdata.ptrval = (void*) refexpr;
3260  SCIPexpriterSetCurrentUserData(it, iterdata);
3261 
3262  break;
3263  }
3264 
3265  default:
3266  SCIPABORT(); /* we should never be called in this stage */
3267  break;
3268  }
3269  }
3270 
3271  *simplified = (SCIP_EXPR*)SCIPexpriterGetExprUserData(it, rootexpr).ptrval;
3272  assert(*simplified != NULL);
3273 
3274  SCIPexpriterFree(&it);
3275 
3276  return SCIP_OKAY;
3277 }
3278 
3279 /** method to retrieve symmetry information from an expression
3280  *
3281  * @see SCIPgetSymDataExpr
3282  */
3284  SCIP_SET* set, /**< global SCIP settings */
3285  SCIP_EXPR* expr, /**< expression from which information is retrieved */
3286  SYM_EXPRDATA** symdata /**< buffer to store symmetry information */
3287  )
3288 {
3289  SCIP_EXPRHDLR* exprhdlr;
3290 
3291  assert(set != NULL);
3292  assert(expr != NULL);
3293  assert(symdata != NULL);
3294 
3295  exprhdlr = SCIPexprGetHdlr(expr);
3296  assert(exprhdlr != NULL);
3297 
3298  if( exprhdlr->getsymdata != NULL )
3299  {
3300  SCIP_CALL( exprhdlr->getsymdata(set->scip, expr, symdata) );
3301  }
3302  else
3303  *symdata = NULL;
3304 
3305  return SCIP_OKAY;
3306 }
3307 
3308 /** checks whether an expression is quadratic
3309  *
3310  * An expression is quadratic if it is either a power expression with exponent 2.0, a product of two expressions,
3311  * or a sum of terms where at least one is a square or a product of two.
3312  *
3313  * Use \ref SCIPexprGetQuadraticData to get data about the representation as quadratic.
3314  */
3316  SCIP_SET* set, /**< global SCIP settings */
3317  BMS_BLKMEM* blkmem, /**< block memory */
3318  SCIP_EXPR* expr, /**< expression */
3319  SCIP_Bool* isquadratic /**< buffer to store result */
3320  )
3321 {
3322  SCIP_HASHMAP* expr2idx;
3323  SCIP_HASHMAP* seenexpr = NULL;
3324  int nquadterms = 0;
3325  int nlinterms = 0;
3326  int nbilinterms = 0;
3327  int c;
3328 
3329  assert(set != NULL);
3330  assert(blkmem != NULL);
3331  assert(expr != NULL);
3332  assert(isquadratic != NULL);
3333 
3334  if( expr->quadchecked )
3335  {
3336  *isquadratic = expr->quaddata != NULL;
3337  return SCIP_OKAY;
3338  }
3339  assert(expr->quaddata == NULL);
3340 
3341  expr->quadchecked = TRUE;
3342  *isquadratic = FALSE;
3343 
3344  /* check if expression is a quadratic expression */
3345  SCIPsetDebugMsg(set, "checking if expr %p is quadratic\n", (void*)expr);
3346 
3347  /* handle single square term */
3348  if( SCIPexprIsPower(set, expr) && SCIPgetExponentExprPow(expr) == 2.0 )
3349  {
3350  SCIPsetDebugMsg(set, "expr %p looks like square: fill data structures\n", (void*)expr);
3351  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, &expr->quaddata) );
3352 
3353  expr->quaddata->nquadexprs = 1;
3354  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &expr->quaddata->quadexprterms, 1) );
3355  expr->quaddata->quadexprterms[0].expr = expr->children[0];
3356  expr->quaddata->quadexprterms[0].sqrcoef = 1.0;
3357 
3358  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, expr->quaddata->quadexprterms[0].expr);
3359 
3360  *isquadratic = TRUE;
3361  return SCIP_OKAY;
3362  }
3363 
3364  /* handle single bilinear term */
3365  if( SCIPexprIsProduct(set, expr) && SCIPexprGetNChildren(expr) == 2 )
3366  {
3367  SCIPsetDebugMsg(set, "expr %p looks like bilinear product: fill data structures\n", (void*)expr);
3368  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, &expr->quaddata) );
3369  expr->quaddata->nquadexprs = 2;
3370 
3371  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &expr->quaddata->quadexprterms, 2) );
3372  expr->quaddata->quadexprterms[0].expr = SCIPexprGetChildren(expr)[0];
3373  expr->quaddata->quadexprterms[0].nadjbilin = 1;
3374  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->quadexprterms[0].adjbilin, 1) );
3375  expr->quaddata->quadexprterms[0].adjbilin[0] = 0;
3376 
3377  expr->quaddata->quadexprterms[1].expr = SCIPexprGetChildren(expr)[1];
3378  expr->quaddata->quadexprterms[1].nadjbilin = 1;
3379  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->quadexprterms[1].adjbilin, 1) );
3380  expr->quaddata->quadexprterms[1].adjbilin[0] = 0;
3381 
3382  expr->quaddata->nbilinexprterms = 1;
3383  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &expr->quaddata->bilinexprterms, 1) );
3384  expr->quaddata->bilinexprterms[0].expr1 = SCIPexprGetChildren(expr)[1];
3385  expr->quaddata->bilinexprterms[0].expr2 = SCIPexprGetChildren(expr)[0];
3386  expr->quaddata->bilinexprterms[0].coef = 1.0;
3387 
3388  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, expr->quaddata->quadexprterms[0].expr)
3389  && SCIPexprIsVar(set, expr->quaddata->quadexprterms[1].expr);
3390 
3391  *isquadratic = TRUE;
3392  return SCIP_OKAY;
3393  }
3394 
3395  /* neither a sum, nor a square, nor a bilinear term */
3396  if( !SCIPexprIsSum(set, expr) )
3397  return SCIP_OKAY;
3398 
3399  SCIP_CALL( SCIPhashmapCreate(&seenexpr, blkmem, 2*SCIPexprGetNChildren(expr)) );
3400  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
3401  {
3402  SCIP_EXPR* child;
3403 
3404  child = SCIPexprGetChildren(expr)[c];
3405  assert(child != NULL);
3406 
3407  if( SCIPexprIsPower(set, child) && SCIPgetExponentExprPow(child) == 2.0 ) /* quadratic term */
3408  {
3409  SCIP_CALL( quadDetectProcessExpr(SCIPexprGetChildren(child)[0], seenexpr, &nquadterms, &nlinterms) );
3410  }
3411  else if( SCIPexprIsProduct(set, child) && SCIPexprGetNChildren(child) == 2 ) /* bilinear term */
3412  {
3413  ++nbilinterms;
3414  SCIP_CALL( quadDetectProcessExpr(SCIPexprGetChildren(child)[0], seenexpr, &nquadterms, &nlinterms) );
3415  SCIP_CALL( quadDetectProcessExpr(SCIPexprGetChildren(child)[1], seenexpr, &nquadterms, &nlinterms) );
3416  }
3417  else
3418  {
3419  /* first time seen linearly --> assign -1; ++nlinterms
3420  * not first time --> assign +=1;
3421  */
3422  if( SCIPhashmapExists(seenexpr, (void*)child) )
3423  {
3424  assert(SCIPhashmapGetImageInt(seenexpr, (void*)child) > 0);
3425 
3426  SCIP_CALL( SCIPhashmapSetImageInt(seenexpr, (void*)child, SCIPhashmapGetImageInt(seenexpr, (void*)child) + 1) );
3427  }
3428  else
3429  {
3430  ++nlinterms;
3431  SCIP_CALL( SCIPhashmapInsertInt(seenexpr, (void*)child, -1) );
3432  }
3433  }
3434  }
3435 
3436  if( nquadterms == 0 )
3437  {
3438  /* only linear sum */
3439  SCIPhashmapFree(&seenexpr);
3440  return SCIP_OKAY;
3441  }
3442 
3443  SCIPsetDebugMsg(set, "expr %p looks quadratic: fill data structures\n", (void*)expr);
3444 
3445  /* expr2idx maps expressions to indices; if index > 0, it is its index in the linexprs array, otherwise -index-1 is
3446  * its index in the quadexprterms array
3447  */
3448  SCIP_CALL( SCIPhashmapCreate(&expr2idx, blkmem, nquadterms + nlinterms) );
3449 
3450  /* allocate memory, etc */
3451  SCIP_ALLOC( BMSallocClearBlockMemory(blkmem, &expr->quaddata) );
3452  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->quadexprterms, nquadterms) );
3453  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->linexprs, nlinterms) );
3454  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->lincoefs, nlinterms) );
3455  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &expr->quaddata->bilinexprterms, nbilinterms) );
3456 
3457  expr->quaddata->constant = SCIPgetConstantExprSum(expr);
3458 
3459  expr->quaddata->allexprsarevars = TRUE;
3460  /* for every term of the sum-expr */
3461  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
3462  {
3463  SCIP_EXPR* child;
3464  SCIP_Real coef;
3465 
3466  child = SCIPexprGetChildren(expr)[c];
3467  coef = SCIPgetCoefsExprSum(expr)[c];
3468 
3469  assert(child != NULL);
3470  assert(coef != 0.0);
3471 
3472  if( SCIPexprIsPower(set, child) && SCIPgetExponentExprPow(child) == 2.0 ) /* quadratic term */
3473  {
3474  SCIP_QUADEXPR_QUADTERM* quadexprterm;
3475  assert(SCIPexprGetNChildren(child) == 1);
3476 
3477  child = SCIPexprGetChildren(child)[0];
3478  assert(SCIPhashmapGetImageInt(seenexpr, (void *)child) > 0);
3479 
3480  SCIP_CALL( quadDetectGetQuadexprterm(blkmem, child, expr2idx, seenexpr, expr->quaddata, &quadexprterm) );
3481  assert(quadexprterm->expr == child);
3482  quadexprterm->sqrcoef = coef;
3483  quadexprterm->sqrexpr = SCIPexprGetChildren(expr)[c];
3484 
3485  if( expr->quaddata->allexprsarevars )
3486  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, quadexprterm->expr);
3487  }
3488  else if( SCIPexprIsProduct(set, child) && SCIPexprGetNChildren(child) == 2 ) /* bilinear term */
3489  {
3490  SCIP_QUADEXPR_BILINTERM* bilinexprterm;
3491  SCIP_QUADEXPR_QUADTERM* quadexprterm;
3492  SCIP_EXPR* expr1;
3493  SCIP_EXPR* expr2;
3494 
3495  assert(SCIPgetCoefExprProduct(child) == 1.0);
3496 
3497  expr1 = SCIPexprGetChildren(child)[0];
3498  expr2 = SCIPexprGetChildren(child)[1];
3499  assert(expr1 != NULL && expr2 != NULL);
3500 
3501  bilinexprterm = &expr->quaddata->bilinexprterms[expr->quaddata->nbilinexprterms];
3502 
3503  bilinexprterm->coef = coef;
3504  if( SCIPhashmapGetImageInt(seenexpr, (void*)expr1) >= SCIPhashmapGetImageInt(seenexpr, (void*)expr2) )
3505  {
3506  bilinexprterm->expr1 = expr1;
3507  bilinexprterm->expr2 = expr2;
3508  }
3509  else
3510  {
3511  bilinexprterm->expr1 = expr2;
3512  bilinexprterm->expr2 = expr1;
3513  }
3514  bilinexprterm->prodexpr = child;
3515 
3516  SCIP_CALL( quadDetectGetQuadexprterm(blkmem, expr1, expr2idx, seenexpr, expr->quaddata, &quadexprterm) );
3517  assert(quadexprterm->expr == expr1);
3518  quadexprterm->adjbilin[quadexprterm->nadjbilin] = expr->quaddata->nbilinexprterms;
3519  ++quadexprterm->nadjbilin;
3520 
3521  if( expr->quaddata->allexprsarevars )
3522  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, quadexprterm->expr);
3523 
3524  SCIP_CALL( quadDetectGetQuadexprterm(blkmem, expr2, expr2idx, seenexpr, expr->quaddata, &quadexprterm) );
3525  assert(quadexprterm->expr == expr2);
3526  quadexprterm->adjbilin[quadexprterm->nadjbilin] = expr->quaddata->nbilinexprterms;
3527  ++quadexprterm->nadjbilin;
3528 
3529  if( expr->quaddata->allexprsarevars )
3530  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, quadexprterm->expr);
3531 
3532  ++expr->quaddata->nbilinexprterms;
3533 
3534  /* store position of second factor in quadexprterms */
3535  bilinexprterm->pos2 = SCIPhashmapGetImageInt(expr2idx, (void*)bilinexprterm->expr2);
3536  }
3537  else /* linear term */
3538  {
3539  if( SCIPhashmapGetImageInt(seenexpr, (void*)child) < 0 )
3540  {
3541  assert(SCIPhashmapGetImageInt(seenexpr, (void*)child) == -1);
3542 
3543  /* expression only appears linearly */
3544  expr->quaddata->linexprs[expr->quaddata->nlinexprs] = child;
3545  expr->quaddata->lincoefs[expr->quaddata->nlinexprs] = coef;
3546  expr->quaddata->nlinexprs++;
3547 
3548  if( expr->quaddata->allexprsarevars )
3549  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, child);
3550  }
3551  else
3552  {
3553  /* expression appears non-linearly: set lin coef */
3554  SCIP_QUADEXPR_QUADTERM* quadexprterm;
3555  assert(SCIPhashmapGetImageInt(seenexpr, (void*)child) > 0);
3556 
3557  SCIP_CALL( quadDetectGetQuadexprterm(blkmem, child, expr2idx, seenexpr, expr->quaddata, &quadexprterm) );
3558  assert(quadexprterm->expr == child);
3559  quadexprterm->lincoef = coef;
3560 
3561  if( expr->quaddata->allexprsarevars )
3562  expr->quaddata->allexprsarevars = SCIPexprIsVar(set, quadexprterm->expr);
3563  }
3564  }
3565  }
3566  assert(expr->quaddata->nquadexprs == nquadterms);
3567  assert(expr->quaddata->nlinexprs == nlinterms);
3568  assert(expr->quaddata->nbilinexprterms == nbilinterms);
3569 
3570  SCIPhashmapFree(&seenexpr);
3571  SCIPhashmapFree(&expr2idx);
3572 
3573  *isquadratic = TRUE;
3574 
3575  return SCIP_OKAY;
3576 }
3577 
3578 /** frees information on quadratic representation of an expression
3579  *
3580  * Reverts SCIPexprCheckQuadratic().
3581  * Before doing changes to an expression, it can be useful to call this function.
3582  */
3584  BMS_BLKMEM* blkmem, /**< block memory */
3585  SCIP_EXPR* expr /**< expression */
3586  )
3587 {
3588  int i;
3589  int n;
3590 
3591  assert(blkmem != NULL);
3592  assert(expr != NULL);
3593 
3594  expr->quadchecked = FALSE;
3595 
3596  if( expr->quaddata == NULL )
3597  return;
3598 
3599  n = expr->quaddata->nquadexprs;
3600 
3604  BMSfreeBlockMemoryArrayNull(blkmem, &expr->quaddata->eigenvalues, n);
3605  if( expr->quaddata->eigenvectors != NULL ) /* check for NULL here before calculating n*n to avoid (harmless) overflow in case of large n */
3606  BMSfreeBlockMemoryArray(blkmem, &expr->quaddata->eigenvectors, n * n); /*lint !e647*/
3607 
3608  for( i = 0; i < n; ++i )
3609  {
3611  expr->quaddata->quadexprterms[i].adjbilinsize);
3612  }
3614 
3615  BMSfreeBlockMemory(blkmem, &expr->quaddata);
3616 }
3617 
3618 /** Checks the curvature of the quadratic function stored in quaddata
3619  *
3620  * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
3621  * If Q is
3622  * - semidefinite positive -> curv is set to convex,
3623  * - semidefinite negative -> curv is set to concave,
3624  * - otherwise -> curv is set to unknown.
3625  *
3626  * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
3627  * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
3628  */
3630  SCIP_SET* set, /**< global SCIP settings */
3631  BMS_BLKMEM* blkmem, /**< block memory */
3632  BMS_BUFMEM* bufmem, /**< buffer memory */
3633  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
3634  SCIP_EXPR* expr, /**< quadratic expression */
3635  SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */
3636  SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
3637  SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */
3638  )
3639 {
3640  SCIP_QUADEXPR* quaddata;
3641  SCIP_HASHMAP* expr2matrix;
3642  double* matrix;
3643  double* alleigval;
3644  int nvars;
3645  int nn;
3646  int n;
3647  int i;
3648 
3649  assert(set != NULL);
3650  assert(blkmem != NULL);
3651  assert(bufmem != NULL);
3652  assert(messagehdlr != NULL);
3653  assert(expr != NULL);
3654  assert(curv != NULL);
3655 
3656  quaddata = expr->quaddata;
3657  assert(quaddata != NULL);
3658 
3659  /* do not store eigen information if we are not considering full matrix */
3660  if( assumevarfixed != NULL )
3661  storeeigeninfo = FALSE;
3662 
3663  if( quaddata->eigeninfostored || (quaddata->curvaturechecked && !storeeigeninfo) )
3664  {
3665  *curv = quaddata->curvature;
3666  /* if we are convex or concave on the full set of variables, then we will also be so on a subset */
3667  if( assumevarfixed == NULL || quaddata->curvature != SCIP_EXPRCURV_UNKNOWN )
3668  return SCIP_OKAY;
3669  }
3670  assert(quaddata->curvature == SCIP_EXPRCURV_UNKNOWN || assumevarfixed != NULL
3671  || (storeeigeninfo && !quaddata->eigeninfostored));
3672 
3673  *curv = SCIP_EXPRCURV_UNKNOWN;
3674 
3675  n = quaddata->nquadexprs;
3676 
3677  /* do not check curvature if nn will be too large
3678  * we want nn * sizeof(real) to fit into an unsigned int, so n must be <= sqrt(unit_max/sizeof(real))
3679  * sqrt(2*214748364/8) = 7327.1475350234
3680  */
3681  if( n > 7000 )
3682  {
3683  SCIPmessageFPrintVerbInfo(messagehdlr, set->disp_verblevel, SCIP_VERBLEVEL_FULL, NULL,
3684  "number of quadratic variables is too large (%d) to check the curvature\n", n);
3685  return SCIP_OKAY;
3686  }
3687 
3688  /* TODO do some simple tests first; like diagonal entries don't change sign, etc */
3689 
3690  if( ! SCIPlapackIsAvailable() )
3691  return SCIP_OKAY;
3692 
3693  nn = n * n;
3694  assert(nn > 0);
3695  assert((unsigned)nn < UINT_MAX / sizeof(SCIP_Real));
3696 
3697  if( storeeigeninfo )
3698  {
3699  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &quaddata->eigenvalues, n));
3700  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &quaddata->eigenvectors, nn));
3701 
3702  alleigval = quaddata->eigenvalues;
3703  matrix = quaddata->eigenvectors;
3704  }
3705  else
3706  {
3707  SCIP_ALLOC( BMSallocBufferMemoryArray(bufmem, &alleigval, n) );
3708  SCIP_ALLOC( BMSallocClearBufferMemoryArray(bufmem, &matrix, nn) );
3709  }
3710 
3711  SCIP_CALL( SCIPhashmapCreate(&expr2matrix, blkmem, n) );
3712 
3713  /* fill matrix's diagonal */
3714  nvars = 0;
3715  for( i = 0; i < n; ++i )
3716  {
3717  SCIP_QUADEXPR_QUADTERM quadexprterm;
3718 
3719  quadexprterm = quaddata->quadexprterms[i];
3720 
3721  assert(!SCIPhashmapExists(expr2matrix, (void*)quadexprterm.expr));
3722 
3723  /* skip expr if it is a variable mentioned in assumevarfixed */
3724  if( assumevarfixed != NULL && SCIPexprIsVar(set, quadexprterm.expr)
3725  && SCIPhashmapExists(assumevarfixed, (void*)SCIPgetVarExprVar(quadexprterm.expr)) )
3726  continue;
3727 
3728  if( quadexprterm.sqrcoef == 0.0 && ! storeeigeninfo )
3729  {
3730  assert(quadexprterm.nadjbilin > 0);
3731  /* SCIPdebugMsg(scip, "var <%s> appears in bilinear term but is not squared
3732  * --> indefinite quadratic\n", SCIPvarGetName(quadexprterm.var)); */
3733  goto CLEANUP;
3734  }
3735 
3736  matrix[nvars * n + nvars] = quadexprterm.sqrcoef;
3737 
3738  /* remember row of variable in matrix */
3739  SCIP_CALL( SCIPhashmapInsert(expr2matrix, (void *)quadexprterm.expr, (void *)(size_t)nvars) );
3740  nvars++;
3741  }
3742 
3743  /* fill matrix's upper-diagonal */
3744  for( i = 0; i < quaddata->nbilinexprterms; ++i )
3745  {
3746  SCIP_QUADEXPR_BILINTERM bilinexprterm;
3747  int col;
3748  int row;
3749 
3750  bilinexprterm = quaddata->bilinexprterms[i];
3751 
3752  /* each factor should have been added to expr2matrix unless it corresponds to a variable mentioned in assumevarfixed */
3753  assert(SCIPhashmapExists(expr2matrix, (void*)bilinexprterm.expr1)
3754  || (assumevarfixed != NULL && SCIPexprIsVar(set, bilinexprterm.expr1)
3755  && SCIPhashmapExists(assumevarfixed, (void*)SCIPgetVarExprVar(bilinexprterm.expr1))));
3756  assert(SCIPhashmapExists(expr2matrix, (void*)bilinexprterm.expr2)
3757  || (assumevarfixed != NULL && SCIPexprIsVar(set, bilinexprterm.expr2)
3758  && SCIPhashmapExists(assumevarfixed, (void*)SCIPgetVarExprVar(bilinexprterm.expr2))));
3759 
3760  /* skip bilinear terms where at least one of the factors should be assumed to be fixed
3761  * (i.e., not present in expr2matrix map) */
3762  if( !SCIPhashmapExists(expr2matrix, (void*)bilinexprterm.expr1)
3763  || !SCIPhashmapExists(expr2matrix, (void*)bilinexprterm.expr2) )
3764  continue;
3765 
3766  row = (int)(size_t)SCIPhashmapGetImage(expr2matrix, bilinexprterm.expr1);
3767  col = (int)(size_t)SCIPhashmapGetImage(expr2matrix, bilinexprterm.expr2);
3768 
3769  assert(row != col);
3770 
3771  if( row < col )
3772  matrix[row * n + col] = bilinexprterm.coef / 2.0;
3773  else
3774  matrix[col * n + row] = bilinexprterm.coef / 2.0;
3775  }
3776 
3777  /* compute eigenvalues */
3778  if( SCIPlapackComputeEigenvalues(bufmem, storeeigeninfo, n, matrix, alleigval) != SCIP_OKAY )
3779  {
3780  SCIPmessagePrintWarning(messagehdlr, "Failed to compute eigenvalues of quadratic coefficient "
3781  "matrix --> don't know curvature\n");
3782  goto CLEANUP;
3783  }
3784 
3785  /* check convexity */
3786  if( !SCIPsetIsNegative(set, alleigval[0]) )
3787  *curv = SCIP_EXPRCURV_CONVEX;
3788  else if( !SCIPsetIsPositive(set, alleigval[n-1]) )
3789  *curv = SCIP_EXPRCURV_CONCAVE;
3790 
3791 CLEANUP:
3792  SCIPhashmapFree(&expr2matrix);
3793 
3794  if( !storeeigeninfo )
3795  {
3796  BMSfreeBufferMemoryArray(bufmem, &matrix);
3797  BMSfreeBufferMemoryArray(bufmem, &alleigval);
3798  }
3799  else
3800  {
3801  assert(!quaddata->eigeninfostored);
3802  quaddata->eigeninfostored = TRUE;
3803  }
3804 
3805  /* if checked convexity on full Q matrix, then remember it
3806  * if indefinite on submatrix, then it will also be indefinite on full matrix, so can remember that, too */
3807  if( assumevarfixed == NULL || *curv == SCIP_EXPRCURV_UNKNOWN )
3808  {
3809  quaddata->curvature = *curv;
3810  quaddata->curvaturechecked = TRUE;
3811  }
3812 
3813  return SCIP_OKAY;
3814 }
3815 
3816 
3817 /* from pub_expr.h */
3818 
3819 #ifdef NDEBUG
3820 #undef SCIPexprGetNUses
3821 #undef SCIPexprGetNChildren
3822 #undef SCIPexprGetChildren
3823 #undef SCIPexprGetHdlr
3824 #undef SCIPexprGetData
3825 #undef SCIPexprSetData
3826 #undef SCIPexprGetOwnerData
3827 #undef SCIPexprGetEvalValue
3828 #undef SCIPexprGetEvalTag
3829 #undef SCIPexprGetDerivative
3830 #undef SCIPexprGetDot
3831 #undef SCIPexprGetBardot
3832 #undef SCIPexprGetDiffTag
3833 #undef SCIPexprGetActivity
3834 #undef SCIPexprGetActivityTag
3835 #undef SCIPexprSetActivity
3836 #undef SCIPexprGetCurvature
3837 #undef SCIPexprSetCurvature
3838 #undef SCIPexprIsIntegral
3839 #undef SCIPexprSetIntegrality
3840 #undef SCIPexprAreQuadraticExprsVariables
3841 #endif
3842 
3843 /** gets the number of times the expression is currently captured */
3845  SCIP_EXPR* expr /**< expression */
3846  )
3847 {
3848  assert(expr != NULL);
3849 
3850  return expr->nuses;
3851 }
3852 
3853 /** gives the number of children of an expression */
3855  SCIP_EXPR* expr /**< expression */
3856  )
3857 {
3858  assert(expr != NULL);
3859 
3860  return expr->nchildren;
3861 }
3862 
3863 /** gives the children of an expression (can be NULL if no children) */
3865  SCIP_EXPR* expr /**< expression */
3866  )
3867 {
3868  assert(expr != NULL);
3869 
3870  return expr->children;
3871 }
3872 
3873 /** gets the expression handler of an expression
3874  *
3875  * This identifies the type of the expression (sum, variable, ...).
3876  */
3878  SCIP_EXPR* expr /**< expression */
3879  )
3880 {
3881  assert(expr != NULL);
3882 
3883  return expr->exprhdlr;
3884 }
3885 
3886 /** gets the expression data of an expression */
3888  SCIP_EXPR* expr /**< expression */
3889  )
3890 {
3891  assert(expr != NULL);
3892 
3893  return expr->exprdata;
3894 }
3895 
3896 /** sets the expression data of an expression
3897  *
3898  * The pointer to possible old data is overwritten and the
3899  * freedata-callback is not called before.
3900  * This function is intended to be used by expression handler only.
3901  */
3903  SCIP_EXPR* expr, /**< expression */
3904  SCIP_EXPRDATA* exprdata /**< expression data to be set (can be NULL) */
3905  )
3906 {
3907  assert(expr != NULL);
3908  assert(exprdata == NULL || expr->exprhdlr->copydata != NULL); /* copydata must be available if there is expression data */
3909  assert(exprdata == NULL || expr->exprhdlr->freedata != NULL); /* freedata must be available if there is expression data */
3910 
3911  expr->exprdata = exprdata;
3912 }
3913 
3914 /** gets the data that the owner of an expression has stored in an expression */
3916  SCIP_EXPR* expr /**< expression */
3917  )
3918 {
3919  assert(expr != NULL);
3920 
3921  return expr->ownerdata;
3922 }
3923 
3924 /** gives the value from the last evaluation of an expression (or SCIP_INVALID if there was an eval error)
3925  *
3926  * @see SCIPevalExpr to evaluate the expression at a given solution.
3927  */
3929  SCIP_EXPR* expr /**< expression */
3930  )
3931 {
3932  assert(expr != NULL);
3933 
3934  return expr->evalvalue;
3935 }
3936 
3937 /** gives the evaluation tag from the last evaluation, or 0
3938  *
3939  * @see SCIPevalExpr
3940  */
3942  SCIP_EXPR* expr /**< expression */
3943  )
3944 {
3945  assert(expr != NULL);
3946 
3947  return expr->evaltag;
3948 }
3949 
3950 /** returns the derivative stored in an expression (or SCIP_INVALID if there was an evaluation error)
3951  *
3952  * @see SCIPevalExprGradient
3953  */
3955  SCIP_EXPR* expr /**< expression */
3956  )
3957 {
3958  assert(expr != NULL);
3959 
3960  return expr->derivative;
3961 }
3962 
3963 /** gives the value of directional derivative from the last evaluation of a directional derivative of
3964  * expression (or SCIP_INVALID if there was an error)
3965  *
3966  * @see SCIPevalExprHessianDir
3967  */
3969  SCIP_EXPR* expr /**< expression */
3970  )
3971 {
3972  assert(expr != NULL);
3973 
3974  return expr->dot;
3975 }
3976 
3977 /** gives the value of directional derivative from the last evaluation of a directional derivative of
3978  * derivative of root (or SCIP_INVALID if there was an error)
3979  *
3980  * @see SCIPevalExprHessianDir
3981  */
3983  SCIP_EXPR* expr /**< expression */
3984  )
3985 {
3986  assert(expr != NULL);
3987 
3988  return expr->bardot;
3989 }
3990 
3991 /** returns the difftag stored in an expression
3992  *
3993  * can be used to check whether partial derivative value is valid
3994  *
3995  * @see SCIPevalExprGradient
3996  */
3998  SCIP_EXPR* expr /**< expression */
3999  )
4000 {
4001  assert(expr != NULL);
4002 
4003  return expr->difftag;
4004 }
4005 
4006 /** returns the activity that is currently stored for an expression
4007  *
4008  * @see SCIPevalExprActivity
4009  */
4011  SCIP_EXPR* expr /**< expression */
4012  )
4013 {
4014  assert(expr != NULL);
4015 
4016  return expr->activity;
4017 }
4018 
4019 /** returns the tag associated with the activity of the expression
4020  *
4021  * It can depend on the owner of the expression how to interpret this tag.
4022  * SCIPevalExprActivity() compares with `stat->domchgcount`.
4023  *
4024  * @see SCIPevalExprActivity
4025  */
4027  SCIP_EXPR* expr /**< expression */
4028  )
4029 {
4030  assert(expr != NULL);
4031 
4032  return expr->activitytag;
4033 }
4034 
4035 /** set the activity with tag for an expression */
4037  SCIP_EXPR* expr, /**< expression */
4038  SCIP_INTERVAL activity, /**< new activity */
4039  SCIP_Longint activitytag /**< tag associated with activity */
4040  )
4041 {
4042  assert(expr != NULL);
4043 
4044  expr->activity = activity;
4045  expr->activitytag = activitytag;
4046 }
4047 
4048 /** returns the curvature of an expression
4049  *
4050  * @note Call SCIPcomputeExprCurvature() before calling this function.
4051  */
4053  SCIP_EXPR* expr /**< expression */
4054  )
4055 {
4056  assert(expr != NULL);
4057 
4058  return expr->curvature;
4059 }
4060 
4061 /** sets the curvature of an expression */
4063  SCIP_EXPR* expr, /**< expression */
4064  SCIP_EXPRCURV curvature /**< curvature of the expression */
4065  )
4066 {
4067  assert(expr != NULL);
4068 
4069  expr->curvature = curvature;
4070 }
4071 
4072 /** returns whether an expression is integral */
4074  SCIP_EXPR* expr /**< expression */
4075  )
4076 {
4077  assert(expr != NULL);
4078 
4079  return expr->isintegral;
4080 }
4081 
4082 /** sets the integrality flag of an expression */
4084  SCIP_EXPR* expr, /**< expression */
4085  SCIP_Bool isintegral /**< integrality of the expression */
4086  )
4087 {
4088  assert(expr != NULL);
4089 
4090  expr->isintegral = isintegral;
4091 }
4092 
4093 /** gives the coefficients and expressions that define a quadratic expression
4094  *
4095  * It can return the constant part, the number, arguments, and coefficients of the purely linear part
4096  * and the number of quadratic terms and bilinear terms.
4097  * Note that for arguments that appear in the quadratic part, a linear coefficient is
4098  * stored with the quadratic term.
4099  * Use SCIPexprGetQuadraticQuadTerm() and SCIPexprGetQuadraticBilinTerm()
4100  * to access the data for a quadratic or bilinear term.
4101  *
4102  * It can also return the eigenvalues and the eigenvectors of the matrix \f$Q\f$ when the quadratic is written
4103  * as \f$x^T Q x + b^T x + c^T y + d\f$, where \f$c^T y\f$ defines the purely linear part.
4104  * Note, however, that to have access to them one needs to call SCIPcomputeExprQuadraticCurvature()
4105  * with `storeeigeninfo=TRUE`. If the eigen information was not stored or it failed to be computed,
4106  * `eigenvalues` and `eigenvectors` will be set to NULL.
4107  *
4108  * This function returns pointers to internal data in linexprs and lincoefs.
4109  * The user must not change this data.
4110  *
4111  * @attention SCIPcheckExprQuadratic() needs to be called first to check whether expression is quadratic and initialize the data of the quadratic representation.
4112  */
4114  SCIP_EXPR* expr, /**< quadratic expression */
4115  SCIP_Real* constant, /**< buffer to store constant term, or NULL */
4116  int* nlinexprs, /**< buffer to store number of expressions that appear linearly, or NULL */
4117  SCIP_EXPR*** linexprs, /**< buffer to store pointer to array of expressions that appear linearly, or NULL */
4118  SCIP_Real** lincoefs, /**< buffer to store pointer to array of coefficients of expressions that appear linearly, or NULL */
4119  int* nquadexprs, /**< buffer to store number of expressions in quadratic terms, or NULL */
4120  int* nbilinexprs, /**< buffer to store number of bilinear expressions terms, or NULL */
4121  SCIP_Real** eigenvalues, /**< buffer to store pointer to array of eigenvalues of Q, or NULL */
4122  SCIP_Real** eigenvectors /**< buffer to store pointer to array of eigenvectors of Q, or NULL */
4123  )
4124 {
4125  SCIP_QUADEXPR* quaddata;
4126 
4127  assert(expr != NULL);
4128 
4129  quaddata = expr->quaddata;
4130  assert(quaddata != NULL);
4131 
4132  if( constant != NULL )
4133  *constant = quaddata->constant;
4134  if( nlinexprs != NULL )
4135  *nlinexprs = quaddata->nlinexprs;
4136  if( linexprs != NULL )
4137  *linexprs = quaddata->linexprs;
4138  if( lincoefs != NULL )
4139  *lincoefs = quaddata->lincoefs;
4140  if( nquadexprs != NULL )
4141  *nquadexprs = quaddata->nquadexprs;
4142  if( nbilinexprs != NULL )
4143  *nbilinexprs = quaddata->nbilinexprterms;
4144  if( eigenvalues != NULL )
4145  *eigenvalues = quaddata->eigenvalues;
4146  if( eigenvectors != NULL )
4147  *eigenvectors = quaddata->eigenvectors;
4148 }
4149 
4150 /** gives the data of a quadratic expression term
4151  *
4152  * For a term \f$a \cdot \text{expr}^2 + b \cdot \text{expr} + \sum_i (c_i \cdot \text{expr} \cdot \text{otherexpr}_i)\f$, returns
4153  * `expr`, \f$a\f$, \f$b\f$, the number of summands, and indices of bilinear terms in the quadratic expressions `bilinexprterms`.
4154  *
4155  * This function returns pointers to internal data in adjbilin.
4156  * The user must not change this data.
4157  */
4159  SCIP_EXPR* quadexpr, /**< quadratic expression */
4160  int termidx, /**< index of quadratic term */
4161  SCIP_EXPR** expr, /**< buffer to store pointer to argument expression (the 'x') of this term, or NULL */
4162  SCIP_Real* lincoef, /**< buffer to store linear coefficient of variable, or NULL */
4163  SCIP_Real* sqrcoef, /**< buffer to store square coefficient of variable, or NULL */
4164  int* nadjbilin, /**< buffer to store number of bilinear terms this variable is involved in, or NULL */
4165  int** adjbilin, /**< buffer to store pointer to indices of associated bilinear terms, or NULL */
4166  SCIP_EXPR** sqrexpr /**< buffer to store pointer to square expression (the 'x^2') of this term or NULL if no square expression, or NULL */
4167  )
4168 {
4169  SCIP_QUADEXPR_QUADTERM* quadexprterm;
4170 
4171  assert(quadexpr != NULL);
4172  assert(quadexpr->quaddata != NULL);
4173  assert(quadexpr->quaddata->quadexprterms != NULL);
4174  assert(termidx >= 0);
4175  assert(termidx < quadexpr->quaddata->nquadexprs);
4176 
4177  quadexprterm = &quadexpr->quaddata->quadexprterms[termidx];
4178 
4179  if( expr != NULL )
4180  *expr = quadexprterm->expr;
4181  if( lincoef != NULL )
4182  *lincoef = quadexprterm->lincoef;
4183  if( sqrcoef != NULL )
4184  *sqrcoef = quadexprterm->sqrcoef;
4185  if( nadjbilin != NULL )
4186  *nadjbilin = quadexprterm->nadjbilin;
4187  if( adjbilin != NULL )
4188  *adjbilin = quadexprterm->adjbilin;
4189  if( sqrexpr != NULL )
4190  *sqrexpr = quadexprterm->sqrexpr;
4191 }
4192 
4193 /** gives the data of a bilinear expression term
4194  *
4195  * For a term a*expr1*expr2, returns expr1, expr2, a, and
4196  * the position of the quadratic expression term that uses expr2 in the quadratic expressions `quadexprterms`.
4197  */
4199  SCIP_EXPR* expr, /**< quadratic expression */
4200  int termidx, /**< index of bilinear term */
4201  SCIP_EXPR** expr1, /**< buffer to store first factor, or NULL */
4202  SCIP_EXPR** expr2, /**< buffer to store second factor, or NULL */
4203  SCIP_Real* coef, /**< buffer to coefficient, or NULL */
4204  int* pos2, /**< buffer to position of expr2 in quadexprterms array of quadratic expression, or NULL */
4205  SCIP_EXPR** prodexpr /**< buffer to store pointer to expression that is product if first and second factor, or NULL */
4206  )
4207 {
4208  SCIP_QUADEXPR_BILINTERM* bilinexprterm;
4209 
4210  assert(expr != NULL);
4211  assert(expr->quaddata != NULL);
4212  assert(expr->quaddata->bilinexprterms != NULL);
4213  assert(termidx >= 0);
4214  assert(termidx < expr->quaddata->nbilinexprterms);
4215 
4216  bilinexprterm = &expr->quaddata->bilinexprterms[termidx];
4217 
4218  if( expr1 != NULL )
4219  *expr1 = bilinexprterm->expr1;
4220  if( expr2 != NULL )
4221  *expr2 = bilinexprterm->expr2;
4222  if( coef != NULL )
4223  *coef = bilinexprterm->coef;
4224  if( pos2 != NULL )
4225  *pos2 = bilinexprterm->pos2;
4226  if( prodexpr != NULL )
4227  *prodexpr = bilinexprterm->prodexpr;
4228 }
4229 
4230 /** returns whether all expressions that are used in a quadratic expression are variable expressions
4231  *
4232  * @return TRUE iff all `linexprs` and `quadexprterms[.].expr` are variable expressions
4233  */
4235  SCIP_EXPR* expr /**< quadratic expression */
4236  )
4237 {
4238  assert(expr != NULL);
4239  assert(expr->quaddata != NULL);
4240 
4241  return expr->quaddata->allexprsarevars;
4242 }
4243 
4244 /** returns a monomial representation of a product expression
4245  *
4246  * The array to store all factor expressions needs to be of size the number of
4247  * children in the expression which is given by SCIPexprGetNChildren().
4248  *
4249  * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where
4250  * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can
4251  * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents.
4252  *
4253  * A non-trivial monomial is a product of a least two expressions.
4254  */
4256  SCIP_SET* set, /**< global SCIP settings */
4257  BMS_BLKMEM* blkmem, /**< block memory */
4258  SCIP_EXPR* expr, /**< expression */
4259  SCIP_Real* coef, /**< coefficient \f$c\f$ */
4260  SCIP_Real* exponents, /**< exponents \f$\alpha\f$ */
4261  SCIP_EXPR** factors /**< factor expressions \f$x\f$ */
4262  )
4263 {
4264  SCIP_EXPR* child;
4265  int c;
4266  int nexprs;
4267 
4268  assert(set != NULL);
4269  assert(blkmem != NULL);
4270  assert(expr != NULL);
4271  assert(coef != NULL);
4272  assert(exponents != NULL);
4273  assert(factors != NULL);
4274 
4275  assert(SCIPexprIsProduct(set, expr));
4276 
4277  *coef = SCIPgetCoefExprProduct(expr);
4278  nexprs = SCIPexprGetNChildren(expr);
4279 
4280  for( c = 0; c < nexprs; ++c )
4281  {
4282  child = SCIPexprGetChildren(expr)[c];
4283 
4284  if( SCIPexprIsPower(set, child) )
4285  {
4286  exponents[c] = SCIPgetExponentExprPow(child);
4287  factors[c] = SCIPexprGetChildren(child)[0];
4288  }
4289  else
4290  {
4291  exponents[c] = 1.0;
4292  factors[c] = child;
4293  }
4294  }
4295 
4296  return SCIP_OKAY;
4297 }
4298 
4299 /**@} */
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
SCIP_RETCODE SCIPexprhdlrHashExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, unsigned int *hashkey, unsigned int *childrenhashes)
Definition: expr.c:1113
SCIP_Longint SCIPexprhdlrGetNSimplifyCalls(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:827
int SCIPexprhdlrCompareExpr(SCIP_SET *set, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: expr.c:1162
#define SCIP_EXPRITER_ALLSTAGES
Definition: type_expr.h:696
SCIP_Longint SCIPexprhdlrGetNEstimateCalls(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:783
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:4113
static SCIP_RETCODE eval(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRINTDATA *exprintdata, const vector< Type > &x, Type &val)
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6269
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:1556
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:468
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:501
SCIP_EXPR_OWNERDATA * SCIPexprGetOwnerData(SCIP_EXPR *expr)
Definition: expr.c:3915
#define SCIP_DECL_EXPREVAL(x)
Definition: type_expr.h:426
void SCIPexprSetIntegrality(SCIP_EXPR *expr, SCIP_Bool isintegral)
Definition: expr.c:4083
#define SCIP_DECL_EXPRPRINT(x)
Definition: type_expr.h:289
internal methods for storing primal CIP solutions
SCIP_RETCODE SCIPexprEvalGradient(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *rootexpr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: expr.c:2745
SCIP_MONOTONE
Definition: type_expr.h:69
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:1525
#define SCIP_DECL_EXPRMONOTONICITY(x)
Definition: type_expr.h:358
#define SCIP_DECL_EXPR_INTEVALVAR(x)
Definition: type_expr.h:163
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
SCIP_Bool SCIPexprhdlrHasFwdiff(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:605
SCIP_Bool allexprsarevars
Definition: struct_expr.h:163
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
internal methods for branch and bound tree
SCIP_RETCODE SCIPexprGetSymData(SCIP_SET *set, SCIP_EXPR *expr, SYM_EXPRDATA **symdata)
Definition: expr.c:3283
SCIP_RETCODE SCIPlapackComputeEigenvalues(BMS_BUFMEM *bufmem, SCIP_Bool geteigenvectors, int N, SCIP_Real *a, SCIP_Real *w)
Definition: lapack_calls.c:352
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:2347
void SCIPmessageFPrintVerbInfo(SCIP_MESSAGEHDLR *messagehdlr, SCIP_VERBLEVEL verblevel, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: message.c:706
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
#define SCIP_EXPRPRINT_NUSES
Definition: type_expr.h:730
SCIP_Real SCIPsetFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6456
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3854
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:740
SCIP_EXPRCURV curvature
Definition: struct_expr.h:165
#define SCIP_DECL_EXPRINITESTIMATES(x)
Definition: type_expr.h:608
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:473
SCIP_EXPR_OWNERDATA * ownerdata
Definition: struct_expr.h:118
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:545
internal methods for clocks and timing issues
SCIP_RETCODE SCIPexprhdlrCopyInclude(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *targetset)
Definition: expr.c:859
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6392
SCIP_EXPR ** linexprs
Definition: struct_expr.h:154
unsigned int ncreated
Definition: struct_expr.h:74
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:422
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1567
SCIP_Longint evaltag
Definition: struct_expr.h:128
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:930
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:3189
#define SCIP_DECL_EXPRFWDIFF(x)
Definition: type_expr.h:480
SCIP_RETCODE SCIPexprhdlrBwFwDiffExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, int childidx, SCIP_Real *bardot, SCIP_SOL *direction)
Definition: expr.c:1489
#define SCIP_EXPRPRINT_EVALTAG
Definition: type_expr.h:732
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3560
SCIP_Real constant
Definition: struct_expr.h:151
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:2844
#define SCIP_DECL_EXPRREVERSEPROP(x)
Definition: type_expr.h:657
SCIP_RETCODE SCIPexprPrintDotInit(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
Definition: expr.c:2315
SCIP_EXPRCURV curvature
Definition: struct_expr.h:138
void SCIPexprhdlrSetGetSymdata(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRGETSYMDATA((*getsymdata)))
Definition: expr.c:521
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
Definition: expr.c:407
structure definitions related to algebraic expressions
void SCIPexprhdlrInit(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set)
Definition: expr.c:884
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
private functions to work with algebraic expressions
SCIP_EXPRHDLRDATA * SCIPexprhdlrGetData(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:575
#define FALSE
Definition: def.h:94
SCIP_RETCODE SCIPexprRemoveChildren(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:1846
SCIP_Bool SCIPexprhdlrHasPrint(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:585
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
void SCIPexprSetCurvature(SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
Definition: expr.c:4062
SCIP_Bool SCIPexprhdlrHasBwdiff(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:595
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:54
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition: expr_pow.c:3457
#define TRUE
Definition: def.h:93
static SCIP_RETCODE quadDetectProcessExpr(SCIP_EXPR *expr, SCIP_HASHMAP *seenexpr, int *nquadterms, int *nlinterms)
Definition: expr.c:105
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Longint nsimplifycalls
Definition: struct_expr.h:80
SCIP_Real SCIPexprhdlrGetEstimateTime(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:793
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
SCIP_Longint nintevalcalls
Definition: struct_expr.h:76
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition: type_expr.h:741
static SCIP_RETCODE quadDetectGetQuadexprterm(BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_HASHMAP *expr2idx, SCIP_HASHMAP *seenexpr, SCIP_QUADEXPR *quadexpr, SCIP_QUADEXPR_QUADTERM **quadexprterm)
Definition: expr.c:145
#define SCIP_EXPRPRINT_EXPRSTRING
Definition: type_expr.h:728
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5834
SCIP_RETCODE SCIPexprDismantle(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_EXPR *expr)
Definition: expr.c:2546
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:451
SCIP_Longint exprlastdifftag
Definition: struct_stat.h:128
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:4010
SCIP_EXPRITER_USERDATA SCIPexpriterGetChildUserDataDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:771
public methods for problem variables
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:440
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP_RETCODE SCIPexprPrintDotFinal(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRPRINTDATA **printdata)
Definition: expr.c:2493
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6403
SCIP_Real SCIPexprhdlrGetSimplifyTime(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:837
#define BMSallocClearBufferMemoryArray(mem, ptr, num)
Definition: memory.h:732
SCIP_RETCODE SCIPexprhdlrBwDiffExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, BMS_BUFMEM *bufmem, SCIP_EXPR *expr, int childidx, SCIP_Real *derivative, SCIP_Real *childrenvals, SCIP_Real exprval)
Definition: expr.c:1272
SCIP_EXPRITER_USERDATA SCIPexpriterGetCurrentUserData(SCIP_EXPRITER *iterator)
Definition: expriter.c:756
#define SCIP_DECL_EXPRGETSYMDATA(x)
Definition: type_expr.h:672
SCIP_Real SCIPexprhdlrGetIntevalTime(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:721
#define SCIP_DECL_EXPRFREEDATA(x)
Definition: type_expr.h:268
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:692
SCIP_RETCODE SCIPexprhdlrIntegralityExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_Bool *isintegral)
Definition: expr.c:1083
#define SCIP_EXPRITER_VISITEDCHILD
Definition: type_expr.h:694
SCIP_Bool SCIPexprAreQuadraticExprsVariables(SCIP_EXPR *expr)
Definition: expr.c:4234
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:3629
SCIP_EXPRHDLR * SCIPsetFindExprhdlr(SCIP_SET *set, const char *name)
Definition: set.c:5180
SCIP_Real SCIPsetCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6467
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:683
Definition: heur_padm.c:134
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition: type_expr.h:80
SCIP_RETCODE SCIPexprPrint(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_EXPR *expr)
Definition: expr.c:2266
unsigned int precedence
Definition: struct_expr.h:48
int nchildren
Definition: struct_expr.h:110
#define SCIP_EXPRPRINT_ACTIVITY
Definition: type_expr.h:733
SCIP * scip
Definition: struct_set.h:76
void SCIPexpriterFree(SCIP_EXPRITER **iterator)
Definition: expriter.c:446
#define SCIP_EXPRPRINT_ACTIVITYTAG
Definition: type_expr.h:734
SCIP_RETCODE SCIPexprPrintDot(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
Definition: expr.c:2379
SCIP_Bool isintegral
Definition: struct_expr.h:141
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition: expriter.c:790
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3887
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3864
SCIP_QUADEXPR_QUADTERM * quadexprterms
Definition: struct_expr.h:158
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:462
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1552
#define SCIP_DECL_EXPRPARSE(x)
Definition: type_expr.h:312
SCIP_Longint SCIPexprGetActivityTag(SCIP_EXPR *expr)
Definition: expr.c:4026
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3928
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:147
SCIP_RETCODE SCIPexprhdlrReversePropExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_INTERVAL bounds, SCIP_INTERVAL *childrenbounds, SCIP_Bool *infeasible)
Definition: expr.c:1680
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition: expr.c:3954
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
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:1600
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:1635
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:209
SCIP_Bool SCIPexprhdlrHasMonotonicity(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:665
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:427
SCIP_Longint SCIPexprhdlrGetNSimplifications(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:847
SCIP_Bool SCIPexprhdlrHasEstimate(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:625
SCIP_CLOCK * estimatetime
Definition: struct_expr.h:84
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_CLOCK * simplifytime
Definition: struct_expr.h:87
SCIP_Bool SCIPexprhdlrHasGetSymData(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:685
#define BMSallocBufferMemoryArray(mem, ptr, num)
Definition: memory.h:731
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void SCIPmessagePrintWarning(SCIP_MESSAGEHDLR *messagehdlr, const char *formatstr,...)
Definition: message.c:427
#define BMSallocClearBlockMemoryArray(mem, ptr, num)
Definition: memory.h:455
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:4158
SCIP_Real SCIPsetFrac(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6489
SCIP_CLOCK * intevaltime
Definition: struct_expr.h:85
SCIP_Real SCIPexprGetBardot(SCIP_EXPR *expr)
Definition: expr.c:3982
SCIP_INTERVAL activity
Definition: struct_expr.h:134
SCIP_Longint SCIPexprGetDiffTag(SCIP_EXPR *expr)
Definition: expr.c:3997
SCIP_EXPRDATA * exprdata
Definition: struct_expr.h:108
SCIP_Real SCIPexprGetDot(SCIP_EXPR *expr)
Definition: expr.c:3968
SCIP_Longint npropcalls
Definition: struct_expr.h:77
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:380
#define SCIP_DECL_EXPRFREEHDLR(x)
Definition: type_expr.h:224
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:707
#define SCIP_EXPRPRINT_OWNER
Definition: type_expr.h:735
SCIP_Bool SCIPexprIsVar(SCIP_SET *set, SCIP_EXPR *expr)
Definition: expr.c:2206
SCIP_Bool SCIPexprhdlrHasCurvature(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:655
SCIP_Longint SCIPexprGetEvalTag(SCIP_EXPR *expr)
Definition: expr.c:3941
SCIP_Bool SCIPexprhdlrHasIntEval(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:615
SCIP_Real * lincoefs
Definition: struct_expr.h:155
SCIP_CLOCK * proptime
Definition: struct_expr.h:86
SCIP_RETCODE SCIPexprhdlrFwDiffExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_Real *dot, SCIP_SOL *direction)
Definition: expr.c:1345
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:370
SCIP_RETCODE SCIPexprReplaceChild(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition: expr.c:1816
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:305
#define SCIP_INTERVAL_INFINITY
Definition: def.h:195
#define SCIP_EXPRPRINT_EVALVALUE
Definition: type_expr.h:731
SCIP_EXPRCURV SCIPexprGetCurvature(SCIP_EXPR *expr)
Definition: expr.c:4052
unsigned int SCIP_EXPRPRINT_WHAT
Definition: type_expr.h:740
interface methods for lapack functions
SCIP_Bool eigeninfostored
Definition: struct_expr.h:169
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:143
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
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:1728
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
public data structures and miscellaneous methods
#define SCIP_DECL_EXPRINTEVAL(x)
Definition: type_expr.h:539
void SCIPexprFreeQuadratic(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition: expr.c:3583
int childrensize
Definition: struct_expr.h:111
#define SCIP_Bool
Definition: def.h:91
#define SCIP_EXPRPRINT_EXPRHDLR
Definition: type_expr.h:729
SCIP_Bool SCIPexprhdlrHasReverseProp(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:675
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:454
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:143
SCIP_Longint nbranchscores
Definition: struct_expr.h:82
SCIP_EXPRCURV
Definition: type_expr.h:60
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:429
SCIP_Longint SCIPexprhdlrGetNCutoffs(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:751
#define SCIP_DECL_EXPRINTEGRALITY(x)
Definition: type_expr.h:375
static SCIP_RETCODE freeExpr(BMS_BLKMEM *blkmem, SCIP_EXPR **expr)
Definition: expr.c:74
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
SCIP_Longint nestimatecalls
Definition: struct_expr.h:75
#define BMSfreeBlockMemoryArray(mem, ptr, num)
Definition: memory.h:467
void SCIPexprCapture(SCIP_EXPR *expr)
Definition: expr.c:2064
#define SCIP_DECL_EXPRBWDIFF(x)
Definition: type_expr.h:449
SCIP_EXPR ** children
Definition: struct_expr.h:112
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:917
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:510
#define SCIPsetDebugMsg
Definition: set.h:1784
SCIP_Longint SCIPexprhdlrGetNDomainReductions(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:761
SCIP_Bool SCIPexprIsIntegral(SCIP_EXPR *expr)
Definition: expr.c:4073
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:858
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:721
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:195
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3877
datastructures for problem statistics
SCIP_Bool curvaturechecked
Definition: struct_expr.h:166
void SCIPexprhdlrSetPrint(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPRINT((*print)))
Definition: expr.c:396
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:383
SCIP_RETCODE SCIPexprEval(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: expr.c:2654
SCIP_Longint difftag
Definition: struct_expr.h:129
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:2033
#define SCIP_DECL_EXPRCURVATURE(x)
Definition: type_expr.h:340
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:664
SCIP_Longint SCIPexprhdlrGetNIntevalCalls(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:711
SCIP_Longint nsimplified
Definition: struct_expr.h:81
#define SCIP_DECL_EXPRCOMPARE(x)
Definition: type_expr.h:410
SCIP_Real * eigenvectors
Definition: struct_expr.h:171
void SCIPexprhdlrSetCompare(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOMPARE((*compare)))
Definition: expr.c:462
#define SCIP_DECL_EXPRSIMPLIFY(x)
Definition: type_expr.h:632
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_Longint ncutoffs
Definition: struct_expr.h:78
SCIP_Bool SCIPexprIsSum(SCIP_SET *set, SCIP_EXPR *expr)
Definition: expr.c:2230
static SCIP_RETCODE evalAndDiff(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag, SCIP_SOL *direction)
Definition: expr.c:188
SCIP_Longint SCIPexprhdlrGetNReversepropCalls(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:731
SCIP_EXPRHDLR * exprhdlr
Definition: struct_expr.h:107
unsigned int SCIPexprhdlrGetPrecedence(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:565
SCIP_RETCODE SCIPexprCheckQuadratic(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition: expr.c:3315
SCIP_Longint domchgcount
Definition: struct_stat.h:114
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:418
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3902
SCIP_QUADEXPR_BILINTERM * bilinexprterms
Definition: struct_expr.h:161
SCIP_Bool SCIPexprhdlrHasInitEstimates(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:635
void SCIPexprhdlrIncrementNDomainReductions(SCIP_EXPRHDLR *exprhdlr, int nreductions)
Definition: expr.c:771
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:696
void SCIPexpriterSetCurrentUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition: expriter.c:806
SCIP_Longint SCIPexprhdlrGetNBranchings(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:807
public methods for message output
SCIP_Bool SCIPexprIsValue(SCIP_SET *set, SCIP_EXPR *expr)
Definition: expr.c:2218
int SCIPexprCompare(SCIP_SET *set, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: expr.c:3082
void SCIPmessageFPrintInfo(SCIP_MESSAGEHDLR *messagehdlr, FILE *file, const char *formatstr,...)
Definition: message.c:618
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
Definition: expr.c:4198
#define SCIP_DECL_EXPRESTIMATE(x)
Definition: type_expr.h:575
#define SCIP_DECL_EXPR_MAPEXPR(x)
Definition: type_expr.h:182
SCIP_Real * eigenvalues
Definition: struct_expr.h:170
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:986
#define SCIP_Real
Definition: def.h:173
SCIP_RETCODE SCIPexprhdlrFree(SCIP_EXPRHDLR **exprhdlr, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: expr.c:340
#define SCIPsetDebugMsgPrint
Definition: set.h:1785
void SCIPexprSetActivity(SCIP_EXPR *expr, SCIP_INTERVAL activity, SCIP_Longint activitytag)
Definition: expr.c:4036
SCIP_RETCODE SCIPexprEvalActivity(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *rootexpr)
Definition: expr.c:2950
#define SCIP_EXPR_MAXINITESTIMATES
Definition: type_expr.h:198
SCIP_Real derivative
Definition: struct_expr.h:125
#define SCIP_INVALID
Definition: def.h:193
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:1205
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:294
unsigned int SCIPexprhdlrGetNCreated(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:701
#define SCIP_Longint
Definition: def.h:158
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:1386
SCIP_Longint ndomreds
Definition: struct_expr.h:79
SCIP_Real SCIPexprhdlrGetReversepropTime(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:741
#define SCIPisFinite(x)
Definition: pub_misc.h:1933
SCIP_Real evalvalue
Definition: struct_expr.h:124
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition: misc.c:10347
#define SCIP_EXPRITER_LEAVEEXPR
Definition: type_expr.h:695
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:532
SCIP_Real bardot
Definition: struct_expr.h:127
SCIP_RETCODE SCIPexprAppendChild(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition: expr.c:1785
SCIP_QUADEXPR * quaddata
Definition: struct_expr.h:144
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:699
const char * SCIPexprhdlrGetDescription(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:555
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
SCIP_DECL_SORTPTRCOMP(SCIPexprhdlrComp)
Definition: expr.c:695
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
#define SCIP_EXPRITER_VISITINGCHILD
Definition: type_expr.h:693
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_Bool SCIPexprIsProduct(SCIP_SET *set, SCIP_EXPR *expr)
Definition: expr.c:2242
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:969
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_EXPRHDLRDATA * data
Definition: struct_expr.h:47
SCIP_RETCODE SCIPexprRelease(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR **rootexpr)
Definition: expr.c:2074
SCIP_Bool SCIPexprhdlrHasSimplify(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:645
SCIP_RETCODE SCIPexprGetMonomialData(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)
Definition: expr.c:4255
SCIP_RETCODE SCIPexprhdlrCurvatureExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_EXPRCURV exprcurvature, SCIP_Bool *success, SCIP_EXPRCURV *childcurv)
Definition: expr.c:1025
#define SCIP_DECL_EXPRCOPYHDLR(x)
Definition: type_expr.h:210
#define SCIP_ALLOC(x)
Definition: def.h:391
#define BMSallocClearBlockMemory(mem, ptr)
Definition: memory.h:452
#define SCIPABORT()
Definition: def.h:352
#define BMSfreeBufferMemoryArray(mem, ptr)
Definition: memory.h:742
SCIP_Real dot
Definition: struct_expr.h:126
void SCIPexprhdlrIncrementNBranchings(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:817
int SCIPexprGetNUses(SCIP_EXPR *expr)
Definition: expr.c:3844
datastructures for global SCIP settings
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:499
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:488
#define SCIP_DECL_EXPRCOPYDATA(x)
Definition: type_expr.h:249
SCIP_Bool SCIPlapackIsAvailable(void)
Definition: lapack_calls.c:121
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:1878
#define SCIP_DECL_EXPRHASH(x)
Definition: type_expr.h:391
SCIP_Bool SCIPexprIsPower(SCIP_SET *set, SCIP_EXPR *expr)
Definition: expr.c:2254
SCIP_Bool quadchecked
Definition: struct_expr.h:145
#define SCIP_DECL_EXPRBWFWDIFF(x)
Definition: type_expr.h:520
SCIP_RETCODE SCIPexprhdlrMonotonicityExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, int childidx, SCIP_MONOTONE *result)
Definition: expr.c:1054
SCIP_Longint activitytag
Definition: struct_expr.h:135