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