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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file 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 */
824 SCIP* scip, /**< SCIP data structure */
825 SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */
826 const char* name, /**< name of expression handler (must not be NULL) */
827 const char* desc, /**< description of expression handler (can be NULL) */
828 unsigned int precedence, /**< precedence of expression operation (used for printing) */
829 SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */
830 SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */
831 )
832{
833 assert(scip != NULL);
834 assert(scip->mem != NULL);
835 assert(exprhdlr != NULL);
836
837 SCIP_CALL( SCIPexprhdlrCreate(scip->mem->setmem, exprhdlr, name, desc, precedence, eval, data) );
838 assert(*exprhdlr != NULL);
839
840 SCIP_CALL( SCIPsetIncludeExprhdlr(scip->set, *exprhdlr) );
841
842 return SCIP_OKAY;
843}
844
845/** gives expression handlers */
847 SCIP* scip /**< SCIP data structure */
848 )
849{
850 assert(scip != NULL);
851 assert(scip->set != NULL);
852
853 return scip->set->exprhdlrs;
854}
855
856/** gives number of expression handlers */
858 SCIP* scip /**< SCIP data structure */
859 )
860{
861 assert(scip != NULL);
862 assert(scip->set != NULL);
863
864 return scip->set->nexprhdlrs;
865}
866
867/** returns an expression handler of a given name (or NULL if not found) */
869 SCIP* scip, /**< SCIP data structure */
870 const char* name /**< name of expression handler */
871 )
872{
873 assert(scip != NULL);
874 assert(scip->set != NULL);
875
876 return SCIPsetFindExprhdlr(scip->set, name);
877}
878
879/** returns expression handler for variable expressions (or NULL if not included) */
881 SCIP* scip /**< SCIP data structure */
882 )
883{
884 assert(scip != NULL);
885 assert(scip->set != NULL);
886
887 return scip->set->exprhdlrvar;
888}
889
890/** returns expression handler for constant value expressions (or NULL if not included) */
892 SCIP* scip /**< SCIP data structure */
893 )
894{
895 assert(scip != NULL);
896 assert(scip->set != NULL);
897
898 return scip->set->exprhdlrval;
899}
900
901/** returns expression handler for sum expressions (or NULL if not included) */
903 SCIP* scip /**< SCIP data structure */
904 )
905{
906 assert(scip != NULL);
907 assert(scip->set != NULL);
908
909 return scip->set->exprhdlrsum;
910}
911
912/** returns expression handler for product expressions (or NULL if not included) */
914 SCIP* scip /**< SCIP data structure */
915 )
916{
917 assert(scip != NULL);
918 assert(scip->set != NULL);
919
920 return scip->set->exprhdlrproduct;
921}
922
923/** returns expression handler for power expressions (or NULL if not included) */
925 SCIP* scip /**< SCIP data structure */
926 )
927{
928 assert(scip != NULL);
929 assert(scip->set != NULL);
930
931 return scip->set->exprhdlrpow;
932}
933
934/**@} */
935
936
937/**@name Expression Methods */
938/**@{ */
939
940#ifdef NDEBUG
941#undef SCIPappendExprChild
942#undef SCIPreplaceExprChild
943#undef SCIPremoveExprChildren
944#undef SCIPduplicateExpr
945#undef SCIPduplicateExprShallow
946#undef SCIPcaptureExpr
947#undef SCIPreleaseExpr
948#undef SCIPisExprVar
949#undef SCIPisExprValue
950#undef SCIPisExprSum
951#undef SCIPisExprProduct
952#undef SCIPisExprPower
953#undef SCIPprintExpr
954#undef SCIPevalExpr
955#undef SCIPgetExprNewSoltag
956#undef SCIPevalExprGradient
957#undef SCIPevalExprHessianDir
958#undef SCIPevalExprActivity
959#undef SCIPcompareExpr
960#undef SCIPsimplifyExpr
961#undef SCIPcallExprCurvature
962#undef SCIPcallExprMonotonicity
963#undef SCIPcallExprEval
964#undef SCIPcallExprEvalFwdiff
965#undef SCIPcallExprInteval
966#undef SCIPcallExprEstimate
967#undef SCIPcallExprInitestimates
968#undef SCIPcallExprSimplify
969#undef SCIPcallExprReverseprop
970#undef SCIPcallExprGetSymData
971#endif
972
973/** creates and captures an expression with given expression data and children */
975 SCIP* scip, /**< SCIP data structure */
976 SCIP_EXPR** expr, /**< pointer where to store expression */
977 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
978 SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */
979 int nchildren, /**< number of children */
980 SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */
981 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
982 void* ownercreatedata /**< data to pass to ownercreate */
983 )
984{
985 assert(scip != NULL);
986 assert(scip->set != NULL);
987
988 SCIP_CALL( SCIPexprCreate(scip->set, scip->mem->probmem, expr, exprhdlr, exprdata, nchildren, children, ownercreate,
989 ownercreatedata) );
990
991 return SCIP_OKAY;
992}
993
994/** creates and captures an expression with given expression data and up to two children */
996 SCIP* scip, /**< SCIP data structure */
997 SCIP_EXPR** expr, /**< pointer where to store expression */
998 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
999 SCIP_EXPRDATA* exprdata, /**< expression data */
1000 SCIP_EXPR* child1, /**< first child (can be NULL) */
1001 SCIP_EXPR* child2, /**< second child (can be NULL) */
1002 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1003 void* ownercreatedata /**< data to pass to ownercreate */
1004 )
1005{
1006 assert(scip != NULL);
1007 assert(expr != NULL);
1008 assert(exprhdlr != NULL);
1009
1010 if( child1 != NULL && child2 != NULL )
1011 {
1012 SCIP_EXPR* pair[2];
1013 pair[0] = child1;
1014 pair[1] = child2;
1015
1016 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 2, pair, ownercreate, ownercreatedata) );
1017 }
1018 else if( child2 == NULL )
1019 {
1020 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, child1 == NULL ? 0 : 1, &child1, ownercreate,
1021 ownercreatedata) );
1022 }
1023 else
1024 {
1025 /* child2 != NULL, child1 == NULL */
1026 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child2, ownercreate, ownercreatedata) );
1027 }
1028
1029 return SCIP_OKAY;
1030}
1031
1032/** creates and captures an expression representing a quadratic function */
1034 SCIP* scip, /**< SCIP data structure */
1035 SCIP_EXPR** expr, /**< pointer where to store expression */
1036 int nlinvars, /**< number of linear terms */
1037 SCIP_VAR** linvars, /**< array with variables in linear part */
1038 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part */
1039 int nquadterms, /**< number of quadratic terms */
1040 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms */
1041 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms */
1042 SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms */
1043 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1044 void* ownercreatedata /**< data to pass to ownercreate */
1045 )
1046{
1047 SCIP_EXPR** children;
1048 SCIP_Real* coefs;
1049 int i;
1050
1051 assert(scip != NULL);
1052 assert(expr != NULL);
1053 assert(nlinvars == 0 || (linvars != NULL && lincoefs != NULL));
1054 assert(nquadterms == 0 || (quadvars1 != NULL && quadvars2 != NULL && quadcoefs != NULL));
1055
1056 /* allocate memory */
1057 SCIP_CALL( SCIPallocBufferArray(scip, &children, nquadterms + nlinvars) );
1058 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nquadterms + nlinvars) );
1059
1060 /* create children for quadratic terms */
1061 for( i = 0; i < nquadterms; ++i )
1062 {
1063 assert(quadvars1 != NULL && quadvars1[i] != NULL);
1064 assert(quadvars2 != NULL && quadvars2[i] != NULL);
1065
1066 /* quadratic term */
1067 if( quadvars1[i] == quadvars2[i] )
1068 {
1069 SCIP_EXPR* xexpr;
1070
1071 /* create variable expression; intentionally not using createExprVar here,
1072 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1073 */
1074 SCIP_CALL( SCIPcreateExprVar(scip, &xexpr, quadvars1[i], ownercreate, ownercreatedata) );
1075
1076 /* create pow expression */
1077 SCIP_CALL( SCIPcreateExprPow(scip, &children[i], xexpr, 2.0, ownercreate, ownercreatedata) );
1078
1079 /* release variable expression; note that the variable expression is still captured by children[i] */
1080 SCIP_CALL( SCIPreleaseExpr(scip, &xexpr) );
1081 }
1082 else /* bilinear term */
1083 {
1084 SCIP_EXPR* exprs[2];
1085
1086 /* create variable expressions; intentionally not using createExprVar here,
1087 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1088 */
1089 SCIP_CALL( SCIPcreateExprVar(scip, &exprs[0], quadvars1[i], ownercreate, ownercreatedata) );
1090 SCIP_CALL( SCIPcreateExprVar(scip, &exprs[1], quadvars2[i], ownercreate, ownercreatedata) );
1091
1092 /* create product expression */
1093 SCIP_CALL( SCIPcreateExprProduct(scip, &children[i], 2, exprs, 1.0, ownercreate, ownercreatedata) );
1094
1095 /* release variable expressions; note that the variable expressions are still captured by children[i] */
1096 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[1]) );
1097 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[0]) );
1098 }
1099
1100 /* store coefficient */
1101 coefs[i] = quadcoefs[i];
1102 }
1103
1104 /* create children for linear terms */
1105 for( i = 0; i < nlinvars; ++i )
1106 {
1107 assert(linvars != NULL && linvars[i] != NULL);
1108
1109 /* create variable expression; intentionally not using createExprVar here,
1110 * since expression created here is not part of a constraint (they will be copied when a constraint is created);
1111 * release variable expression after the sum expression has been created
1112 */
1113 SCIP_CALL( SCIPcreateExprVar(scip, &children[nquadterms + i], linvars[i], ownercreate, ownercreatedata) );
1114
1115 /* store coefficient */
1116 coefs[nquadterms + i] = lincoefs[i];
1117 }
1118
1119 /* create sum expression */
1120 SCIP_CALL( SCIPcreateExprSum(scip, expr, nquadterms + nlinvars, children, coefs, 0.0, ownercreate, ownercreatedata) );
1121
1122 /* release children */
1123 for( i = 0; i < nquadterms + nlinvars; ++i )
1124 {
1125 assert(children[i] != NULL);
1126 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1127 }
1128
1129 /* free memory */
1130 SCIPfreeBufferArray(scip, &coefs);
1131 SCIPfreeBufferArray(scip, &children);
1132
1133 return SCIP_OKAY;
1134}
1135
1136/** creates and captures an expression representing a monomial
1137 *
1138 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents.
1139 * So this function actually creates an expression for a signomial that has exactly one term.
1140 */
1142 SCIP* scip, /**< SCIP data structure */
1143 SCIP_EXPR** expr, /**< pointer where to store expression */
1144 int nfactors, /**< number of factors in monomial */
1145 SCIP_VAR** vars, /**< variables in the monomial */
1146 SCIP_Real* exponents, /**< exponent in each factor, or NULL if all 1.0 */
1147 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1148 void* ownercreatedata /**< data to pass to ownercreate */
1149 )
1150{
1151 assert(scip != NULL);
1152 assert(expr != NULL);
1153 assert(nfactors >= 0);
1154
1155 /* return 1 as constant expression if there are no factors */
1156 if( nfactors == 0 )
1157 {
1158 SCIP_CALL( SCIPcreateExprValue(scip, expr, 1.0, ownercreate, ownercreatedata) );
1159 }
1160 else if( nfactors == 1 )
1161 {
1162 /* only one factor and exponent is 1 => return factors[0] */
1163 if( exponents == NULL || exponents[0] == 1.0 )
1164 {
1165 /* intentionally not using createExprVar here, since expression created here is not part of
1166 * a constraint (they will be copied when a constraint is created)
1167 */
1168 SCIP_CALL( SCIPcreateExprVar(scip, expr, vars[0], ownercreate, ownercreatedata) );
1169 }
1170 else
1171 {
1172 SCIP_EXPR* varexpr;
1173
1174 /* create variable and power expression; intentionally not using createExprVar here,
1175 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1176 */
1177 SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[0], ownercreate, ownercreatedata) );
1178 SCIP_CALL( SCIPcreateExprPow(scip, expr, varexpr, exponents[0], ownercreate, ownercreatedata) );
1179 SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
1180 }
1181 }
1182 else
1183 {
1184 SCIP_EXPR** children;
1185 int i;
1186
1187 /* allocate memory to store the children */
1188 SCIP_CALL( SCIPallocBufferArray(scip, &children, nfactors) );
1189
1190 /* create children */
1191 for( i = 0; i < nfactors; ++i )
1192 {
1193 /* check whether to create a power expression or not, i.e., exponent == 1 */
1194 if( exponents == NULL || exponents[i] == 1.0 )
1195 {
1196 SCIP_CALL( SCIPcreateExprVar(scip, &children[i], vars[i], ownercreate, ownercreatedata) );
1197 }
1198 else
1199 {
1200 SCIP_EXPR* varexpr;
1201
1202 /* create variable and pow expression */
1203 SCIP_CALL( SCIPcreateExprVar(scip, &varexpr, vars[i], ownercreate, ownercreatedata) );
1204 SCIP_CALL( SCIPcreateExprPow(scip, &children[i], varexpr, exponents[i], ownercreate, ownercreatedata) );
1205 SCIP_CALL( SCIPreleaseExpr(scip, &varexpr) );
1206 }
1207 }
1208
1209 /* create product expression */
1210 SCIP_CALL( SCIPcreateExprProduct(scip, expr, nfactors, children, 1.0, ownercreate, ownercreatedata) );
1211
1212 /* release children */
1213 for( i = 0; i < nfactors; ++i )
1214 {
1215 assert(children[i] != NULL);
1216 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1217 }
1218
1219 /* free memory */
1220 SCIPfreeBufferArray(scip, &children);
1221 }
1222
1223 return SCIP_OKAY;
1224}
1225
1226/** appends child to the children list of expr
1227 *
1228 * @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.
1229 */
1231 SCIP* scip, /**< SCIP data structure */
1232 SCIP_EXPR* expr, /**< expression */
1233 SCIP_EXPR* child /**< expression to be appended */
1234 )
1235{
1236 assert(scip != NULL);
1237 assert(scip->mem != NULL);
1238
1239 SCIP_CALL( SCIPexprAppendChild(scip->set, scip->mem->probmem, expr, child) );
1240
1241 return SCIP_OKAY;
1242}
1243
1244/** overwrites/replaces a child of an expressions
1245 *
1246 * The old child is released and the newchild is captured, unless they are the same (=same pointer).
1247 */
1249 SCIP* scip, /**< SCIP data structure */
1250 SCIP_EXPR* expr, /**< expression which is going to replace a child */
1251 int childidx, /**< index of child being replaced */
1252 SCIP_EXPR* newchild /**< the new child */
1253 )
1254{
1255 assert(scip != NULL);
1256 assert(scip->mem != NULL);
1257
1258 SCIP_CALL( SCIPexprReplaceChild(scip->set, scip->stat, scip->mem->probmem, expr, childidx, newchild) );
1259
1260 return SCIP_OKAY;
1261}
1262
1263/** remove all children of expr
1264 *
1265 * @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.
1266 */
1268 SCIP* scip, /**< SCIP data structure */
1269 SCIP_EXPR* expr /**< expression */
1270 )
1271{
1272 assert(scip != NULL);
1273 assert(scip->mem != NULL);
1274
1275 SCIP_CALL( SCIPexprRemoveChildren(scip->set, scip->stat, scip->mem->probmem, expr) );
1276
1277 return SCIP_OKAY;
1278}
1279
1280/** duplicates the given expression and its children */
1282 SCIP* scip, /**< SCIP data structure */
1283 SCIP_EXPR* expr, /**< original expression */
1284 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
1285 SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */
1286 void* mapexprdata, /**< data of expression mapping function */
1287 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1288 void* ownercreatedata /**< data to pass to ownercreate */
1289 )
1290{
1291 assert(scip != NULL);
1292 assert(scip->mem != NULL);
1293
1294 SCIP_CALL( SCIPexprCopy(scip->set, scip->stat, scip->mem->probmem, scip->set, scip->stat, scip->mem->probmem,
1295 expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) );
1296
1297 return SCIP_OKAY;
1298}
1299
1300/** duplicates the given expression, but reuses its children */
1302 SCIP* scip, /**< SCIP data structure */
1303 SCIP_EXPR* expr, /**< original expression */
1304 SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */
1305 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1306 void* ownercreatedata /**< data to pass to ownercreate */
1307 )
1308{
1309 assert(scip != NULL);
1310 assert(scip->mem != NULL);
1311
1312 SCIP_CALL( SCIPexprDuplicateShallow(scip->set, scip->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata) );
1313
1314 return SCIP_OKAY;
1315}
1316
1317/** copies an expression including children to use in a (possibly different) SCIP instance */
1319 SCIP* sourcescip, /**< source SCIP data structure */
1320 SCIP* targetscip, /**< target SCIP data structure */
1321 SCIP_EXPR* expr, /**< original expression */
1322 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
1323 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1324 void* ownercreatedata, /**< data to pass to ownercreate */
1325 SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding
1326 * variables of the target SCIP, or NULL */
1327 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
1328 * target constraints, or NULL */
1329 SCIP_Bool global, /**< create a global or a local copy? */
1330 SCIP_Bool* valid /**< pointer to store whether all checked or enforced constraints were validly copied */
1331 )
1332{
1333#ifndef _MSC_VER
1334 COPY_MAPEXPR_DATA copydata = {
1335 .varmap = varmap,
1336 .consmap = consmap,
1337 .global = global,
1338 .valid = TRUE
1339 };
1340#else /* MS compiler doesn't have proper C99 support... */
1341 COPY_MAPEXPR_DATA copydata;
1342 copydata.varmap = varmap;
1343 copydata.consmap = consmap;
1344 copydata.global = global;
1345 copydata.valid = TRUE;
1346#endif
1347
1348 assert(sourcescip != NULL);
1349 assert(sourcescip->mem != NULL);
1350 assert(targetscip != NULL);
1351 assert(targetscip->mem != NULL);
1352
1353 SCIP_CALL( SCIPexprCopy(sourcescip->set, sourcescip->stat, sourcescip->mem->probmem,
1354 targetscip->set, targetscip->stat, targetscip->mem->probmem,
1355 expr, copyexpr, copyVarExpr, &copydata, ownercreate, ownercreatedata) );
1356
1357 *valid = copydata.valid;
1358
1359 return SCIP_OKAY;
1360}
1361
1362/** creates an expression from a string
1363 *
1364 * We specify the grammar that defines the syntax of an expression.
1365 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power,
1366 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`.
1367 *
1368 * The actual definition:
1369 * <pre>
1370 * Expression -> ["+" | "-"] Term { [ ("+" | "-" | "number *") Term | ("number" <varname>) ] }
1371 * Term -> Factor { ("*" | "/" ) Factor }
1372 * Factor -> Base [ "^" "number" | "^(" "number" ")" ]
1373 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
1374 * </pre>
1375 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`.
1376 *
1377 * Note that `Op` and `OpExpression` are undefined.
1378 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method).
1379 */
1381 SCIP* scip, /**< SCIP data structure */
1382 SCIP_EXPR** expr, /**< pointer to store the expr parsed */
1383 const char* exprstr, /**< string with the expr to parse */
1384 const char** finalpos, /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */
1385 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1386 void* ownercreatedata /**< data to pass to ownercreate */
1387 )
1388{
1389 const char* finalpos_;
1390 SCIP_RETCODE retcode;
1391 SCIP_HASHMAP* vartoexprvarmap;
1392
1393 assert(scip != NULL);
1394
1395 SCIP_CALL( SCIPhashmapCreate(&vartoexprvarmap, SCIPblkmem(scip), 5 * SCIPgetNVars(scip)) );
1396
1397 /* if parseExpr fails, we still want to free hashmap */
1398 retcode = parseExpr(scip, vartoexprvarmap, exprstr, &finalpos_, expr, ownercreate, ownercreatedata);
1399
1400 SCIPhashmapFree(&vartoexprvarmap);
1401
1402 if( finalpos != NULL )
1403 *finalpos = finalpos_;
1404
1405 return retcode;
1406}
1407
1408/** captures an expression (increments usage count) */
1410 SCIP_EXPR* expr /**< expression to be captured */
1411 )
1412{
1413 SCIPexprCapture(expr);
1414}
1415
1416/** releases an expression (decrements usage count and possibly frees expression) */
1418 SCIP* scip, /**< SCIP data structure */
1419 SCIP_EXPR** expr /**< pointer to expression to be released */
1420 )
1421{
1422 assert(scip != NULL);
1423 assert(scip->mem != NULL);
1424
1425 SCIP_CALL( SCIPexprRelease(scip->set, scip->stat, scip->mem->probmem, expr) );
1426
1427 return SCIP_OKAY;
1428}
1429
1430/** returns whether an expression is a variable expression */
1432 SCIP* scip, /**< SCIP data structure */
1433 SCIP_EXPR* expr /**< expression */
1434 )
1435{
1436 assert(scip != NULL);
1437
1438 return SCIPexprIsVar(scip->set, expr);
1439}
1440
1441/** returns whether an expression is a value expression */
1443 SCIP* scip, /**< SCIP data structure */
1444 SCIP_EXPR* expr /**< expression */
1445 )
1446{
1447 assert(scip != NULL);
1448
1449 return SCIPexprIsValue(scip->set, expr);
1450}
1451
1452/** returns whether an expression is a sum expression */
1454 SCIP* scip, /**< SCIP data structure */
1455 SCIP_EXPR* expr /**< expression */
1456 )
1457{
1458 assert(scip != NULL);
1459
1460 return SCIPexprIsSum(scip->set, expr);
1461}
1462
1463/** returns whether an expression is a product expression */
1465 SCIP* scip, /**< SCIP data structure */
1466 SCIP_EXPR* expr /**< expression */
1467 )
1468{
1469 assert(scip != NULL);
1470
1471 return SCIPexprIsProduct(scip->set, expr);
1472}
1473
1474/** returns whether an expression is a power expression */
1476 SCIP* scip, /**< SCIP data structure */
1477 SCIP_EXPR* expr /**< expression */
1478 )
1479{
1480 assert(scip != NULL);
1481
1482 return SCIPexprIsPower(scip->set, expr);
1483}
1484
1485/** print an expression as info-message */
1487 SCIP* scip, /**< SCIP data structure */
1488 SCIP_EXPR* expr, /**< expression to be printed */
1489 FILE* file /**< file to print to, or NULL for stdout */
1490 )
1491{
1492 assert(scip != NULL);
1493 assert(scip->mem != NULL);
1494
1495 SCIP_CALL( SCIPexprPrint(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1496
1497 return SCIP_OKAY;
1498}
1499
1500/** initializes printing of expressions in dot format to a give FILE* pointer */
1502 SCIP* scip, /**< SCIP data structure */
1503 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
1504 FILE* file, /**< file to print to, or NULL for stdout */
1505 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
1506 )
1507{
1508 assert(scip != NULL);
1509 assert(scip->mem != NULL);
1510
1511 SCIP_CALL( SCIPexprPrintDotInit(scip->set, scip->stat, scip->mem->probmem, printdata, file, whattoprint) );
1512
1513 return SCIP_OKAY;
1514}
1515
1516/** initializes printing of expressions in dot format to a file with given filename */
1518 SCIP* scip, /**< SCIP data structure */
1519 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
1520 const char* filename, /**< name of file to print to */
1521 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
1522 )
1523{
1524 assert(scip != NULL);
1525 assert(scip->mem != NULL);
1526
1527 SCIP_CALL( SCIPexprPrintDotInit2(scip->set, scip->stat, scip->mem->probmem, printdata, filename, whattoprint) );
1528
1529 return SCIP_OKAY;
1530}
1531
1532/** main part of printing an expression in dot format */
1534 SCIP* scip, /**< SCIP data structure */
1535 SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */
1536 SCIP_EXPR* expr /**< expression to be printed */
1537 )
1538{
1539 assert(scip != NULL);
1540
1541 SCIP_CALL( SCIPexprPrintDot(scip->set, scip->messagehdlr, printdata, expr) );
1542
1543 return SCIP_OKAY;
1544}
1545
1546/** finishes printing of expressions in dot format */
1548 SCIP* scip, /**< SCIP data structure */
1549 SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */
1550 )
1551{
1552 assert(scip != NULL);
1553 assert(scip->mem != NULL);
1554
1555 SCIP_CALL( SCIPexprPrintDotFinal(scip->set, scip->stat, scip->mem->probmem, printdata) );
1556
1557 return SCIP_OKAY;
1558}
1559
1560/** shows a single expression by use of dot and gv
1561 *
1562 * This function is meant for debugging purposes.
1563 * It's signature is kept as simple as possible to make it
1564 * easily callable from gdb, for example.
1565 *
1566 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file,
1567 * then calls ghostview (gv) to show the file. SCIP will hold until ghostscript is closed.
1568 */
1570 SCIP* scip, /**< SCIP data structure */
1571 SCIP_EXPR* expr /**< expression to be printed */
1572 )
1573{
1574 /* this function is for developers, so don't bother with C variants that don't have popen() */
1575#if _POSIX_C_SOURCE < 2
1576 SCIPerrorMessage("No POSIX version 2. Try http://distrowatch.com/.");
1577 return SCIP_ERROR;
1578#else
1579 SCIP_EXPRPRINTDATA* dotdata;
1580 FILE* f;
1581 SCIP_RETCODE retcode = SCIP_OKAY;
1582
1583 assert(scip != NULL);
1584 assert(expr != NULL);
1585
1586 /* call dot to generate postscript output and show it via ghostview */
1587 f = popen("dot -Tps | gv --media=a3 -", "w");
1588 if( f == NULL )
1589 {
1590 SCIPerrorMessage("Calling popen() failed");
1591 return SCIP_FILECREATEERROR;
1592 }
1593
1594 /* print all of the expression into the pipe */
1595 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotInit(scip, &dotdata, f, SCIP_EXPRPRINT_ALL), TERMINATE );
1596 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDot(scip, dotdata, expr), TERMINATE );
1597 SCIP_CALL_TERMINATE( retcode, SCIPprintExprDotFinal(scip, &dotdata), TERMINATE );
1598
1599 TERMINATE:
1600 /* close the pipe */
1601 (void) pclose(f);
1602
1603 return retcode;
1604#endif
1605}
1606
1607/** prints structure of an expression a la Maple's dismantle */
1609 SCIP* scip, /**< SCIP data structure */
1610 FILE* file, /**< file to print to, or NULL for stdout */
1611 SCIP_EXPR* expr /**< expression to dismantle */
1612 )
1613{
1614 assert(scip != NULL);
1615 assert(scip->mem != NULL);
1616
1617 SCIP_CALL( SCIPexprDismantle(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1618
1619 return SCIP_OKAY;
1620}
1621
1622/** evaluate an expression in a point
1623 *
1624 * Iterates over expressions to also evaluate children, if necessary.
1625 * Value can be received via SCIPexprGetEvalValue().
1626 * If an evaluation error (division by zero, ...) occurs, this value will
1627 * be set to SCIP_INVALID.
1628 *
1629 * If a nonzero \p soltag is passed, then only (sub)expressions are
1630 * reevaluated that have a different solution tag. If a soltag of 0
1631 * is passed, then subexpressions are always reevaluated.
1632 * The tag is stored together with the value and can be received via
1633 * SCIPexprGetEvalTag().
1634 */
1636 SCIP* scip, /**< SCIP data structure */
1637 SCIP_EXPR* expr, /**< expression to be evaluated */
1638 SCIP_SOL* sol, /**< solution to be evaluated */
1639 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
1640 )
1641{
1642 assert(scip != NULL);
1643 assert(scip->mem != NULL);
1644
1645 SCIP_CALL( SCIPexprEval(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1646
1647 return SCIP_OKAY;
1648}
1649
1650/** returns a previously unused solution tag for expression evaluation */
1652 SCIP* scip /**< SCIP data structure */
1653 )
1654{
1655 assert(scip != NULL);
1656
1657 return ++(scip->stat->exprlastsoltag);
1658}
1659
1660/** evaluates gradient of an expression for a given point
1661 *
1662 * Initiates an expression walk to also evaluate children, if necessary.
1663 * Value can be received via SCIPgetExprPartialDiffNonlinear().
1664 * If an error (division by zero, ...) occurs, this value will
1665 * be set to SCIP_INVALID.
1666 */
1668 SCIP* scip, /**< SCIP data structure */
1669 SCIP_EXPR* expr, /**< expression to be differentiated */
1670 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
1671 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
1672 )
1673{
1674 assert(scip != NULL);
1675 assert(scip->mem != NULL);
1676
1677 SCIP_CALL( SCIPexprEvalGradient(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1678
1679 return SCIP_OKAY;
1680}
1681
1682/** evaluates Hessian-vector product of an expression for a given point and direction
1683 *
1684 * Evaluates children, if necessary.
1685 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear().
1686 * If an error (division by zero, ...) occurs, this value will
1687 * be set to SCIP_INVALID.
1688 */
1690 SCIP* scip, /**< SCIP data structure */
1691 SCIP_EXPR* expr, /**< expression to be differentiated */
1692 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
1693 SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */
1694 SCIP_SOL* direction /**< direction */
1695 )
1696{
1697 assert(scip != NULL);
1698 assert(scip->mem != NULL);
1699
1700 SCIP_CALL( SCIPexprEvalHessianDir(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag, direction) );
1701
1702 return SCIP_OKAY;
1703}
1704
1705/** possibly reevaluates and then returns the activity of the expression
1706 *
1707 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation).
1708 *
1709 * The owner of the expression may overwrite the methods used to evaluate the activity,
1710 * including whether the local or global domain of variables is used.
1711 * By default (no owner, or owner doesn't overwrite activity evaluation),
1712 * the local domain of variables is used.
1713 *
1714 * @note If expression is set to be integral, then activities are tightened to integral values.
1715 * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
1716 */
1718 SCIP* scip, /**< SCIP data structure */
1719 SCIP_EXPR* expr /**< expression */
1720 )
1721{
1722 assert(scip != NULL);
1723 assert(scip->mem != NULL);
1724
1725 SCIP_CALL( SCIPexprEvalActivity(scip->set, scip->stat, scip->mem->probmem, expr) );
1726
1727 return SCIP_OKAY;
1728}
1729
1730/** compare expressions
1731 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
1732 * @note The given expressions are assumed to be simplified.
1733 */
1735 SCIP* scip, /**< SCIP data structure */
1736 SCIP_EXPR* expr1, /**< first expression */
1737 SCIP_EXPR* expr2 /**< second expression */
1738 )
1739{
1740 assert(scip != NULL);
1741
1742 return SCIPexprCompare(scip->set, expr1, expr2);
1743}
1744
1745/** compute the hash value of an expression */
1747 SCIP* scip, /**< SCIP data structure */
1748 SCIP_EXPR* expr, /**< expression */
1749 unsigned int* hashval /**< pointer to store the hash value */
1750 )
1751{
1752 SCIP_EXPRITER* it;
1753
1754 assert(scip != NULL);
1755 assert(scip->mem != NULL);
1756 assert(expr != NULL);
1757 assert(hashval != NULL);
1758
1759 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1762
1763 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, expr, it, NULL) );
1764
1765 *hashval = SCIPexpriterGetExprUserData(it, expr).uintval;
1766
1767 SCIPexpriterFree(&it);
1768
1769 return SCIP_OKAY;
1770}
1771
1772/** simplifies an expression (duplication of long doxygen comment omitted here) */
1774 SCIP* scip, /**< SCIP data structure */
1775 SCIP_EXPR* rootexpr, /**< expression to be simplified */
1776 SCIP_EXPR** simplified, /**< buffer to store simplified expression */
1777 SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */
1778 SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */
1779 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1780 void* ownercreatedata /**< data to pass to ownercreate */
1781 )
1782{
1783 assert(scip != NULL);
1784 assert(scip->mem != NULL);
1785
1786 SCIP_CALL( SCIPexprSimplify(scip->set, scip->stat, scip->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) );
1787
1788 return SCIP_OKAY;
1789}
1790
1791/** retrieves symmetry information from an expression */
1793 SCIP* scip, /**< SCIP data structure */
1794 SCIP_EXPR* expr, /**< expression from which information needs to be retrieved */
1795 SYM_EXPRDATA** symdata /**< buffer to store symmetry data */
1796 )
1797{
1798 assert(scip != NULL);
1799 assert(expr != NULL);
1800 assert(symdata != NULL);
1801
1802 SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) );
1803
1804 return SCIP_OKAY;
1805}
1806
1807/** replaces common sub-expressions in a given expression graph by using a hash key for each expression
1808 *
1809 * The algorithm consists of two steps:
1810 *
1811 * 1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash
1812 *
1813 * 2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a
1814 * structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the
1815 * hash table, otherwise we add it to the hash table
1816 *
1817 * @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions
1818 * (with the same hash) are structurally the same we use the function SCIPexprCompare().
1819 */
1821 SCIP* scip, /**< SCIP data structure */
1822 SCIP_EXPR** exprs, /**< expressions (possibly replaced by equivalent on output) */
1823 int nexprs, /**< total number of expressions */
1824 SCIP_Bool* replacedroot /**< buffer to store whether any root expression (expression in exprs) was replaced */
1825 )
1826{
1827 COMMONSUBEXPR_HASH_DATA hashdata;
1828 SCIP_EXPRITER* hashiterator;
1829 SCIP_EXPRITER* repliterator;
1830 SCIP_MULTIHASH* key2expr;
1831 int i;
1832 int nvisitedexprs = 0;
1833
1834 assert(scip != NULL);
1835 assert(scip->mem != NULL);
1836 assert(exprs != NULL);
1837 assert(nexprs >= 0);
1838 assert(replacedroot != NULL);
1839
1840 *replacedroot = FALSE;
1841
1842 if( nexprs == 0 )
1843 return SCIP_OKAY;
1844
1845 SCIP_CALL( SCIPcreateExpriter(scip, &hashiterator) );
1848
1849 /* compute all hashes for each sub-expression */
1850 for( i = 0; i < nexprs; ++i )
1851 {
1852 assert(exprs[i] != NULL);
1853 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, exprs[i], hashiterator, &nvisitedexprs) );
1854 }
1855
1856 /* replace equivalent sub-expressions */
1857 hashdata.hashiterator = hashiterator;
1858 hashdata.set = scip->set;
1859 SCIP_CALL( SCIPmultihashCreate(&key2expr, scip->mem->probmem, nvisitedexprs,
1860 hashCommonSubexprGetKey, hashCommonSubexprEq, hashCommonSubexprKeyval, (void*)&hashdata) );
1861
1862 SCIP_CALL( SCIPcreateExpriter(scip, &repliterator) );
1863
1864 for( i = 0; i < nexprs; ++i )
1865 {
1866 SCIP_EXPR* newroot;
1867 SCIP_EXPR* newchild;
1868 SCIP_EXPR* child;
1869
1870 /* check the root for equivalence separately first */
1871 SCIP_CALL( findEqualExpr(scip->set, exprs[i], key2expr, &newroot) );
1872
1873 if( newroot != NULL )
1874 {
1875 assert(newroot != exprs[i]);
1876 assert(SCIPexprCompare(scip->set, exprs[i], newroot) == 0);
1877
1878 SCIPdebugMsg(scip, "replacing common root expression of %dth expr: %p -> %p\n", i, (void*)exprs[i], (void*)newroot);
1879
1880 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[i]) );
1881
1882 exprs[i] = newroot;
1883 SCIPexprCapture(newroot);
1884
1885 *replacedroot = TRUE;
1886
1887 continue;
1888 }
1889
1890 /* replace equivalent sub-expressions in the tree */
1891 SCIP_CALL( SCIPexpriterInit(repliterator, exprs[i], SCIP_EXPRITER_DFS, FALSE) );
1893
1894 while( !SCIPexpriterIsEnd(repliterator) )
1895 {
1896 child = SCIPexpriterGetChildExprDFS(repliterator);
1897 assert(child != NULL);
1898
1899 /* try to find an equivalent expression */
1900 SCIP_CALL( findEqualExpr(scip->set, child, key2expr, &newchild) );
1901
1902 /* replace child with newchild */
1903 if( newchild != NULL )
1904 {
1905 assert(child != newchild);
1906 assert(SCIPexprCompare(scip->set, child, newchild) == 0);
1907
1908 SCIPdebugMsg(scip, "replacing common child expression %p -> %p\n", (void*)child, (void*)newchild);
1909
1910 SCIP_CALL( SCIPreplaceExprChild(scip, SCIPexpriterGetCurrent(repliterator), SCIPexpriterGetChildIdxDFS(repliterator), newchild) );
1911
1912 (void) SCIPexpriterSkipDFS(repliterator);
1913 }
1914 else
1915 {
1916 (void) SCIPexpriterGetNext(repliterator);
1917 }
1918 }
1919 }
1920
1921 /* free memory */
1922 SCIPexpriterFree(&repliterator);
1923 SCIPmultihashFree(&key2expr);
1924 SCIPexpriterFree(&hashiterator);
1925
1926 return SCIP_OKAY;
1927}
1928
1929/** computes the curvature of a given expression and all its subexpressions
1930 *
1931 * @note this function also evaluates all subexpressions w.r.t. current variable bounds
1932 * @note this function relies on information from the curvature callback of expression handlers only,
1933 * consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity
1934 */
1936 SCIP* scip, /**< SCIP data structure */
1937 SCIP_EXPR* expr /**< expression */
1938 )
1939{
1940 SCIP_EXPRITER* it;
1941 SCIP_EXPRCURV curv;
1942 SCIP_EXPRCURV* childcurv;
1943 int childcurvsize;
1944 SCIP_Bool success;
1946 int i, c;
1947
1948 assert(scip != NULL);
1949 assert(scip->mem != NULL);
1950 assert(expr != NULL);
1951
1952 childcurvsize = 5;
1953 SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, childcurvsize) );
1954
1955 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1958
1959 for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
1960 {
1961 curv = SCIP_EXPRCURV_UNKNOWN;
1962
1964 {
1965 /* set curvature in expression */
1966 SCIPexprSetCurvature(expr, curv);
1967 continue;
1968 }
1969
1970 if( SCIPexprGetNChildren(expr) > childcurvsize )
1971 {
1972 childcurvsize = SCIPcalcMemGrowSize(scip, SCIPexprGetNChildren(expr));
1973 SCIP_CALL( SCIPreallocBufferArray(scip, &childcurv, childcurvsize) );
1974 }
1975
1976 for( i = 0; i < 3; ++i )
1977 {
1978 /* check if expression can have a curvature trialcurv[i] */
1979 SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, trialcurv[i], &success, childcurv) );
1980 if( !success )
1981 continue;
1982
1983 /* check if conditions on children are satisfied */
1984 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1985 {
1986 if( (childcurv[c] & SCIPexprGetCurvature(SCIPexprGetChildren(expr)[c])) != childcurv[c] )
1987 {
1988 success = FALSE;
1989 break;
1990 }
1991 }
1992
1993 if( success )
1994 {
1995 curv = trialcurv[i];
1996 break;
1997 }
1998 }
1999
2000 /* set curvature in expression */
2001 SCIPexprSetCurvature(expr, curv);
2002 }
2003
2004 SCIPexpriterFree(&it);
2005
2006 SCIPfreeBufferArray(scip, &childcurv);
2007
2008 return SCIP_OKAY;
2009}
2010
2011/** computes integrality information of a given expression and all its subexpressions
2012 *
2013 * The integrality information can be accessed via SCIPexprIsIntegral().
2014 */
2016 SCIP* scip, /**< SCIP data structure */
2017 SCIP_EXPR* expr /**< expression */
2018 )
2019{
2020 SCIP_EXPRITER* it;
2021 SCIP_Bool isintegral;
2022
2023 assert(scip != NULL);
2024 assert(scip->mem != NULL);
2025 assert(expr != NULL);
2026
2027 /* shortcut for expr without children */
2028 if( SCIPexprGetNChildren(expr) == 0 )
2029 {
2030 /* compute integrality information */
2031 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2032 SCIPexprSetIntegrality(expr, isintegral);
2033
2034 return SCIP_OKAY;
2035 }
2036
2037 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2040
2041 for( expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2042 {
2043 /* compute integrality information */
2044 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2045 SCIPexprSetIntegrality(expr, isintegral);
2046 }
2047
2048 SCIPexpriterFree(&it);
2049
2050 return SCIP_OKAY;
2051}
2052
2053/** returns the total number of variable expressions in an expression
2054 *
2055 * The function counts variable expressions in common sub-expressions only once, but
2056 * counts variables appearing in several variable expressions multiple times.
2057 */
2059 SCIP* scip, /**< SCIP data structure */
2060 SCIP_EXPR* expr, /**< expression */
2061 int* nvars /**< buffer to store the total number of variables */
2062 )
2063{
2064 SCIP_EXPRITER* it;
2065
2066 assert(scip != NULL);
2067 assert(scip->mem != NULL);
2068 assert(expr != NULL);
2069 assert(nvars != NULL);
2070
2071 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2073
2074 *nvars = 0;
2075 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2076 if( SCIPexprIsVar(scip->set, expr) )
2077 ++(*nvars);
2078
2079 SCIPexpriterFree(&it);
2080
2081 return SCIP_OKAY;
2082}
2083
2084/** returns all variable expressions contained in a given expression
2085 *
2086 * The array to store all variable expressions needs to be at least of size
2087 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars().
2088 *
2089 * If every variable is represented by only one variable expression (common subexpression have been removed)
2090 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars().
2091 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying,
2092 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars().
2093 *
2094 * @note function captures variable expressions
2095 */
2097 SCIP* scip, /**< SCIP data structure */
2098 SCIP_EXPR* expr, /**< expression */
2099 SCIP_EXPR** varexprs, /**< array to store all variable expressions */
2100 int* nvarexprs /**< buffer to store the total number of variable expressions */
2101 )
2102{
2103 SCIP_EXPRITER* it;
2104
2105 assert(scip != NULL);
2106 assert(scip->mem != NULL);
2107 assert(expr != NULL);
2108 assert(varexprs != NULL);
2109 assert(nvarexprs != NULL);
2110
2111 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2113
2114 *nvarexprs = 0;
2115 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2116 {
2117 assert(expr != NULL);
2118
2119 if( SCIPexprIsVar(scip->set, expr) )
2120 {
2121 varexprs[(*nvarexprs)++] = expr;
2122
2123 /* capture expression */
2124 SCIPcaptureExpr(expr);
2125 }
2126 }
2127
2128 /* @todo sort variable expressions here? */
2129
2130 SCIPexpriterFree(&it);
2131
2132 return SCIP_OKAY;
2133}
2134
2135/** calls the print callback for an expression
2136 *
2137 * @see SCIP_DECL_EXPRPRINT
2138 */
2139SCIP_DECL_EXPRPRINT(SCIPcallExprPrint)
2140{
2141 assert(scip != NULL);
2142
2143 SCIP_CALL( SCIPexprhdlrPrintExpr(SCIPexprGetHdlr(expr), scip->set, scip->messagehdlr, expr, stage, currentchild, parentprecedence, file) );
2144
2145 return SCIP_OKAY;
2146}
2147
2148/** calls the curvature callback for an expression
2149 *
2150 * @see SCIP_DECL_EXPRCURVATURE
2151 *
2152 * Returns unknown curvature if callback not implemented.
2153 */
2154SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature)
2155{
2156 assert(scip != NULL);
2157
2158 SCIP_CALL( SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), scip->set, expr, exprcurvature, success, childcurv) );
2159
2160 return SCIP_OKAY;
2161}
2162
2163/** calls the monotonicity callback for an expression
2164 *
2165 * @see SCIP_DECL_EXPRMONOTONICITY
2166 *
2167 * Returns unknown monotonicity if callback not implemented.
2168 */
2169SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity)
2170{
2171 assert(scip != NULL);
2172
2173 SCIP_CALL( SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), scip->set, expr, childidx, result) );
2174
2175 return SCIP_OKAY;
2176}
2177
2178/** calls the eval callback for an expression with given values for children
2179 *
2180 * Does not iterates over expressions, but requires values for children to be given.
2181 * Value is not stored in expression, but returned in `val`.
2182 * If an evaluation error (division by zero, ...) occurs, this value will
2183 * be set to `SCIP_INVALID`.
2184 */
2186 SCIP* scip, /**< SCIP data structure */
2187 SCIP_EXPR* expr, /**< expression to be evaluated */
2188 SCIP_Real* childrenvalues, /**< values for children */
2189 SCIP_Real* val /**< buffer to store evaluated value */
2190 )
2191{
2192 assert(scip != NULL);
2193 assert(scip->mem != NULL);
2194 assert(childrenvalues != NULL);
2195 assert(val != NULL);
2196
2197 SCIP_CALL( SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, childrenvalues, NULL) );
2198
2199 return SCIP_OKAY;
2200}
2201
2202/** calls the eval and fwdiff callback of an expression with given values for children
2203 *
2204 * Does not iterates over expressions, but requires values for children and direction to be given.
2205 *
2206 * Value is not stored in expression, but returned in `val`.
2207 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2208 *
2209 * Direction is not stored in expression, but returned in `dot`.
2210 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2211 */
2213 SCIP* scip, /**< SCIP data structure */
2214 SCIP_EXPR* expr, /**< expression to be evaluated */
2215 SCIP_Real* childrenvalues, /**< values for children */
2216 SCIP_Real* direction, /**< direction in which to differentiate */
2217 SCIP_Real* val, /**< buffer to store evaluated value */
2218 SCIP_Real* dot /**< buffer to store derivative value */
2219 )
2220{
2221 assert(scip != NULL);
2222 assert(scip->mem != NULL);
2223
2224 SCIP_CALL( SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, dot,
2225 childrenvalues, NULL, direction, NULL) );
2226
2227 return SCIP_OKAY;
2228}
2229
2230/** calls the interval evaluation callback for an expression
2231 *
2232 * @see SCIP_DECL_EXPRINTEVAL
2233 *
2234 * Returns entire interval if callback not implemented.
2235 */
2236SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval)
2237{
2238 assert(scip != NULL);
2239
2240 SCIP_CALL( SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), scip->set, expr, interval, intevalvar, intevalvardata) );
2241
2242 return SCIP_OKAY;
2243}
2244
2245/** calls the estimate callback for an expression
2246 *
2247 * @see SCIP_DECL_EXPRESTIMATE
2248 *
2249 * Returns without success if callback not implemented.
2250 */
2251SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate)
2252{
2253 assert(scip != NULL);
2254
2255 SCIP_CALL( SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), scip->set, expr, localbounds, globalbounds, refpoint,
2256 overestimate, targetvalue, coefs, constant, islocal, success, branchcand) );
2257
2258 return SCIP_OKAY;
2259}
2260
2261/** calls the initial estimators callback for an expression
2262 *
2263 * @see SCIP_DECL_EXPRINITESTIMATES
2264 *
2265 * Returns no estimators if callback not implemented.
2266 */
2267SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates)
2268{
2269 assert(scip != NULL);
2270
2271 SCIP_CALL( SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, overestimate, coefs,
2272 constant, nreturned) );
2273
2274 return SCIP_OKAY;
2275}
2276
2277/** calls the simplify callback for an expression
2278 *
2279 * @see SCIP_DECL_EXPRSIMPLIFY
2280 *
2281 * Returns unmodified expression if simplify callback not implemented.
2282 *
2283 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that.
2284 */
2285SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify)
2286{
2287 assert(scip != NULL);
2288
2289 /* use simplification of expression handlers */
2290 SCIP_CALL( SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), scip->set, expr, simplifiedexpr, ownercreate,
2291 ownercreatedata) );
2292
2293 return SCIP_OKAY;
2294}
2295
2296/** calls the reverse propagation callback for an expression
2297 *
2298 * @see SCIP_DECL_EXPRREVERSEPROP
2299 *
2300 * Returns unmodified childrenbounds if reverseprop callback not implemented.
2301 */
2302SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop)
2303{
2304 assert(scip != NULL);
2305
2306 SCIP_CALL( SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, childrenbounds, infeasible) );
2307
2308 return SCIP_OKAY;
2309}
2310
2311/** calls the symmetry data callback for an expression
2312 *
2313 * Returns no information if not implemented.
2314 */
2315SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData)
2316{
2317 assert(scip != NULL);
2318 assert(expr != NULL);
2319 assert(symdata != NULL);
2320
2321 SCIP_CALL( SCIPexprGetSymData(scip->set, expr, symdata) );
2322
2323 return SCIP_OKAY;
2324}
2325
2326/**@} */
2327
2328/**@name Expression Iterator Methods */
2329/**@{ */
2330
2331#ifdef NDEBUG
2332#undef SCIPcreateExpriter
2333#undef SCIPfreeExpriter
2334#endif
2335
2336/** creates an expression iterator */
2338 SCIP* scip, /**< SCIP data structure */
2339 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */
2340 )
2341{
2342 assert(scip != NULL);
2343 assert(scip->mem != NULL);
2344
2345 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, iterator) );
2346
2347 return SCIP_OKAY;
2348}
2349
2350/** frees an expression iterator */
2352 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */
2353 )
2354{
2355 SCIPexpriterFree(iterator);
2356}
2357
2358/**@} */
2359
2360
2361/**@name Quadratic expression functions */
2362/**@{ */
2363
2364#ifdef NDEBUG
2365#undef SCIPcheckExprQuadratic
2366#undef SCIPfreeExprQuadratic
2367#undef SCIPcomputeExprQuadraticCurvature
2368#endif
2369
2370/** checks whether an expression is quadratic
2371 *
2372 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions),
2373 * or a sum of terms where at least one is a square or a product.
2374 *
2375 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic.
2376 */
2378 SCIP* scip, /**< SCIP data structure */
2379 SCIP_EXPR* expr, /**< expression */
2380 SCIP_Bool* isquadratic /**< buffer to store result */
2381 )
2382{
2383 assert(scip != NULL);
2384 assert(scip->mem != NULL);
2385
2386 SCIP_CALL( SCIPexprCheckQuadratic(scip->set, scip->mem->probmem, expr, isquadratic) );
2387
2388 return SCIP_OKAY;
2389}
2390
2391/** frees information on quadratic representation of an expression
2392 *
2393 * Before doing changes to an expression, it can be useful to call this function.
2394 */
2396 SCIP* scip, /**< SCIP data structure */
2397 SCIP_EXPR* expr /**< expression */
2398 )
2399{
2400 assert(scip != NULL);
2401 assert(scip->mem != NULL);
2402
2403 SCIPexprFreeQuadratic(scip->mem->probmem, expr);
2404}
2405
2406/** evaluates quadratic term in a solution
2407 *
2408 * \note This requires that every expression used in the quadratic data is a variable expression.
2409 */
2411 SCIP* scip, /**< SCIP data structure */
2412 SCIP_EXPR* expr, /**< quadratic expression */
2413 SCIP_SOL* sol /**< solution to evaluate, or NULL for LP solution */
2414 )
2415{
2416 SCIP_Real auxvalue;
2417 int nlinexprs;
2418 SCIP_Real* lincoefs;
2419 SCIP_EXPR** linexprs;
2420 int nquadexprs;
2421 int nbilinexprs;
2422 int i;
2423
2424 assert(scip != NULL);
2425 assert(expr != NULL);
2426
2427 SCIPexprGetQuadraticData(expr, &auxvalue, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2428
2429 /* linear terms */
2430 for( i = 0; i < nlinexprs; ++i )
2431 {
2432 assert(SCIPexprIsVar(scip->set, linexprs[i]));
2433 auxvalue += lincoefs[i] * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(linexprs[i]));
2434 }
2435
2436 /* quadratic terms */
2437 for( i = 0; i < nquadexprs; ++i )
2438 {
2439 SCIP_EXPR* quadexprterm;
2440 SCIP_Real lincoef;
2441 SCIP_Real sqrcoef;
2442 SCIP_Real solval;
2443
2444 SCIPexprGetQuadraticQuadTerm(expr, i, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2445
2446 assert(SCIPexprIsVar(scip->set, quadexprterm));
2447
2448 solval = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(quadexprterm));
2449 auxvalue += (lincoef + sqrcoef * solval) * solval;
2450 }
2451
2452 /* bilinear terms */
2453 for( i = 0; i < nbilinexprs; ++i )
2454 {
2455 SCIP_EXPR* expr1;
2456 SCIP_EXPR* expr2;
2457 SCIP_Real coef;
2458
2459 SCIPexprGetQuadraticBilinTerm(expr, i, &expr1, &expr2, &coef, NULL, NULL);
2460
2461 assert(SCIPexprIsVar(scip->set, expr1));
2462 assert(SCIPexprIsVar(scip->set, expr2));
2463 auxvalue += coef * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr1)) * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr2));
2464 }
2465
2466 return auxvalue;
2467}
2468
2469/** prints quadratic expression */
2471 SCIP* scip, /**< SCIP data structure */
2472 SCIP_EXPR* expr /**< quadratic expression */
2473 )
2474{
2475 SCIP_Real constant;
2476 int nlinexprs;
2477 SCIP_Real* lincoefs;
2478 SCIP_EXPR** linexprs;
2479 int nquadexprs;
2480 int nbilinexprs;
2481 int c;
2482
2483 assert(scip != NULL);
2484 assert(expr != NULL);
2485
2486 SCIPexprGetQuadraticData(expr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2487
2488 SCIPinfoMessage(scip, NULL, "Constant: %g\n", constant);
2489
2490 SCIPinfoMessage(scip, NULL, "Linear: ");
2491 for( c = 0; c < nlinexprs; ++c )
2492 {
2493 SCIPinfoMessage(scip, NULL, "%g * ", lincoefs[c]);
2494 SCIP_CALL( SCIPprintExpr(scip, linexprs[c], NULL) );
2495 if( c < nlinexprs - 1 )
2496 SCIPinfoMessage(scip, NULL, " + ");
2497 }
2498 SCIPinfoMessage(scip, NULL, "\n");
2499
2500 SCIPinfoMessage(scip, NULL, "Quadratic: ");
2501 for( c = 0; c < nquadexprs; ++c )
2502 {
2503 SCIP_EXPR* quadexprterm;
2504 SCIP_Real lincoef;
2505 SCIP_Real sqrcoef;
2506
2507 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2508 SCIPinfoMessage(scip, NULL, "(%g * sqr(", sqrcoef);
2509 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2510 SCIPinfoMessage(scip, NULL, ") + %g) * ", lincoef);
2511 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2512 if( c < nquadexprs - 1 )
2513 SCIPinfoMessage(scip, NULL, " + ");
2514 }
2515 SCIPinfoMessage(scip, NULL, "\n");
2516
2517 if( nbilinexprs == 0 )
2518 {
2519 SCIPinfoMessage(scip, NULL, "Bilinear: none\n");
2520 return SCIP_OKAY;
2521 }
2522
2523 SCIPinfoMessage(scip, NULL, "Bilinear: ");
2524 for( c = 0; c < nbilinexprs; ++c )
2525 {
2526 SCIP_EXPR* expr1;
2527 SCIP_EXPR* expr2;
2528 SCIP_Real coef;
2529
2530 SCIPexprGetQuadraticBilinTerm(expr, c, &expr1, &expr2, &coef, NULL, NULL);
2531
2532 SCIPinfoMessage(scip, NULL, "%g * ", coef);
2533 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2534 SCIPinfoMessage(scip, NULL, " * ");
2535 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2536 if( c < nbilinexprs - 1 )
2537 SCIPinfoMessage(scip, NULL, " + ");
2538 }
2539 SCIPinfoMessage(scip, NULL, "\n");
2540
2541 SCIPinfoMessage(scip, NULL, "Bilinear of quadratics: \n");
2542 for( c = 0; c < nquadexprs; ++c )
2543 {
2544 SCIP_EXPR* quadexprterm;
2545 int nadjbilin;
2546 int* adjbilin;
2547 int i;
2548
2549 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, NULL, NULL, &nadjbilin, &adjbilin, NULL);
2550
2551 SCIPinfoMessage(scip, NULL, " For ");
2552 SCIP_CALL( SCIPprintExpr(scip, quadexprterm, NULL) );
2553 SCIPinfoMessage(scip, NULL, " we see: ");
2554 for( i = 0; i < nadjbilin; ++i )
2555 {
2556 SCIP_EXPR* expr1;
2557 SCIP_EXPR* expr2;
2558 SCIP_Real coef;
2559
2560 SCIPexprGetQuadraticBilinTerm(expr, adjbilin[i], &expr1, &expr2, &coef, NULL, NULL);
2561
2562 SCIPinfoMessage(scip, NULL, "%g * ", coef);
2563 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2564 SCIPinfoMessage(scip, NULL, " * ");
2565 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2566 if( i < nadjbilin - 1 )
2567 SCIPinfoMessage(scip, NULL, " + ");
2568 }
2569 SCIPinfoMessage(scip, NULL, "\n");
2570 }
2571
2572 return SCIP_OKAY;
2573}
2574
2575/** checks the curvature of the quadratic expression
2576 *
2577 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
2578 * If Q is
2579 * - semidefinite positive -> curv is set to convex,
2580 * - semidefinite negative -> curv is set to concave,
2581 * - otherwise -> curv is set to unknown.
2582 *
2583 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
2584 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
2585 */
2587 SCIP* scip, /**< SCIP data structure */
2588 SCIP_EXPR* expr, /**< quadratic expression */
2589 SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */
2590 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
2591 SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */
2592 )
2593{
2594 assert(scip != NULL);
2595 assert(scip->mem != NULL);
2596
2597 SCIP_CALL( SCIPexprComputeQuadraticCurvature(scip->set, scip->mem->probmem, scip->mem->buffer, scip->messagehdlr,
2598 expr, curv, assumevarfixed, storeeigeninfo) );
2599
2600 return SCIP_OKAY;
2601}
2602
2603/**@} */
2604
2605/**@name Monomial expression functions */
2606/**@{ */
2607
2608#ifdef NDEBUG
2609#undef SCIPgetExprMonomialData
2610#endif
2611
2612/** returns a monomial representation of a product expression
2613 *
2614 * The array to store all factor expressions needs to be of size the number of
2615 * children in the expression which is given by SCIPexprGetNChildren().
2616 *
2617 * Given a non-trivial monomial expression, the function finds its representation as \f$cx^\alpha\f$, where
2618 * \f$c\f$ is a real coefficient, \f$x\f$ is a vector of auxiliary or original variables (where some entries can
2619 * be NULL is the auxiliary variable has not been created yet), and \f$\alpha\f$ is a real vector of exponents.
2620 *
2621 * A non-trivial monomial is a product of a least two expressions.
2622 */
2624 SCIP* scip, /**< SCIP data structure */
2625 SCIP_EXPR* expr, /**< expression */
2626 SCIP_Real* coef, /**< coefficient \f$c\f$ */
2627 SCIP_Real* exponents, /**< exponents \f$\alpha\f$ */
2628 SCIP_EXPR** factors /**< factor expressions \f$x\f$ */
2629 )
2630{
2631 assert(scip != NULL);
2632 assert(scip->mem != NULL);
2633
2634 SCIP_CALL( SCIPexprGetMonomialData(scip->set, scip->mem->probmem, expr, coef, exponents, factors) );
2635
2636 return SCIP_OKAY;
2637}
2638
2639/**@} */
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_SPACECONTROL
Definition: def.h:289
#define SCIP_Bool
Definition: def.h:91
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition: def.h:395
#define SCIP_CALL(x)
Definition: def.h:374
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:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
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:1993
SCIP_RETCODE SCIPmultihashInsert(SCIP_MULTIHASH *multihash, void *element)
Definition: misc.c:2024
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:1960
void * SCIPmultihashRetrieveNext(SCIP_MULTIHASH *multihash, SCIP_MULTIHASHLIST **multihashlist, void *key)
Definition: misc.c:2113
int SCIPgetNExprhdlrs(SCIP *scip)
Definition: scip_expr.c:857
SCIP_Bool SCIPexprhdlrHasCurvature(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:655
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct(SCIP *scip)
Definition: scip_expr.c:913
SCIP_EXPRHDLR * SCIPgetExprhdlrVar(SCIP *scip)
Definition: scip_expr.c:880
SCIP_EXPRHDLR ** SCIPgetExprhdlrs(SCIP *scip)
Definition: scip_expr.c:846
SCIP_EXPRHDLR * SCIPgetExprhdlrValue(SCIP *scip)
Definition: scip_expr.c:891
SCIP_EXPRHDLR * SCIPgetExprhdlrSum(SCIP *scip)
Definition: scip_expr.c:902
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:823
SCIP_EXPRHDLR * SCIPgetExprhdlrPower(SCIP *scip)
Definition: scip_expr.c:924
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:868
SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity)
Definition: scip_expr.c:2169
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:1033
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:1141
SCIP_RETCODE SCIPgetSymDataExpr(SCIP *scip, SCIP_EXPR *expr, SYM_EXPRDATA **symdata)
Definition: scip_expr.c:1792
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:974
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition: scip_expr.c:1230
SCIP_RETCODE SCIPevalExprHessianDir(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag, SCIP_SOL *direction)
Definition: scip_expr.c:1689
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1635
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3860
SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval)
Definition: scip_expr.c:2236
SCIP_RETCODE SCIPprintExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:2470
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:2015
SCIP_DECL_EXPRPRINT(SCIPcallExprPrint)
Definition: scip_expr.c:2139
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1464
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1667
SCIP_RETCODE SCIPprintExprDotInit2(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, const char *filename, SCIP_EXPRPRINT_WHAT whattoprint)
Definition: scip_expr.c:1517
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:969
SCIP_Longint SCIPgetExprNewSoltag(SCIP *scip)
Definition: scip_expr.c:1651
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:1453
SCIP_RETCODE SCIPgetExprMonomialData(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)
Definition: scip_expr.c:2623
SCIP_RETCODE SCIPgetExprNVars(SCIP *scip, SCIP_EXPR *expr, int *nvars)
Definition: scip_expr.c:2058
SCIP_RETCODE SCIPduplicateExprShallow(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1301
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:1248
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1442
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:995
void SCIPfreeExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:2395
SCIP_RETCODE SCIPprintExprDot(SCIP *scip, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
Definition: scip_expr.c:1533
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1734
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
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:1431
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:1380
SCIP_RETCODE SCIPhashExpr(SCIP *scip, SCIP_EXPR *expr, unsigned int *hashval)
Definition: scip_expr.c:1746
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition: scip_expr.c:2586
SCIP_DECL_EXPRGETSYMDATA(SCIPcallExprGetSymData)
Definition: scip_expr.c:2315
SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature)
Definition: scip_expr.c:2154
SCIP_RETCODE SCIPcallExprEval(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
Definition: scip_expr.c:2185
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:2337
SCIP_RETCODE SCIPcallExprEvalFwdiff(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *direction, SCIP_Real *val, SCIP_Real *dot)
Definition: scip_expr.c:2212
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:1486
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:1475
SCIP_RETCODE SCIPreplaceCommonSubexpressions(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Bool *replacedroot)
Definition: scip_expr.c:1820
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:858
SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify)
Definition: scip_expr.c:2285
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition: scip_expr.c:2377
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3870
SCIP_RETCODE SCIPprintExprDotFinal(SCIP *scip, SCIP_EXPRPRINTDATA **printdata)
Definition: scip_expr.c:1547
SCIP_RETCODE SCIPprintExprDotInit(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
Definition: scip_expr.c:1501
SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate)
Definition: scip_expr.c:2251
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:1318
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:416
SCIP_RETCODE SCIPshowExpr(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1569
SCIP_Real SCIPevalExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol)
Definition: scip_expr.c:2410
SCIP_RETCODE SCIPcomputeExprCurvature(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1935
SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop)
Definition: scip_expr.c:2302
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:2267
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2351
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:1281
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1409
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:2096
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:1608
SCIP_RETCODE SCIPremoveExprChildren(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1267
SCIP_RETCODE SCIPsimplifyExpr(SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1773
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
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:1217
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:17419
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition: misc.c:10977
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
#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