Scippy

SCIP

Solving Constraint Integer Programs

pub_expr.h
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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file nlpi/pub_expr.h
17  * @brief public methods for expressions, expression trees, expression graphs, and related stuff
18  * @author Stefan Vigerske
19  * @author Thorsten Gellermann
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __NLPI_PUB_EXPR_H__
25 #define __NLPI_PUB_EXPR_H__
26 
27 #include "scip/def.h"
28 #include "scip/pub_message.h"
29 #include "scip/intervalarith.h"
30 #include "blockmemshell/memory.h"
31 #include "nlpi/type_expr.h"
32 #include "nlpi/type_exprinterpret.h"
33 
34 #ifdef NDEBUG
35 #include "nlpi/struct_expr.h"
36 #endif
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 /**@name Expression curvature methods */
43 /**@{ */
44 
45 /** gives curvature for a sum of two functions with given curvature */
46 extern
47 SCIP_EXPRCURV SCIPexprcurvAdd(
48  SCIP_EXPRCURV curv1, /**< curvature of first summand */
49  SCIP_EXPRCURV curv2 /**< curvature of second summand */
50  );
51 
52 #ifdef NDEBUG
53 #define SCIPexprcurvAdd(curv1, curv2) ((SCIP_EXPRCURV) ((curv1) & (curv2)))
54 #endif
55 
56 /** gives the curvature for the negation of a function with given curvature */
57 extern
58 SCIP_EXPRCURV SCIPexprcurvNegate(
59  SCIP_EXPRCURV curvature /**< curvature of function */
60  );
61 
62 /** gives curvature for a functions with given curvature multiplied by a constant factor */
63 extern
64 SCIP_EXPRCURV SCIPexprcurvMultiply(
65  SCIP_Real factor, /**< constant factor */
66  SCIP_EXPRCURV curvature /**< curvature of other factor */
67  );
68 
69 /** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */
70 extern
71 SCIP_EXPRCURV SCIPexprcurvPower(
72  SCIP_INTERVAL basebounds, /**< bounds on base function */
73  SCIP_EXPRCURV basecurv, /**< curvature of base function */
74  SCIP_Real exponent /**< exponent */
75  );
76 
77 /** gives curvature for a monomial with given curvatures and bounds for each factor */
78 extern
79 SCIP_EXPRCURV SCIPexprcurvMonomial(
80  int nfactors, /**< number of factors in monomial */
81  SCIP_Real* exponents, /**< exponents in monomial, or NULL if all 1.0 */
82  int* factoridxs, /**< indices of factors, or NULL if identity mapping */
83  SCIP_EXPRCURV* factorcurv, /**< curvature of each factor */
84  SCIP_INTERVAL* factorbounds /**< bounds of each factor */
85  );
86 
87 /** gives name as string for a curvature */
88 extern
89 const char* SCIPexprcurvGetName(
90  SCIP_EXPRCURV curv /**< curvature */
91  );
92 
93 /**@} */
94 
95 /**@name Expression operand methods */
96 /**@{ */
97 
98 /** gives the name of an operand */
99 extern
100 const char* SCIPexpropGetName(
101  SCIP_EXPROP op /**< expression operand */
102  );
103 
104 /** gives the number of children of a simple operand
105  * @return -1 for invalid operands and -2 for complex operands (those where the number of children depends on the expression)
106  */
107 extern
108 int SCIPexpropGetNChildren(
109  SCIP_EXPROP op /**< expression operand */
110  );
111 
112 /**@} */
113 
114 /**@name Expression methods */
115 /**@{ */
116 
117 /** gives operator of expression */
118 extern
119 SCIP_EXPROP SCIPexprGetOperator(
120  SCIP_EXPR* expr /**< expression */
121  );
122 
123 /** gives number of children of an expression */
124 extern
125 int SCIPexprGetNChildren(
126  SCIP_EXPR* expr /**< expression */
127  );
128 
129 /** gives pointer to array with children of an expression */
130 extern
131 SCIP_EXPR** SCIPexprGetChildren(
132  SCIP_EXPR* expr /**< expression */
133  );
134 
135 /** gives index belonging to a SCIP_EXPR_VARIDX or SCIP_EXPR_PARAM operand */
136 extern
137 int SCIPexprGetOpIndex(
138  SCIP_EXPR* expr /**< expression */
139  );
140 
141 /** gives real belonging to a SCIP_EXPR_CONST operand */
142 extern
143 SCIP_Real SCIPexprGetOpReal(
144  SCIP_EXPR* expr /**< expression */
145  );
146 
147 /** gives void* belonging to a complex operand */
148 extern
149 void* SCIPexprGetOpData(
150  SCIP_EXPR* expr /**< expression */
151  );
152 
153 /** gives exponent belonging to a SCIP_EXPR_REALPOWER expression */
154 extern
155 SCIP_Real SCIPexprGetRealPowerExponent(
156  SCIP_EXPR* expr /**< expression */
157  );
158 
159 /** gives exponent belonging to a SCIP_EXPR_INTPOWER expression */
160 extern
161 int SCIPexprGetIntPowerExponent(
162  SCIP_EXPR* expr /**< expression */
163  );
164 
165 /** gives exponent belonging to a SCIP_EXPR_SIGNPOWER expression */
166 extern
167 SCIP_Real SCIPexprGetSignPowerExponent(
168  SCIP_EXPR* expr /**< expression */
169  );
170 
171 /** gives linear coefficients belonging to a SCIP_EXPR_LINEAR expression */
172 extern
173 SCIP_Real* SCIPexprGetLinearCoefs(
174  SCIP_EXPR* expr /**< expression */
175  );
176 
177 /** gives constant belonging to a SCIP_EXPR_LINEAR expression */
178 extern
179 SCIP_Real SCIPexprGetLinearConstant(
180  SCIP_EXPR* expr /**< expression */
181  );
182 
183 /** gives quadratic elements belonging to a SCIP_EXPR_QUADRATIC expression */
184 extern
185 SCIP_QUADELEM* SCIPexprGetQuadElements(
186  SCIP_EXPR* expr /**< quadratic expression */
187  );
188 
189 /** gives constant belonging to a SCIP_EXPR_QUADRATIC expression */
190 extern
191 SCIP_Real SCIPexprGetQuadConstant(
192  SCIP_EXPR* expr /**< quadratic expression */
193  );
194 
195 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression
196  * can be NULL if all coefficients are 0.0 */
197 extern
198 SCIP_Real* SCIPexprGetQuadLinearCoefs(
199  SCIP_EXPR* expr /**< quadratic expression */
200  );
201 
202 /** gives number of quadratic elements belonging to a SCIP_EXPR_QUADRATIC expression */
203 extern
204 int SCIPexprGetNQuadElements(
205  SCIP_EXPR* expr /**< quadratic expression */
206  );
207 
208 /** gives the monomials belonging to a SCIP_EXPR_POLYNOMIAL expression */
209 extern
210 SCIP_EXPRDATA_MONOMIAL** SCIPexprGetMonomials(
211  SCIP_EXPR* expr /**< expression */
212  );
213 
214 /** gives the number of monomials belonging to a SCIP_EXPR_POLYNOMIAL expression */
215 extern
216 int SCIPexprGetNMonomials(
217  SCIP_EXPR* expr /**< expression */
218  );
219 
220 /** gives the constant belonging to a SCIP_EXPR_POLYNOMIAL expression */
221 extern
222 SCIP_Real SCIPexprGetPolynomialConstant(
223  SCIP_EXPR* expr /**< expression */
224  );
225 
226 /** gets coefficient of a monomial */
227 extern
228 SCIP_Real SCIPexprGetMonomialCoef(
229  SCIP_EXPRDATA_MONOMIAL* monomial /**< monomial */
230  );
231 
232 /** gets number of factors of a monomial */
233 extern
234 int SCIPexprGetMonomialNFactors(
235  SCIP_EXPRDATA_MONOMIAL* monomial /**< monomial */
236  );
237 
238 /** gets indices of children corresponding to factors of a monomial */
239 extern
240 int* SCIPexprGetMonomialChildIndices(
241  SCIP_EXPRDATA_MONOMIAL* monomial /**< monomial */
242  );
243 
244 /** gets exponents in factors of a monomial */
245 extern
246 SCIP_Real* SCIPexprGetMonomialExponents(
247  SCIP_EXPRDATA_MONOMIAL* monomial /**< monomial */
248  );
249 
250 #ifdef NDEBUG
251 
252 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
253  * speed up the algorithms.
254  */
255 
256 #define SCIPexprGetOperator(expr) (expr)->op
257 #define SCIPexprGetNChildren(expr) (expr)->nchildren
258 #define SCIPexprGetChildren(expr) (expr)->children
259 #define SCIPexprGetOpIndex(expr) (expr)->data.intval
260 #define SCIPexprGetOpReal(expr) (expr)->data.dbl
261 #define SCIPexprGetOpData(expr) (expr)->data.data
262 #define SCIPexprGetRealPowerExponent(expr) (expr)->data.dbl
263 #define SCIPexprGetIntPowerExponent(expr) (expr)->data.intval
264 #define SCIPexprGetSignPowerExponent(expr) (expr)->data.dbl
265 #define SCIPexprGetLinearCoefs(expr) ((SCIP_Real*)(expr)->data.data)
266 #define SCIPexprGetLinearConstant(expr) (((SCIP_Real*)(expr)->data.data)[(expr)->nchildren])
267 #define SCIPexprGetQuadElements(expr) ((SCIP_EXPRDATA_QUADRATIC*)(expr)->data.data)->quadelems
268 #define SCIPexprGetQuadConstant(expr) ((SCIP_EXPRDATA_QUADRATIC*)(expr)->data.data)->constant
269 #define SCIPexprGetQuadLinearCoefs(expr) ((SCIP_EXPRDATA_QUADRATIC*)(expr)->data.data)->lincoefs
270 #define SCIPexprGetNQuadElements(expr) ((SCIP_EXPRDATA_QUADRATIC*)(expr)->data.data)->nquadelems
271 #define SCIPexprGetMonomials(expr) ((SCIP_EXPRDATA_POLYNOMIAL*)(expr)->data.data)->monomials
272 #define SCIPexprGetNMonomials(expr) ((SCIP_EXPRDATA_POLYNOMIAL*)(expr)->data.data)->nmonomials
273 #define SCIPexprGetPolynomialConstant(expr) ((SCIP_EXPRDATA_POLYNOMIAL*)(expr)->data.data)->constant
274 #define SCIPexprGetMonomialCoef(monomial) (monomial)->coef
275 #define SCIPexprGetMonomialNFactors(monomial) (monomial)->nfactors
276 #define SCIPexprGetMonomialChildIndices(monomial) (monomial)->childidxs
277 #define SCIPexprGetMonomialExponents(monomial) (monomial)->exponents
278 
279 #endif
280 
281 /** creates a simple expression */
282 extern
283 SCIP_RETCODE SCIPexprCreate(
284  BMS_BLKMEM* blkmem, /**< block memory data structure */
285  SCIP_EXPR** expr, /**< pointer to buffer for expression address */
286  SCIP_EXPROP op, /**< operand of expression */
287  ... /**< arguments of operand */
288  );
289 
290 /** copies an expression including its children */
291 extern
292 SCIP_RETCODE SCIPexprCopyDeep(
293  BMS_BLKMEM* blkmem, /**< block memory data structure */
294  SCIP_EXPR** targetexpr, /**< buffer to store pointer to copied expression */
295  SCIP_EXPR* sourceexpr /**< expression to copy */
296  );
297 
298 /** frees an expression including its children */
299 extern
300 void SCIPexprFreeDeep(
301  BMS_BLKMEM* blkmem, /**< block memory data structure */
302  SCIP_EXPR** expr /**< pointer to expression to free */
303  );
304 
305 /** frees an expression but not its children */
306 extern
307 void SCIPexprFreeShallow(
308  BMS_BLKMEM* blkmem, /**< block memory data structure */
309  SCIP_EXPR** expr /**< pointer to expression to free */
310  );
311 
312 /** creates an expression from the addition of two given expression, with coefficients, and a constant
313  *
314  * the given expressions may be modified or freed, otherwise it will be used a child expression
315  * favors creation and maintaining of SCIP_EXPR_LINEAR over SCIP_EXPR_PLUS or SCIP_EXPR_SUM
316  */
317 extern
318 SCIP_RETCODE SCIPexprAdd(
319  BMS_BLKMEM* blkmem, /**< block memory data structure */
320  SCIP_EXPR** expr, /**< pointer to store pointer to created expression */
321  SCIP_Real coef1, /**< coefficient of first term */
322  SCIP_EXPR* term1, /**< expression of first term, or NULL */
323  SCIP_Real coef2, /**< coefficient of second term */
324  SCIP_EXPR* term2, /**< expression of second term, or NULL */
325  SCIP_Real constant /**< constant term to add */
326  );
327 
328 /** creates an expression from the multiplication of an expression with a constant
329  *
330  * the given expressions may be modified or freed, otherwise it will be used a child expression
331  * favors creation of SCIP_EXPR_LINEAR over SCIP_EXPR_MUP or SCIP_EXPR_PROD
332  */
333 extern
334 SCIP_RETCODE SCIPexprMulConstant(
335  BMS_BLKMEM* blkmem, /**< block memory data structure */
336  SCIP_EXPR** expr, /**< buffer to store pointer to created expression */
337  SCIP_EXPR* term, /**< term to multiply by factor */
338  SCIP_Real factor /**< factor */
339  );
340 
341 /** creates a SCIP_EXPR_LINEAR expression that is (affine) linear in its children: constant + sum_i coef_i child_i */
342 extern
343 SCIP_RETCODE SCIPexprCreateLinear(
344  BMS_BLKMEM* blkmem, /**< block memory data structure */
345  SCIP_EXPR** expr, /**< pointer to buffer for expression address */
346  int nchildren, /**< number of children */
347  SCIP_EXPR** children, /**< children of expression */
348  SCIP_Real* coefs, /**< coefficients of children */
349  SCIP_Real constant /**< constant part */
350  );
351 
352 /** adds new terms to a linear expression */
353 extern
354 SCIP_RETCODE SCIPexprAddToLinear(
355  BMS_BLKMEM* blkmem, /**< block memory */
356  SCIP_EXPR* expr, /**< linear expression */
357  int nchildren, /**< number of children to add */
358  SCIP_Real* coefs, /**< coefficients of additional children */
359  SCIP_EXPR** children, /**< additional children expressions */
360  SCIP_Real constant /**< constant to add */
361  );
362 
363 /** creates a SCIP_EXPR_QUADRATIC expression: constant + sum_i coef_i child_i + sum_i coef_i child1_i child2_i */
364 SCIP_RETCODE SCIPexprCreateQuadratic(
365  BMS_BLKMEM* blkmem, /**< block memory data structure */
366  SCIP_EXPR** expr, /**< pointer to buffer for expression address */
367  int nchildren, /**< number of children */
368  SCIP_EXPR** children, /**< children of expression */
369  SCIP_Real constant, /**< constant */
370  SCIP_Real* lincoefs, /**< linear coefficients of children, or NULL if all 0.0 */
371  int nquadelems, /**< number of quadratic elements */
372  SCIP_QUADELEM* quadelems /**< quadratic elements specifying coefficients and child indices */
373  );
374 
375 /** ensures that quadratic elements of a quadratic expression are sorted */
376 extern
377 void SCIPexprSortQuadElems(
378  SCIP_EXPR* expr /**< quadratic expression */
379  );
380 
381 /** creates a SCIP_EXPR_POLYNOMIAL expression from an array of monomials: constant + sum_i monomial_i */
382 extern
383 SCIP_RETCODE SCIPexprCreatePolynomial(
384  BMS_BLKMEM* blkmem, /**< block memory data structure */
385  SCIP_EXPR** expr, /**< pointer to buffer for expression address */
386  int nchildren, /**< number of children */
387  SCIP_EXPR** children, /**< children of expression */
388  int nmonomials, /**< number of monomials */
389  SCIP_EXPRDATA_MONOMIAL** monomials, /**< monomials */
390  SCIP_Real constant, /**< constant part */
391  SCIP_Bool copymonomials /**< should monomials by copied or ownership be assumed? */
392  );
393 
394 /** adds an array of monomials to a SCIP_EXPR_POLYNOMIAL expression */
395 extern
396 SCIP_RETCODE SCIPexprAddMonomials(
397  BMS_BLKMEM* blkmem, /**< block memory of expression */
398  SCIP_EXPR* expr, /**< expression */
399  int nmonomials, /**< number of monomials to add */
400  SCIP_EXPRDATA_MONOMIAL** monomials, /**< the monomials to add */
401  SCIP_Bool copymonomials /**< should monomials by copied or ownership be assumed? */
402  );
403 
404 /** changes the constant in a SCIP_EXPR_POLYNOMIAL expression */
405 extern
406 void SCIPexprChgPolynomialConstant(
407  SCIP_EXPR* expr, /**< expression */
408  SCIP_Real constant /**< new value for constant */
409  );
410 
411 /** multiplies each summand of a polynomial by a given constant */
412 extern
413 void SCIPexprMultiplyPolynomialByConstant(
414  BMS_BLKMEM* blkmem, /**< block memory */
415  SCIP_EXPR* expr, /**< polynomial expression */
416  SCIP_Real factor /**< constant factor */
417  );
418 
419 /** multiplies each summand of a polynomial by a given monomial */
420 extern
421 SCIP_RETCODE SCIPexprMultiplyPolynomialByMonomial(
422  BMS_BLKMEM* blkmem, /**< block memory */
423  SCIP_EXPR* expr, /**< polynomial expression */
424  SCIP_EXPRDATA_MONOMIAL* factor, /**< monomial factor */
425  int* childmap /**< map children in factor to children in expr, or NULL for 1:1 */
426  );
427 
428 /** multiplies this polynomial by a polynomial
429  * factor needs to be different from expr */
430 extern
431 SCIP_RETCODE SCIPexprMultiplyPolynomialByPolynomial(
432  BMS_BLKMEM* blkmem, /**< block memory */
433  SCIP_EXPR* expr, /**< polynomial expression */
434  SCIP_EXPR* factor, /**< polynomial factor */
435  int* childmap /**< map children in factor to children in expr, or NULL for 1:1 */
436  );
437 
438 /** takes a power of the polynomial
439  * exponent need to be an integer
440  * polynomial need to be a monomial, if exponent is negative
441  */
442 extern
443 SCIP_RETCODE SCIPexprPolynomialPower(
444  BMS_BLKMEM* blkmem, /**< block memory */
445  SCIP_EXPR* expr, /**< polynomial expression */
446  int exponent /**< exponent of power operation */
447  );
448 
449 /** merges monomials in a polynomial expression that differ only in coefficient into a single monomial
450  * eliminates monomials with coefficient between -eps and eps
451  */
452 extern
453 void SCIPexprMergeMonomials(
454  BMS_BLKMEM* blkmem, /**< block memory */
455  SCIP_EXPR* expr, /**< polynomial expression */
456  SCIP_Real eps, /**< threshold under which numbers are treat as zero */
457  SCIP_Bool mergefactors /**< whether to merge factors in monomials too */
458  );
459 
460 /** creates a monomial */
461 extern
462 SCIP_RETCODE SCIPexprCreateMonomial(
463  BMS_BLKMEM* blkmem, /**< block memory */
464  SCIP_EXPRDATA_MONOMIAL** monomial, /**< buffer where to store pointer to new monomial */
465  SCIP_Real coef, /**< coefficient of monomial */
466  int nfactors, /**< number of factors in monomial */
467  int* childidxs, /**< indices of children corresponding to factors, or NULL if identity */
468  SCIP_Real* exponents /**< exponent in each factor, or NULL if all 1.0 */
469  );
470 
471 /** frees a monomial */
472 extern
473 void SCIPexprFreeMonomial(
474  BMS_BLKMEM* blkmem, /**< block memory */
475  SCIP_EXPRDATA_MONOMIAL** monomial /**< pointer to monomial that should be freed */
476  );
477 
478 /** ensures that factors in a monomial are sorted */
479 extern
480 void SCIPexprSortMonomialFactors(
481  SCIP_EXPRDATA_MONOMIAL* monomial /**< monomial */
482  );
483 
484 /** finds a factor corresponding to a given child index in a monomial
485  * note that if the factors have not been merged, the position of some factor corresponding to a given child is given
486  * returns TRUE if a factor is found, FALSE if not
487  */
488 extern
489 SCIP_Bool SCIPexprFindMonomialFactor(
490  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
491  int childidx, /**< index of the child which factor to search for */
492  int* pos /**< buffer to store position of factor */
493  );
494 
495 /** checks if two monomials are equal */
496 extern
497 SCIP_Bool SCIPexprAreMonomialsEqual(
498  SCIP_EXPRDATA_MONOMIAL* monomial1, /**< first monomial */
499  SCIP_EXPRDATA_MONOMIAL* monomial2, /**< second monomial */
500  SCIP_Real eps /**< threshold under which numbers are treated as 0.0 */
501  );
502 
503 /** adds factors to a monomial */
504 extern
505 SCIP_RETCODE SCIPexprAddMonomialFactors(
506  BMS_BLKMEM* blkmem, /**< block memory */
507  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
508  int nfactors, /**< number of factors to add */
509  int* childidxs, /**< indices of children corresponding to factors */
510  SCIP_Real* exponents /**< exponent in each factor */
511  );
512 
513 /** changes coefficient of monomial */
514 extern
515 void SCIPexprChgMonomialCoef(
516  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
517  SCIP_Real newcoef /**< new coefficient */
518  );
519 
520 /** multiplies a monomial with a monomial */
521 extern
522 SCIP_RETCODE SCIPexprMultiplyMonomialByMonomial(
523  BMS_BLKMEM* blkmem, /**< block memory */
524  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
525  SCIP_EXPRDATA_MONOMIAL* factor, /**< factor monomial */
526  int* childmap /**< map to apply to children in factor, or NULL for 1:1 */
527  );
528 
529 /** replaces the monomial by a power of the monomial
530  * allows only integers as exponent
531  */
532 extern
533 void SCIPexprMonomialPower(
534  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
535  int exponent /**< integer exponent of power operation */
536  );
537 
538 /** merges factors that correspond to the same child by adding exponents
539  * eliminates factors with exponent between -eps and eps
540  */
541 extern
542 void SCIPexprMergeMonomialFactors(
543  SCIP_EXPRDATA_MONOMIAL* monomial, /**< monomial */
544  SCIP_Real eps /**< threshold under which numbers are treated as 0.0 */
545  );
546 
547 /** ensures that monomials of a polynomial are sorted */
548 extern
549 void SCIPexprSortMonomials(
550  SCIP_EXPR* expr /**< polynomial expression */
551  );
552 
553 /** indicates whether the expression contains a SCIP_EXPR_PARAM */
554 extern
555 SCIP_Bool SCIPexprHasParam(
556  SCIP_EXPR* expr /**< expression */
557  );
558 
559 /** gets maximal degree of expression, or SCIP_EXPR_DEGREEINFINITY if not a polynomial */
560 extern
561 SCIP_RETCODE SCIPexprGetMaxDegree(
562  SCIP_EXPR* expr, /**< expression */
563  int* maxdegree /**< buffer to store maximal degree */
564  );
565 
566 /** counts usage of variables in expression */
567 extern
568 void SCIPexprGetVarsUsage(
569  SCIP_EXPR* expr, /**< expression to update */
570  int* varsusage /**< array with counters of variable usage */
571  );
572 
573 /** compares whether two expressions are the same
574  * inconclusive, i.e., may give FALSE even if expressions are equivalent (x*y != y*x)
575  */
576 extern
577 SCIP_Bool SCIPexprAreEqual(
578  SCIP_EXPR* expr1, /**< first expression */
579  SCIP_EXPR* expr2, /**< second expression */
580  SCIP_Real eps /**< threshold under which numbers are assumed to be zero */
581  );
582 
583 /** aims at simplifying an expression and splitting of a linear expression
584  * if linear variables are split off, expression interpreter data, if stored in the tree, is freed
585  */
586 extern
587 SCIP_RETCODE SCIPexprSimplify(
588  BMS_BLKMEM* blkmem, /**< block memory data structure */
589  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
590  SCIP_EXPR* expr, /**< expression */
591  SCIP_Real eps, /**< threshold, under which positive values are treat as 0 */
592  int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
593  int nvars, /**< number of variables in expression */
594  int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
595  int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
596  SCIP_Real* lincoefs /**< array to store coefficients of linear part, or NULL */
597  );
598 
599 /** evaluates an expression w.r.t. a point */
600 extern
601 SCIP_RETCODE SCIPexprEval(
602  SCIP_EXPR* expr, /**< expression */
603  SCIP_Real* varvals, /**< values for variables, can be NULL if the expression is constant */
604  SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
605  SCIP_Real* val /**< buffer to store value */
606  );
607 
608 /** evaluates an expression w.r.t. an interval */
609 extern
610 SCIP_RETCODE SCIPexprEvalInt(
611  SCIP_EXPR* expr, /**< expression */
612  SCIP_Real infinity, /**< value to use for infinity */
613  SCIP_INTERVAL* varvals, /**< interval values for variables, can be NULL if the expression is constant */
614  SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
615  SCIP_INTERVAL* val /**< buffer to store value */
616  );
617 
618 /** tries to determine the curvature type of an expression w.r.t. given variable domains */
619 extern
620 SCIP_RETCODE SCIPexprCheckCurvature(
621  SCIP_EXPR* expr, /**< expression to check */
622  SCIP_Real infinity, /**< value to use for infinity */
623  SCIP_INTERVAL* varbounds, /**< domains of variables */
624  SCIP_Real* param, /**< values for parameters, can be NULL if the expression is not parameterized */
625  SCIP_EXPRCURV* curv, /**< buffer to store curvature of expression */
626  SCIP_INTERVAL* bounds /**< buffer to store bounds on expression */
627  );
628 
629 /** substitutes variables (SCIP_EXPR_VARIDX) by expressions
630  * Note that only the children of the given expr are checked!
631  * A variable with index i is replaced by a copy of substexprs[i], if that latter is not NULL
632  * if substexprs[i] == NULL, then the variable expression i is not touched
633  */
634 extern
635 SCIP_RETCODE SCIPexprSubstituteVars(
636  BMS_BLKMEM* blkmem, /**< block memory data structure */
637  SCIP_EXPR* expr, /**< expression, which of the children may be replaced */
638  SCIP_EXPR** substexprs /**< array of substitute expressions; single entries can be NULL */
639  );
640 
641 /** updates variable indices in expression tree */
642 extern
643 void SCIPexprReindexVars(
644  SCIP_EXPR* expr, /**< expression to update */
645  int* newindices /**< new indices of variables */
646  );
647 
648 /** updates parameter indices in expression tree */
649 extern
650 void SCIPexprReindexParams(
651  SCIP_EXPR* expr, /**< expression to update */
652  int* newindices /**< new indices of variables */
653  );
654 
655 /** prints an expression */
656 extern
657 void SCIPexprPrint(
658  SCIP_EXPR* expr, /**< expression */
659  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
660  FILE* file, /**< file for printing, or NULL for stdout */
661  const char** varnames, /**< names of variables, or NULL for default names */
662  const char** paramnames, /**< names of parameters, or NULL for default names */
663  SCIP_Real* paramvals /**< values of parameters, or NULL for not printing */
664  );
665 
666 /** parses an expression from a string */
667 extern
668 SCIP_RETCODE SCIPexprParse(
669  BMS_BLKMEM* blkmem, /**< block memory data structure */
670  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
671  SCIP_EXPR** expr, /**< buffer to store pointer to created expression */
672  const char* str, /**< pointer to the string to be parsed */
673  const char* lastchar, /**< pointer to the last char of str that should be parsed */
674  int* nvars, /**< buffer to store number of variables */
675  int* varnames /**< buffer to store variable names, prefixed by index (as int) */
676  );
677 
678 /**@} */
679 
680 /**@name Expression tree methods */
681 /**@{ */
682 
683 /** returns root expression of an expression tree */
684 extern
685 SCIP_EXPR* SCIPexprtreeGetRoot(
686  SCIP_EXPRTREE* tree /**< expression tree */
687  );
688 
689 /** returns number of variables in expression tree */
690 extern
691 int SCIPexprtreeGetNVars(
692  SCIP_EXPRTREE* tree /**< expression tree */
693  );
694 
695 /** returns number of parameters in expression tree */
696 extern
697 int SCIPexprtreeGetNParams(
698  SCIP_EXPRTREE* tree /**< expression tree */
699  );
700 
701 /** returns values of parameters or NULL if none */
702 extern
703 SCIP_Real* SCIPexprtreeGetParamVals(
704  SCIP_EXPRTREE* tree /**< expression tree */
705  );
706 
707 /** sets value of a single parameter in expression tree */
708 extern
709 void SCIPexprtreeSetParamVal(
710  SCIP_EXPRTREE* tree, /**< expression tree */
711  int paramidx, /**< index of parameter */
712  SCIP_Real paramval /**< new value of parameter */
713  );
714 
715 /** gets data of expression tree interpreter, or NULL if not set */
716 extern
717 SCIP_EXPRINTDATA* SCIPexprtreeGetInterpreterData(
718  SCIP_EXPRTREE* tree /**< expression tree */
719  );
720 
721 /** sets data of expression tree interpreter */
722 extern
723 void SCIPexprtreeSetInterpreterData(
724  SCIP_EXPRTREE* tree, /**< expression tree */
725  SCIP_EXPRINTDATA* interpreterdata /**< expression interpreter data */
726  );
727 
728 /** frees data of expression tree interpreter, if any */
729 extern
730 SCIP_RETCODE SCIPexprtreeFreeInterpreterData(
731  SCIP_EXPRTREE* tree /**< expression tree */
732  );
733 
734 /** indicates whether there are parameterized constants (SCIP_EXPR_PARAM) in expression tree */
735 extern
736 SCIP_Bool SCIPexprtreeHasParam(
737  SCIP_EXPRTREE* tree /**< expression tree */
738  );
739 
740 /** Gives maximal degree of expression in expression tree.
741  * If constant expression, gives 0,
742  * if linear expression, gives 1,
743  * if polynomial expression, gives its maximal degree,
744  * otherwise (nonpolynomial nonconstant expressions) gives at least SCIP_EXPR_DEGREEINFINITY.
745  */
746 extern
747 SCIP_RETCODE SCIPexprtreeGetMaxDegree(
748  SCIP_EXPRTREE* tree, /**< expression tree */
749  int* maxdegree /**< buffer to store maximal degree */
750  );
751 
752 /** evaluates an expression tree w.r.t. a point */
753 extern
754 SCIP_RETCODE SCIPexprtreeEval(
755  SCIP_EXPRTREE* tree, /**< expression tree */
756  SCIP_Real* varvals, /**< values for variables */
757  SCIP_Real* val /**< buffer to store expression tree value */
758  );
759 
760 /** evaluates an expression tree w.r.t. an interval */
761 extern
762 SCIP_RETCODE SCIPexprtreeEvalInt(
763  SCIP_EXPRTREE* tree, /**< expression tree */
764  SCIP_Real infinity, /**< value for infinity */
765  SCIP_INTERVAL* varvals, /**< intervals for variables */
766  SCIP_INTERVAL* val /**< buffer to store expression tree value */
767  );
768 
769 /** prints an expression tree */
770 extern
771 void SCIPexprtreePrint(
772  SCIP_EXPRTREE* tree, /**< expression tree */
773  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
774  FILE* file, /**< file for printing, or NULL for stdout */
775  const char** varnames, /**< names of variables, or NULL for default names */
776  const char** paramnames /**< names of parameters, or NULL for default names */
777  );
778 
779 #ifdef NDEBUG
780 
781 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
782  * speed up the algorithms.
783  */
784 
785 #define SCIPexprtreeGetRoot(tree) (tree)->root
786 #define SCIPexprtreeGetNVars(tree) (tree)->nvars
787 #define SCIPexprtreeGetNParams(tree) (tree)->nparams
788 #define SCIPexprtreeGetParamVals(tree) (tree)->params
789 #define SCIPexprtreeSetParamVal(tree, paramidx, paramval) do { (tree)->params[(paramidx)] = paramval; } while (FALSE)
790 #define SCIPexprtreeGetInterpreterData(tree) (tree)->interpreterdata
791 #define SCIPexprtreeSetInterpreterData(tree, newinterpreterdata) do { (tree)->interpreterdata = newinterpreterdata; } while (FALSE)
792 #define SCIPexprtreeFreeInterpreterData(tree) ((tree)->interpreterdata != NULL ? SCIPexprintFreeData(&(tree)->interpreterdata) : SCIP_OKAY)
793 #define SCIPexprtreeHasParam(tree) SCIPexprHasParam((tree)->root)
794 #define SCIPexprtreeGetMaxDegree(tree, maxdegree) SCIPexprGetMaxDegree((tree)->root, maxdegree)
795 #define SCIPexprtreeEval(tree, varvals, val) SCIPexprEval((tree)->root, varvals, (tree)->params, val)
796 #define SCIPexprtreeEvalInt(tree, infinity, varvals, val) SCIPexprEvalInt((tree)->root, infinity, varvals, (tree)->params, val)
797 #define SCIPexprtreePrint(tree, messagehdlr, file, varnames, paramnames) SCIPexprPrint((tree)->root, messagehdlr, file, varnames, paramnames, (tree)->params)
798 
799 #endif
800 
801 /** creates an expression tree */
802 extern
803 SCIP_RETCODE SCIPexprtreeCreate(
804  BMS_BLKMEM* blkmem, /**< block memory data structure */
805  SCIP_EXPRTREE** tree, /**< buffer to store address of created expression tree */
806  SCIP_EXPR* root, /**< pointer to root expression, not copied deep !, can be NULL */
807  int nvars, /**< number of variables in variable mapping */
808  int nparams, /**< number of parameters in expression */
809  SCIP_Real* params /**< values for parameters, or NULL (if NULL but nparams > 0, then params is initialized with zeros) */
810  );
811 
812 /** copies an expression tree */
813 extern
814 SCIP_RETCODE SCIPexprtreeCopy(
815  BMS_BLKMEM* blkmem, /**< block memory that should be used in new expression tree */
816  SCIP_EXPRTREE** targettree, /**< buffer to store address of copied expression tree */
817  SCIP_EXPRTREE* sourcetree /**< expression tree to copy */
818  );
819 
820 /** frees an expression tree */
821 extern
822 SCIP_RETCODE SCIPexprtreeFree(
823  SCIP_EXPRTREE** tree /**< pointer to expression tree that is freed */
824  );
825 
826 /** sets number and values of all parameters in expression tree */
827 extern
828 SCIP_RETCODE SCIPexprtreeSetParams(
829  SCIP_EXPRTREE* tree, /**< expression tree */
830  int nparams, /**< number of parameters */
831  SCIP_Real* paramvals /**< values of parameters, can be NULL if nparams == 0 */
832  );
833 
834 /** gives the number of usages for each variable in the expression tree */
835 extern
836 void SCIPexprtreeGetVarsUsage(
837  SCIP_EXPRTREE* tree, /**< expression tree */
838  int* varsusage /**< array where to store for each variable how often it is used in the tree */
839  );
840 
841 /** aims at simplifying an expression and splitting of a linear expression
842  * if linear variables are split off, expression interpreter data, if stored in the tree, is freed
843  */
844 extern
845 SCIP_RETCODE SCIPexprtreeSimplify(
846  SCIP_EXPRTREE* tree, /**< expression tree */
847  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
848  SCIP_Real eps, /**< threshold, under which positive values are treat as 0 */
849  int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
850  int* nlinvars, /**< buffer to store number of linear variables in linear part, or NULL if linear part should not be separated */
851  int* linidxs, /**< array to store indices of variables in expression tree which belong to linear part, or NULL */
852  SCIP_Real* lincoefs /**< array to store coefficients of linear part, or NULL */
853  );
854 
855 /** adds an expression to the root expression of the tree
856  * the root is replaced with an SCIP_EXPR_PLUS expression which has the previous root and the given expression as children
857  */
858 extern
859 SCIP_RETCODE SCIPexprtreeAddExpr(
860  SCIP_EXPRTREE* tree, /**< expression tree */
861  SCIP_EXPR* expr, /**< expression to add to tree */
862  SCIP_Bool copyexpr /**< whether expression should be copied */
863  );
864 
865 /** tries to determine the curvature type of an expression tree w.r.t. given variable domains */
866 extern
867 SCIP_RETCODE SCIPexprtreeCheckCurvature(
868  SCIP_EXPRTREE* tree, /**< expression tree */
869  SCIP_Real infinity, /**< value for infinity */
870  SCIP_INTERVAL* varbounds, /**< domains of variables */
871  SCIP_EXPRCURV* curv, /**< buffer to store curvature of expression */
872  SCIP_INTERVAL* bounds /**< buffer to store bounds on expression, or NULL if not needed */
873  );
874 
875 /** substitutes variables (SCIP_EXPR_VARIDX) in an expression tree by expressions
876  * A variable with index i is replaced by a copy of substexprs[i], if that latter is not NULL
877  * if substexprs[i] == NULL, then the variable expression i is not touched
878  */
879 extern
880 SCIP_RETCODE SCIPexprtreeSubstituteVars(
881  SCIP_EXPRTREE* tree, /**< expression tree */
882  SCIP_EXPR** substexprs /**< array of substitute expressions; single entries can be NULL */
883  );
884 
885 /**@} */
886 
887 /**@name Quadratic element methods */
888 /**@{ */
889 
890 /** sorts an array of quadratic elements
891  * The elements are sorted such that the first index is increasing and
892  * such that among elements with the same first index, the second index is increasing.
893  * For elements with same first and second index, the order is not defined.
894  */
895 extern
896 void SCIPquadelemSort(
897  SCIP_QUADELEM* quadelems, /**< array of quadratic elements */
898  int nquadelems /**< number of quadratic elements */
899  );
900 
901 /** Finds an index pair in a sorted array of quadratic elements.
902  * If (idx1,idx2) is found in quadelems, then returns TRUE and stores position of quadratic element in *pos.
903  * If (idx1,idx2) is not found in quadelems, then returns FALSE and stores position where a quadratic element with these indices would be inserted in *pos.
904  * Assumes that idx1 <= idx2.
905  */
906 extern
907 SCIP_Bool SCIPquadelemSortedFind(
908  SCIP_QUADELEM* quadelems, /**< array of quadratic elements */
909  int idx1, /**< index of first variable in element to search for */
910  int idx2, /**< index of second variable in element to search for */
911  int nquadelems, /**< number of quadratic elements in array */
912  int* pos /**< buffer to store position of found quadratic element, or position where it would be inserted */
913  );
914 
915 /** Adds quadratic elements with same index and removes elements with coefficient 0.0.
916  * Assumes that elements have been sorted before.
917  */
918 extern
919 void SCIPquadelemSqueeze(
920  SCIP_QUADELEM* quadelems, /**< array of quadratic elements */
921  int nquadelems, /**< number of quadratic elements */
922  int* nquadelemsnew /**< pointer to store new (reduced) number of quadratic elements */
923  );
924 
925 /**@} */
926 
927 /**@name Expression graph node methods */
928 /**@{ */
929 
930 /** captures node, i.e., increases number of uses */
931 extern
932 void SCIPexprgraphCaptureNode(
933  SCIP_EXPRGRAPHNODE* node /**< expression graph node to capture */
934  );
935 
936 /** returns whether a node is currently enabled */
937 extern
938 SCIP_Bool SCIPexprgraphIsNodeEnabled(
939  SCIP_EXPRGRAPHNODE* node /**< expression graph node to enable */
940  );
941 
942 /** gets number of children of a node in an expression graph */
943 extern
944 int SCIPexprgraphGetNodeNChildren(
945  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
946  );
947 
948 /** gets children of a node in an expression graph */
949 extern
950 SCIP_EXPRGRAPHNODE** SCIPexprgraphGetNodeChildren(
951  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
952  );
953 
954 /** gets number of parents of a node in an expression graph */
955 extern
956 int SCIPexprgraphGetNodeNParents(
957  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
958  );
959 
960 /** gets parents of a node in an expression graph */
961 extern
962 SCIP_EXPRGRAPHNODE** SCIPexprgraphGetNodeParents(
963  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
964  );
965 
966 /** gets depth of node in expression graph */
967 extern
968 int SCIPexprgraphGetNodeDepth(
969  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
970  );
971 
972 /** gets position of node in expression graph at its depth level */
973 extern
974 int SCIPexprgraphGetNodePosition(
975  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
976  );
977 
978 /** gets operator of a node in an expression graph */
979 extern
980 SCIP_EXPROP SCIPexprgraphGetNodeOperator(
981  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
982  );
983 
984 /** gives index belonging to a SCIP_EXPR_VARIDX or SCIP_EXPR_PARAM operand */
985 extern
986 int SCIPexprgraphGetNodeOperatorIndex(
987  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
988  );
989 
990 /** gives real belonging to a SCIP_EXPR_CONST operand */
991 extern
992 SCIP_Real SCIPexprgraphGetNodeOperatorReal(
993  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
994  );
995 
996 /** gives variable belonging to a SCIP_EXPR_VARIDX expression */
997 extern
998 void* SCIPexprgraphGetNodeVar(
999  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1000  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1001  );
1002 
1003 /** gives exponent belonging to a SCIP_EXPR_REALPOWER expression */
1004 extern
1005 SCIP_Real SCIPexprgraphGetNodeRealPowerExponent(
1006  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1007  );
1008 
1009 /** gives exponent belonging to a SCIP_EXPR_INTPOWER expression */
1010 extern
1011 int SCIPexprgraphGetNodeIntPowerExponent(
1012  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1013  );
1014 
1015 /** gives exponent belonging to a SCIP_EXPR_SIGNPOWER expression */
1016 extern
1017 SCIP_Real SCIPexprgraphGetNodeSignPowerExponent(
1018  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1019  );
1020 
1021 /** gives linear coefficients belonging to a SCIP_EXPR_LINEAR expression */
1022 extern
1023 SCIP_Real* SCIPexprgraphGetNodeLinearCoefs(
1024  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1025  );
1026 
1027 /** gives constant belonging to a SCIP_EXPR_LINEAR expression */
1028 extern
1029 SCIP_Real SCIPexprgraphGetNodeLinearConstant(
1030  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1031  );
1032 
1033 /** gives constant belonging to a SCIP_EXPR_QUADRATIC expression */
1034 extern
1035 SCIP_Real SCIPexprgraphGetNodeQuadraticConstant(
1036  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1037  );
1038 
1039 /** gives linear coefficients belonging to a SCIP_EXPR_QUADRATIC expression, or NULL if all coefficients are 0.0 */
1040 extern
1041 SCIP_Real* SCIPexprgraphGetNodeQuadraticLinearCoefs(
1042  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1043  );
1044 
1045 /** gives quadratic elements belonging to a SCIP_EXPR_QUADRATIC expression */
1046 extern
1047 SCIP_QUADELEM* SCIPexprgraphGetNodeQuadraticQuadElements(
1048  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1049  );
1050 
1051 /** gives number of quadratic elements belonging to a SCIP_EXPR_QUADRATIC expression */
1052 extern
1053 int SCIPexprgraphGetNodeQuadraticNQuadElements(
1054  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1055  );
1056 
1057 /** gives the monomials belonging to a SCIP_EXPR_POLYNOMIAL expression */
1058 extern
1059 SCIP_EXPRDATA_MONOMIAL** SCIPexprgraphGetNodePolynomialMonomials(
1060  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1061  );
1062 
1063 /** gives the number of monomials belonging to a SCIP_EXPR_POLYNOMIAL expression */
1064 extern
1065 int SCIPexprgraphGetNodePolynomialNMonomials(
1066  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1067  );
1068 
1069 /** gives the constant belonging to a SCIP_EXPR_POLYNOMIAL expression */
1070 extern
1071 SCIP_Real SCIPexprgraphGetNodePolynomialConstant(
1072  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1073  );
1074 
1075 /** gets bounds of a node in an expression graph */
1076 extern
1077 SCIP_INTERVAL SCIPexprgraphGetNodeBounds(
1078  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1079  );
1080 
1081 /** gets value of expression associated to node from last evaluation call */
1082 extern
1083 SCIP_Real SCIPexprgraphGetNodeVal(
1084  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1085  );
1086 
1087 /** gets curvature of expression associated to node from last curvature check call */
1088 extern
1089 SCIP_EXPRCURV SCIPexprgraphGetNodeCurvature(
1090  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1091  );
1092 
1093 #ifdef NDEBUG
1094 
1095 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1096  * speed up the algorithms.
1097  */
1098 
1099 #define SCIPexprgraphCaptureNode(node) do { ++(node)->nuses; } while( FALSE )
1100 #define SCIPexprgraphIsNodeEnabled(node) (node)->enabled
1101 #define SCIPexprgraphGetNodeNChildren(node) (node)->nchildren
1102 #define SCIPexprgraphGetNodeChildren(node) (node)->children
1103 #define SCIPexprgraphGetNodeNParents(node) (node)->nparents
1104 #define SCIPexprgraphGetNodeParents(node) (node)->parents
1105 #define SCIPexprgraphGetNodeDepth(node) (node)->depth
1106 #define SCIPexprgraphGetNodePosition(node) (node)->pos
1107 #define SCIPexprgraphGetNodeOperator(node) (node)->op
1108 #define SCIPexprgraphGetNodeOperatorIndex(node) (node)->data.intval
1109 #define SCIPexprgraphGetNodeOperatorReal(node) (node)->data.dbl
1110 #define SCIPexprgraphGetNodeVar(exprgraph, node) (exprgraph)->vars[(node)->data.intval]
1111 #define SCIPexprgraphGetNodeRealPowerExponent(node) (node)->data.dbl
1112 #define SCIPexprgraphGetNodeIntPowerExponent(node) (node)->data.intval
1113 #define SCIPexprgraphGetNodeSignPowerExponent(node) (node)->data.dbl
1114 #define SCIPexprgraphGetNodeLinearCoefs(node) ((SCIP_Real*)(node)->data.data)
1115 #define SCIPexprgraphGetNodeLinearConstant(node) (((SCIP_Real*)(node)->data.data)[(node)->nchildren])
1116 #define SCIPexprgraphGetNodeQuadraticConstant(node) ((SCIP_EXPRDATA_QUADRATIC*)(node)->data.data)->constant
1117 #define SCIPexprgraphGetNodeQuadraticLinearCoefs(node) ((SCIP_EXPRDATA_QUADRATIC*)(node)->data.data)->lincoefs
1118 #define SCIPexprgraphGetNodeQuadraticQuadElements(node) ((SCIP_EXPRDATA_QUADRATIC*)(node)->data.data)->quadelems
1119 #define SCIPexprgraphGetNodeQuadraticNQuadElements(node) ((SCIP_EXPRDATA_QUADRATIC*)(node)->data.data)->nquadelems
1120 #define SCIPexprgraphGetNodePolynomialMonomials(node) ((SCIP_EXPRDATA_POLYNOMIAL*)(node)->data.data)->monomials
1121 #define SCIPexprgraphGetNodePolynomialNMonomials(node) ((SCIP_EXPRDATA_POLYNOMIAL*)(node)->data.data)->nmonomials
1122 #define SCIPexprgraphGetNodePolynomialConstant(node) ((SCIP_EXPRDATA_POLYNOMIAL*)(node)->data.data)->constant
1123 #define SCIPexprgraphGetNodeBounds(node) (node)->bounds
1124 #define SCIPexprgraphGetNodeVal(node) (node)->value
1125 #define SCIPexprgraphGetNodeCurvature(node) (node)->curv
1126 
1127 #endif
1128 
1129 /** creates an expression graph node */
1130 extern
1131 SCIP_RETCODE SCIPexprgraphCreateNode(
1132  BMS_BLKMEM* blkmem, /**< block memory */
1133  SCIP_EXPRGRAPHNODE** node, /**< buffer to store expression graph node */
1134  SCIP_EXPROP op, /**< operator type of expression */
1135  ...
1136  );
1137 
1138 /** creates an expression graph node for a linear expression */
1139 extern
1140 SCIP_RETCODE SCIPexprgraphCreateNodeLinear(
1141  BMS_BLKMEM* blkmem, /**< block memory */
1142  SCIP_EXPRGRAPHNODE** node, /**< buffer to store expression graph node */
1143  int ncoefs, /**< number of coefficients */
1144  SCIP_Real* coefs, /**< coefficients of linear expression */
1145  SCIP_Real constant /**< constant of linear expression */
1146  );
1147 
1148 /** creates an expression graph node for a quadratic expression */
1149 extern
1150 SCIP_RETCODE SCIPexprgraphCreateNodeQuadratic(
1151  BMS_BLKMEM* blkmem, /**< block memory */
1152  SCIP_EXPRGRAPHNODE** node, /**< buffer to store expression graph node */
1153  int nchildren, /**< number of children */
1154  SCIP_Real* lincoefs, /**< linear coefficients for children, or NULL */
1155  int nquadelems, /**< number of quadratic elements */
1156  SCIP_QUADELEM* quadelems, /**< quadratic elements, or NULL if nquadelems == 0 */
1157  SCIP_Real constant /**< constant */
1158  );
1159 
1160 /** creates an expression graph node for a polynomial expression */
1161 extern
1162 SCIP_RETCODE SCIPexprgraphCreateNodePolynomial(
1163  BMS_BLKMEM* blkmem, /**< block memory */
1164  SCIP_EXPRGRAPHNODE** node, /**< buffer to store expression graph node */
1165  int nmonomials, /**< number of monomials */
1166  SCIP_EXPRDATA_MONOMIAL** monomials, /**< monomials */
1167  SCIP_Real constant, /**< constant of polynomial */
1168  SCIP_Bool copymonomials /**< whether to copy monomials or to assume ownership */
1169  );
1170 
1171 /** adds monomials to an expression graph node that is a polynomial expression */
1172 extern
1173 SCIP_RETCODE SCIPexprgraphNodePolynomialAddMonomials(
1174  BMS_BLKMEM* blkmem, /**< block memory */
1175  SCIP_EXPRGRAPHNODE* node, /**< store expression graph node with polynomial operator */
1176  int nmonomials, /**< number of monomials */
1177  SCIP_EXPRDATA_MONOMIAL** monomials, /**< monomials */
1178  SCIP_Bool copymonomials /**< whether to copy monomials or to assume ownership */
1179  );
1180 
1181 /** given a node of an expression graph, splitup a linear part which variables are not used somewhere else in the same expression
1182  * E.g., if the expression is 1 + x + y + y^2, one gets 1 + x and the node remains at y + y^2.
1183  * If the node is a linear expression, it may be freed.
1184  * If it is not linear, the node may change, i.e., the remaining nonlinear part may be stored in a new node.
1185  * It is assumed that the user had captured the node.
1186  * It is assumed that the expression graph has been simplified before.
1187  */
1188 extern
1189 SCIP_RETCODE SCIPexprgraphNodeSplitOffLinear(
1190  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1191  SCIP_EXPRGRAPHNODE** node, /**< expression graph node where to splitup linear part */
1192  int linvarssize, /**< length of linvars and lincoefs arrays */
1193  int* nlinvars, /**< buffer to store length of linear term that have been splitup */
1194  void** linvars, /**< buffer to store variables of linear part */
1195  SCIP_Real* lincoefs, /**< buffer to store coefficients of linear part */
1196  SCIP_Real* constant /**< buffer to store constant part */
1197  );
1198 
1199 /** moves parents from a one node to another node
1200  * in other words, replaces the child srcnode by targetnode in all parents of srcnode
1201  * srcnode may be freed, if not captured
1202  * it is assumes that targetnode represents the same expression as srcnode
1203  */
1204 extern
1205 SCIP_RETCODE SCIPexprgraphMoveNodeParents(
1206  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1207  SCIP_EXPRGRAPHNODE** srcnode, /**< node which parents to move */
1208  SCIP_EXPRGRAPHNODE* targetnode /**< node where to move parents to */
1209  );
1210 
1211 /** releases node, i.e., decreases number of uses
1212  * node is freed if no parents and no other uses
1213  * children are recursively released if they have no other parents
1214  * nodes that are removed are also freed
1215  * if node correspond to a variable, then the variable is removed from the expression graph
1216  * similar for constants
1217  */
1218 extern
1219 SCIP_RETCODE SCIPexprgraphReleaseNode(
1220  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1221  SCIP_EXPRGRAPHNODE** node /**< expression graph node to release */
1222  );
1223 
1224 /** frees a node of an expression graph */
1225 extern
1226 void SCIPexprgraphFreeNode(
1227  BMS_BLKMEM* blkmem, /**< block memory */
1228  SCIP_EXPRGRAPHNODE** node /**< pointer to expression graph node that should be freed */
1229  );
1230 
1231 /** enables a node and recursively all its children in an expression graph */
1232 extern
1233 void SCIPexprgraphEnableNode(
1234  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1235  SCIP_EXPRGRAPHNODE* node /**< expression graph node to enable */
1236  );
1237 
1238 /** disables a node and recursively all children which have no enabled parents in an expression graph */
1239 extern
1240 void SCIPexprgraphDisableNode(
1241  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1242  SCIP_EXPRGRAPHNODE* node /**< expression graph node to enable */
1243  );
1244 
1245 /** returns whether the node has siblings in the expression graph */
1246 extern
1247 SCIP_Bool SCIPexprgraphHasNodeSibling(
1248  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1249  );
1250 
1251 /** returns whether all children of an expression graph node are variable nodes
1252  * gives TRUE for nodes without children
1253  */
1254 extern
1255 SCIP_Bool SCIPexprgraphAreAllNodeChildrenVars(
1256  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1257  );
1258 
1259 /** returns whether the node has an ancestor which has a nonlinear expression operand */
1260 extern
1261 SCIP_Bool SCIPexprgraphHasNodeNonlinearAncestor(
1262  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1263  );
1264 
1265 /** prints an expression graph node */
1266 extern
1267 void SCIPexprgraphPrintNode(
1268  SCIP_EXPRGRAPHNODE* node, /**< expression graph node */
1269  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1270  FILE* file /**< file to print to, or NULL for stdout */
1271  );
1272 
1273 /** tightens the bounds in a node of the graph
1274  * preparation for reverse propagation
1275  * sets bound status to SCIP_EXPRBOUNDSTATUS_TIGHTENEDBYPARENTRECENT if tightening is strong enough and not cutoff
1276  */
1277 extern
1278 void SCIPexprgraphTightenNodeBounds(
1279  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1280  SCIP_EXPRGRAPHNODE* node, /**< node in expression graph with no parents */
1281  SCIP_INTERVAL nodebounds, /**< new bounds for node */
1282  SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes (set to negative value if propagation should always be triggered) */
1283  SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
1284  );
1285 
1286 /** ensures that bounds and curvature information in a node is uptodate
1287  * assumes that bounds and curvature in children are uptodate
1288  */
1289 extern
1290 SCIP_RETCODE SCIPexprgraphUpdateNodeBoundsCurvature(
1291  SCIP_EXPRGRAPHNODE* node, /**< expression graph node */
1292  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
1293  SCIP_Real minstrength, /**< minimal required relative bound strengthening to trigger a bound recalculation in parent nodes */
1294  SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
1295  );
1296 
1297 /**@} */
1298 
1299 /**@name Expression graph methods */
1300 /**@{ */
1301 
1302 /** get current maximal depth of expression graph */
1303 extern
1304 int SCIPexprgraphGetDepth(
1305  SCIP_EXPRGRAPH* exprgraph /**< expression graph */
1306  );
1307 
1308 /** gets array with number of nodes at each depth of expression graph */
1309 extern
1310 int* SCIPexprgraphGetNNodes(
1311  SCIP_EXPRGRAPH* exprgraph /**< expression graph */
1312  );
1313 
1314 /** gets nodes of expression graph, one array per depth */
1315 extern
1316 SCIP_EXPRGRAPHNODE*** SCIPexprgraphGetNodes(
1317  SCIP_EXPRGRAPH* exprgraph /**< expression graph */
1318  );
1319 
1320 /** gets number of variables in expression graph */
1321 extern
1322 int SCIPexprgraphGetNVars(
1323  SCIP_EXPRGRAPH* exprgraph /**< pointer to expression graph that should be freed */
1324  );
1325 
1326 /** gets array of variables in expression graph */
1327 extern
1328 void** SCIPexprgraphGetVars(
1329  SCIP_EXPRGRAPH* exprgraph /**< pointer to expression graph that should be freed */
1330  );
1331 
1332 /** gets array of expression graph nodes corresponding to variables */
1333 extern
1334 SCIP_EXPRGRAPHNODE** SCIPexprgraphGetVarNodes(
1335  SCIP_EXPRGRAPH* exprgraph /**< pointer to expression graph that should be freed */
1336  );
1337 
1338 /** sets value for a single variable given as expression graph node */
1339 extern
1340 void SCIPexprgraphSetVarNodeValue(
1341  SCIP_EXPRGRAPHNODE* varnode, /**< expression graph node corresponding to variable */
1342  SCIP_Real value /**< new value for variable */
1343  );
1344 
1345 /** sets bounds for variables */
1346 extern
1347 void SCIPexprgraphSetVarsBounds(
1348  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1349  SCIP_INTERVAL* varbounds /**< new bounds for variables */
1350  );
1351 
1352 /** sets bounds for a single variable */
1353 extern
1354 void SCIPexprgraphSetVarBounds(
1355  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1356  void* var, /**< variable */
1357  SCIP_INTERVAL varbounds /**< new bounds of variable */
1358  );
1359 
1360 /** sets bounds for a single variable given as expression graph node */
1361 extern
1362 void SCIPexprgraphSetVarNodeBounds(
1363  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1364  SCIP_EXPRGRAPHNODE* varnode, /**< expression graph node corresponding to variable */
1365  SCIP_INTERVAL varbounds /**< new bounds of variable */
1366  );
1367 
1368 /** sets lower bound for a single variable given as expression graph node */
1369 extern
1370 void SCIPexprgraphSetVarNodeLb(
1371  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1372  SCIP_EXPRGRAPHNODE* varnode, /**< expression graph node corresponding to variable */
1373  SCIP_Real lb /**< new lower bound for variable */
1374  );
1375 
1376 /** sets upper bound for a single variable given as expression graph node */
1377 extern
1378 void SCIPexprgraphSetVarNodeUb(
1379  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1380  SCIP_EXPRGRAPHNODE* varnode, /**< expression graph node corresponding to variable */
1381  SCIP_Real ub /**< new upper bound for variable */
1382  );
1383 
1384 /** gets bounds that are stored for all variables */
1385 extern
1386 SCIP_INTERVAL* SCIPexprgraphGetVarsBounds(
1387  SCIP_EXPRGRAPH* exprgraph /**< expression graph */
1388  );
1389 
1390 #ifdef NDEBUG
1391 
1392 /* In optimized mode, the function calls are overwritten by defines to reduce the number of function calls and
1393  * speed up the algorithms.
1394  */
1395 
1396 #define SCIPexprgraphGetDepth(exprgraph) (exprgraph)->depth
1397 #define SCIPexprgraphGetNNodes(exprgraph) (exprgraph)->nnodes
1398 #define SCIPexprgraphGetNodes(exprgraph) (exprgraph)->nodes
1399 #define SCIPexprgraphGetNVars(exprgraph) (exprgraph)->nvars
1400 #define SCIPexprgraphGetVars(exprgraph) (exprgraph)->vars
1401 #define SCIPexprgraphGetVarNodes(exprgraph) (exprgraph)->varnodes
1402 #define SCIPexprgraphSetVarNodeValue(varnode, newvalue) do { (varnode)->value = newvalue; } while (FALSE)
1403 #define SCIPexprgraphSetVarsBounds(exprgraph, newvarbounds) BMScopyMemoryArray((exprgraph)->varbounds, newvarbounds, (exprgraph)->nvars)
1404 #define SCIPexprgraphSetVarBounds(exprgraph, var, newvarbounds) do { (exprgraph)->varbounds[(int)(size_t)SCIPhashmapGetImage((exprgraph)->varidxs, var)] = newvarbounds; } while (FALSE)
1405 #define SCIPexprgraphSetVarNodeBounds(exprgraph, varnode, newvarbounds) do { (exprgraph)->varbounds[(varnode)->data.intval] = newvarbounds; } while (FALSE)
1406 #define SCIPexprgraphSetVarNodeLb(exprgraph, varnode, lb) do { (exprgraph)->varbounds[(varnode)->data.intval].inf = lb; } while (FALSE)
1407 #define SCIPexprgraphSetVarNodeUb(exprgraph, varnode, ub) do { (exprgraph)->varbounds[(varnode)->data.intval].sup = ub; } while (FALSE)
1408 #define SCIPexprgraphGetVarsBounds(exprgraph) (exprgraph)->varbounds
1409 
1410 #endif
1411 
1412 /** creates an empty expression graph */
1413 extern
1414 SCIP_RETCODE SCIPexprgraphCreate(
1415  BMS_BLKMEM* blkmem, /**< block memory */
1416  SCIP_EXPRGRAPH** exprgraph, /**< buffer to store pointer to expression graph */
1417  int varssizeinit, /**< minimal initial size for variables array, or -1 to choose automatically */
1418  int depthinit, /**< minimal initial depth of expression graph, or -1 to choose automatically */
1419  SCIP_DECL_EXPRGRAPHVARADDED((*exprgraphvaradded)), /** callback method to invoke when a variable has been added to the expression graph, or NULL if not needed */
1420  SCIP_DECL_EXPRGRAPHVARREMOVE((*exprgraphvarremove)), /** callback method to invoke when a variable will be removed from the expression graph, or NULL if not needed */
1421  SCIP_DECL_EXPRGRAPHVARCHGIDX((*exprgraphvarchgidx)), /** callback method to invoke when a variable changes its index in the expression graph, or NULL if not needed */
1422  void* userdata /**< user data to pass to callback functions */
1423  );
1424 
1425 /** frees an expression graph */
1426 extern
1427 SCIP_RETCODE SCIPexprgraphFree(
1428  SCIP_EXPRGRAPH** exprgraph /**< pointer to expression graph that should be freed */
1429  );
1430 
1431 /** adds an expression graph node to an expression graph
1432  * expression graph assumes ownership of node
1433  * children are notified about new parent
1434  * depth will be chosen to be the maximum of mindepth and the depth of all children plus one
1435  */
1436 extern
1437 SCIP_RETCODE SCIPexprgraphAddNode(
1438  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1439  SCIP_EXPRGRAPHNODE* node, /**< expression graph node to add */
1440  int mindepth, /**< minimal depth in expression graph where to add node, e.g., 0 or smaller to choose automatically */
1441  int nchildren, /**< number of children */
1442  SCIP_EXPRGRAPHNODE** children /**< children nodes, or NULL if no children */
1443  );
1444 
1445 /** adds variables to an expression graph, if not existing yet
1446  * also already existing nodes are enabled
1447  */
1448 extern
1449 SCIP_RETCODE SCIPexprgraphAddVars(
1450  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1451  int nvars, /**< number of variables to add */
1452  void** vars, /**< variables to add */
1453  SCIP_EXPRGRAPHNODE** varnodes /**< array to store nodes corresponding to variables, or NULL if not of interest */
1454  );
1455 
1456 /** adds a constant to an expression graph, if not existing yet
1457  * also already existing nodes are enabled
1458  */
1459 SCIP_RETCODE SCIPexprgraphAddConst(
1460  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1461  SCIP_Real constant, /**< constant to add */
1462  SCIP_EXPRGRAPHNODE** constnode /**< buffer to store pointer to expression graph node corresponding to constant */
1463  );
1464 
1465 /** adds sum of expression trees into expression graph
1466  * node will also be captured
1467  */
1468 extern
1469 SCIP_RETCODE SCIPexprgraphAddExprtreeSum(
1470  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1471  int nexprtrees, /**< number of expression trees to add */
1472  SCIP_EXPRTREE** exprtrees, /**< expression trees that should be added */
1473  SCIP_Real* coefs, /**< coefficients of expression trees, or NULL if all 1.0 */
1474  SCIP_EXPRGRAPHNODE** rootnode, /**< buffer to store expression graph node corresponding to root of expression tree */
1475  SCIP_Bool* rootnodeisnew /**< buffer to indicate whether the node in *rootnode has been newly created for this expression tree (otherwise, expression tree was already in graph) */
1476  );
1477 
1478 /** replaces variable in expression graph by a linear sum of variables
1479  * variables will be added if not in the graph yet
1480  */
1481 extern
1482 SCIP_RETCODE SCIPexprgraphReplaceVarByLinearSum(
1483  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1484  void* var, /**< variable to replace */
1485  int ncoefs, /**< number of coefficients in linear term */
1486  SCIP_Real* coefs, /**< coefficients in linear term, or NULL if ncoefs == 0 */
1487  void** vars, /**< variables in linear term */
1488  SCIP_Real constant /**< constant offset */
1489  );
1490 
1491 /** finds expression graph node corresponding to a variable */
1492 extern
1493 SCIP_Bool SCIPexprgraphFindVarNode(
1494  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1495  void* var, /**< variable to search for */
1496  SCIP_EXPRGRAPHNODE** varnode /**< buffer to store node corresponding to variable, if found, or NULL if not found */
1497  );
1498 
1499 /** finds expression graph node corresponding to a constant */
1500 extern
1501 SCIP_Bool SCIPexprgraphFindConstNode(
1502  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1503  SCIP_Real constant, /**< constant to search for */
1504  SCIP_EXPRGRAPHNODE** constnode /**< buffer to store node corresponding to constant, if found, or NULL if not found */
1505  );
1506 
1507 /** prints an expression graph in dot format */
1508 extern
1509 SCIP_RETCODE SCIPexprgraphPrintDot(
1510  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1511  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1512  FILE* file, /**< file to print to, or NULL for stdout */
1513  const char** varnames /**< variable names, or NULL for generic names */
1514  );
1515 
1516 /** evaluates nodes of expression graph for given values of variables */
1517 extern
1518 SCIP_RETCODE SCIPexprgraphEval(
1519  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1520  SCIP_Real* varvals /**< values for variables */
1521  );
1522 
1523 /** propagates bound changes in variables forward through the expression graph */
1524 extern
1525 SCIP_RETCODE SCIPexprgraphPropagateVarBounds(
1526  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1527  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
1528  SCIP_Bool clearreverseprop, /**< whether to reset bound tightenings from reverse propagation */
1529  SCIP_Bool* domainerror /**< buffer to store whether a node with empty bounds has been found, propagation is interrupted in this case */
1530  );
1531 
1532 /** propagates bound changes in nodes backward through the graph
1533  * new bounds are not stored in varbounds, but only in nodes corresponding to variables
1534  * NOTE: it is assumed that SCIPexprgraphPropagateVarBounds was called before if variable bounds were relaxed
1535  */
1536 extern
1537 void SCIPexprgraphPropagateNodeBounds(
1538  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1539  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
1540  SCIP_Real minstrength, /**< minimal required relative bound strengthening in a node to trigger a propagation into children nodes */
1541  SCIP_Bool* cutoff /**< buffer to store whether a node's bounds were propagated to an empty interval */
1542  );
1543 
1544 /** updates curvature information in expression graph nodes w.r.t. currently stored variable bounds
1545  * implies update of bounds in expression graph
1546  */
1547 extern
1548 SCIP_RETCODE SCIPexprgraphCheckCurvature(
1549  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1550  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
1551  SCIP_Bool clearreverseprop /**< whether to reset bound tightenings from reverse propagation */
1552  );
1553 
1554 /** aims at simplifying an expression graph
1555  * a domain error can occur when variables were fixed to values for which a parent expression is not defined (e.g., 0^(-1) or log(-1))
1556  */
1557 extern
1558 SCIP_RETCODE SCIPexprgraphSimplify(
1559  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1560  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1561  SCIP_Real eps, /**< threshold, under which positive values are treat as 0 */
1562  int maxexpansionexponent,/**< maximal exponent for which we still expand non-monomial polynomials */
1563  SCIP_Bool* havechange, /**< buffer to indicate whether the graph has been modified */
1564  SCIP_Bool* domainerror /**< buffer to indicate whether a domain error has been encountered, i.e., some expressions turned into NaN */
1565  );
1566 
1567 /** creates an expression tree from a given node in an expression graph */
1568 extern
1569 SCIP_RETCODE SCIPexprgraphGetTree(
1570  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1571  SCIP_EXPRGRAPHNODE* rootnode, /**< expression graph node that should represent root of expression tree */
1572  SCIP_EXPRTREE** exprtree /**< buffer to store pointer to created expression tree */
1573  );
1574 
1575 /** creates a sum of expression trees with pairwise disjoint variables from a given node in an expression graph
1576  * Giving SCIPexprgraphGetNodeNChildren() for exprtreesize is always sufficient.
1577  */
1578 extern
1579 SCIP_RETCODE SCIPexprgraphGetSeparableTrees(
1580  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1581  SCIP_EXPRGRAPHNODE* node, /**< expression graph node which represents expression to get */
1582  int exprtreessize, /**< length of exprtrees and exprtreecoefs arrays, need to be at least one */
1583  int* nexprtrees, /**< buffer to store number of expression trees */
1584  SCIP_EXPRTREE** exprtrees, /**< array where to store expression trees */
1585  SCIP_Real* exprtreecoefs /**< array where to store coefficients of expression trees */
1586  );
1587 
1588 /** returns how often expression graph variables are used in a subtree of the expression graph */
1589 extern
1590 void SCIPexprgraphGetSubtreeVarsUsage(
1591  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1592  SCIP_EXPRGRAPHNODE* node, /**< root node of expression graph subtree */
1593  int* varsusage /**< array where to count usage of variables, length must be at least the number of variables in the graph */
1594  );
1595 
1596 /** gives the number of summands which the expression of an expression graph node consists of */
1597 extern
1598 int SCIPexprgraphGetSumTreesNSummands(
1599  SCIP_EXPRGRAPHNODE* node /**< expression graph node */
1600  );
1601 
1602 /** creates a sum of expression trees, possibly sharing variables, from a given node in an expression graph */
1603 extern
1604 SCIP_RETCODE SCIPexprgraphGetSumTrees(
1605  SCIP_EXPRGRAPH* exprgraph, /**< expression graph */
1606  SCIP_EXPRGRAPHNODE* node, /**< expression graph node which represents expression to get */
1607  int exprtreessize, /**< length of exprtrees and exptreecoefs arrays, should be at least SCIPexprgraphGetSumTreesNSummands() */
1608  int* nexprtrees, /**< buffer to store number of expression trees */
1609  SCIP_EXPRTREE** exprtrees, /**< array where to store expression trees */
1610  SCIP_Real* exprtreecoefs /**< array where to store coefficients of expression trees */
1611  );
1612 
1613 /**@} */
1614 
1615 #ifdef __cplusplus
1616 }
1617 #endif
1618 
1619 #endif /* __NLPI_PUB_EXPR_H__ */
1620