Scippy

SCIP

Solving Constraint Integer Programs

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