SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2023 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;
86
87 assert(sourcescip != NULL);
92
94
95 if( !SCIPisExprVar(sourcescip, sourceexpr) )
96 return SCIP_OKAY;
97
99
101 data->consmap, data->global, &valid) );
103
104 /* if copy was not valid, store so in mapvar data */
105 if( !valid )
106 data->valid = FALSE;
107
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 */
203 {
204 debugParse("Variable <%s> has already been parsed, capturing its expression\n", SCIPvarGetName(var));
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 */
216 }
217 }
218 else if( *expr == '(' )
219 {
220 /* parse expression */
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);
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);
245 }
246 else if( isalpha(*expr) )
247 {
248 /* a (function) name is coming, should find exprhandler with such name */
249 int i;
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 */
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;
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{
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
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");
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);
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);
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);
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);
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 {
424 }
425 else
426 /* Factor consists of this unique Base */
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{
449
450 debugParse("parsing term from %s\n", expr);
451
452 /* parse Factor */
453 /* ignore whitespace */
454 SCIP_CALL( SCIPskipSpace((char**)&expr) );
455
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 */
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;
481
482 /* release termtree, if parseFactor fails with a read-error */
483 if( retcode == SCIP_READERROR )
484 {
486 }
487 SCIP_CALL( retcode );
488
489 /* append newly created factor */
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 */
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;
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
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 */
558 }
559 else
560 {
561 /* initialize exprtree as a sum expression with a single term, so we can append the following terms */
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 /* no '*', so fall back to parsing term after sign */
580 coef = (*expr == '+') ? 1.0 : -1.0;
581 ++expr;
582 }
583 else
584 {
585 /* keep coefficient in coef and continue parsing term after coefficient */
586 expr = (*newpos)+1;
587
588 SCIP_CALL( SCIPskipSpace((char**)&expr) );
589 }
590 }
591 else
592 {
593 coef = (*expr == '+') ? 1.0 : -1.0;
594 ++expr;
595 }
596
597 debugParse("while parsing expression, read coefficient %g\n", coef); /*lint !e506 !e681*/
598
600
601 /* release exprtree if parseTerm fails with an read-error */
602 if( retcode == SCIP_READERROR )
603 {
605 }
606 SCIP_CALL( retcode );
607
608 /* append newly created term */
611
612 /* find next symbol */
613 expr = *newpos;
614 SCIP_CALL( SCIPskipSpace((char**)&expr) );
615 } while( *expr == '+' || *expr == '-' );
616 }
617 else
618 {
619 /* Expr consists of this unique ['+' | '-'] Term */
620 if( sign < 0.0 )
621 {
622 assert(sign == -1.0);
625 }
626 else
628 }
629
630 *newpos = expr;
631
632 return SCIP_OKAY;
633}
634
635/** @} */ /* end of parsing methods */
636
637/** @name Simplify methods (internal)
638 * @{
639 */
640
641/** returns an equivalent expression for a given expression if possible
642 *
643 * it adds the expression to key2expr if the map does not contain the key
644 */
645static
647 SCIP_SET* set, /**< global SCIP settings */
648 SCIP_EXPR* expr, /**< expression to replace */
649 SCIP_MULTIHASH* key2expr, /**< mapping of hashes to expressions */
650 SCIP_EXPR** newexpr /**< pointer to store an equivalent expression (NULL if there is none) */
651 )
652{ /*lint --e{438}*/
654
655 assert(set != NULL);
656 assert(expr != NULL);
657 assert(key2expr != NULL);
658 assert(newexpr != NULL);
659
660 *newexpr = NULL;
662 do
663 {
664 /* search for an equivalent expression */
666
667 if( *newexpr == NULL )
668 {
669 /* processed all expressions like expr from hash table, so insert expr */
670 SCIP_CALL( SCIPmultihashInsert(key2expr, (void*) expr) );
671 break;
672 }
673 else if( expr != *newexpr )
674 {
675 assert(SCIPexprCompare(set, expr, *newexpr) == 0);
676 break;
677 }
678 else
679 {
680 /* can not replace expr since it is already contained in the hashtablelist */
681 assert(expr == *newexpr);
682 *newexpr = NULL;
683 break;
684 }
685 }
686 while( TRUE ); /*lint !e506*/
687
688 return SCIP_OKAY;
689}
690
691/** userdata for multihash for common subexpression */
697
698/** get key of hash element */
699static
701{
702 return elem;
703} /*lint !e715*/
704
705/** checks if two expressions are structurally the same */
706static
708{
710 SCIP_EXPR* expr1;
711 SCIP_EXPR* expr2;
712
713 data = (COMMONSUBEXPR_HASH_DATA*)userptr;
714 assert(data != NULL);
715
716 expr1 = (SCIP_EXPR*)key1;
717 expr2 = (SCIP_EXPR*)key2;
718 assert(expr1 != NULL);
719 assert(expr2 != NULL);
720
721 return expr1 == expr2 || SCIPexprCompare(data->set, expr1, expr2) == 0;
722} /*lint !e715*/
723
724/** get value of hash element when comparing with another expression */
725static
727{
729 SCIP_EXPR* expr;
730
731 expr = (SCIP_EXPR*) key;
732 assert(expr != NULL);
733
734 data = (COMMONSUBEXPR_HASH_DATA*) userptr;
735 assert(data != NULL);
736
738} /*lint !e715*/
739
740/** hashes an expression using an already existing iterator
741 *
742 * The iterator must by of type DFS with allowrevisit=FALSE and only the leaveexpr stage enabled.
743 * The hashes of all visited expressions will be stored in the iterators expression data.
744 */
745static
747 SCIP_SET* set, /**< global SCIP settings */
748 BMS_BUFMEM* bufmem, /**< buffer memory */
749 SCIP_EXPR* expr, /**< expression to hash */
750 SCIP_EXPRITER* hashiterator, /**< iterator to use for hashing */
751 int* nvisitedexprs /**< counter to increment by the number of expressions visited, or NULL */
752 )
753{
754 SCIP_EXPRITER_USERDATA iterdata;
755 unsigned int* childrenhashes;
757 int i;
758
759 assert(set != NULL);
760 assert(expr != NULL);
761 assert(hashiterator != NULL);
762
765
766 for( expr = SCIPexpriterRestartDFS(hashiterator, expr); !SCIPexpriterIsEnd(hashiterator); expr = SCIPexpriterGetNext(hashiterator) ) /*lint !e441*/
767 {
769
770 if( nvisitedexprs != NULL )
771 ++*nvisitedexprs;
772
773 /* collect hashes of children */
775 {
778 }
779 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
780 childrenhashes[i] = SCIPexpriterGetExprUserData(hashiterator, SCIPexprGetChildren(expr)[i]).uintval;
781
783
784 SCIPexpriterSetCurrentUserData(hashiterator, iterdata);
785 }
786
788
789 return SCIP_OKAY;
790}
791
792/** @} */ /* end of simplify methods */
793
794/*
795 * public functions
796 */
797
798/**@addtogroup PublicExprHandlerMethods
799 * @{
800 */
801
802#ifdef NDEBUG
803#undef SCIPgetExprhdlrs
804#undef SCIPgetNExprhdlrs
805#undef SCIPfindExprhdlr
806#undef SCIPgetExprhdlrVar
807#undef SCIPgetExprhdlrValue
808#undef SCIPgetExprhdlrSum
809#undef SCIPgetExprhdlrProduct
810#undef SCIPgetExprhdlrPower
811#endif
812
813/** creates the handler for an expression handler and includes it into SCIP */
815 SCIP* scip, /**< SCIP data structure */
816 SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */
817 const char* name, /**< name of expression handler (must not be NULL) */
818 const char* desc, /**< description of expression handler (can be NULL) */
819 unsigned int precedence, /**< precedence of expression operation (used for printing) */
820 SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */
821 SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */
822 )
823{
824 assert(scip != NULL);
825 assert(scip->mem != NULL);
826 assert(exprhdlr != NULL);
827
828 SCIP_CALL( SCIPexprhdlrCreate(scip->mem->setmem, exprhdlr, name, desc, precedence, eval, data) );
829 assert(*exprhdlr != NULL);
830
831 SCIP_CALL( SCIPsetIncludeExprhdlr(scip->set, *exprhdlr) );
832
833 return SCIP_OKAY;
834}
835
836/** gives expression handlers */
838 SCIP* scip /**< SCIP data structure */
839 )
840{
841 assert(scip != NULL);
842 assert(scip->set != NULL);
843
844 return scip->set->exprhdlrs;
845}
846
847/** gives number of expression handlers */
849 SCIP* scip /**< SCIP data structure */
850 )
851{
852 assert(scip != NULL);
853 assert(scip->set != NULL);
854
855 return scip->set->nexprhdlrs;
856}
857
858/** returns an expression handler of a given name (or NULL if not found) */
860 SCIP* scip, /**< SCIP data structure */
861 const char* name /**< name of expression handler */
862 )
863{
864 assert(scip != NULL);
865 assert(scip->set != NULL);
866
867 return SCIPsetFindExprhdlr(scip->set, name);
868}
869
870/** returns expression handler for variable expressions (or NULL if not included) */
872 SCIP* scip /**< SCIP data structure */
873 )
874{
875 assert(scip != NULL);
876 assert(scip->set != NULL);
877
878 return scip->set->exprhdlrvar;
879}
880
881/** returns expression handler for constant value expressions (or NULL if not included) */
883 SCIP* scip /**< SCIP data structure */
884 )
885{
886 assert(scip != NULL);
887 assert(scip->set != NULL);
888
889 return scip->set->exprhdlrval;
890}
891
892/** returns expression handler for sum expressions (or NULL if not included) */
894 SCIP* scip /**< SCIP data structure */
895 )
896{
897 assert(scip != NULL);
898 assert(scip->set != NULL);
899
900 return scip->set->exprhdlrsum;
901}
902
903/** returns expression handler for product expressions (or NULL if not included) */
905 SCIP* scip /**< SCIP data structure */
906 )
907{
908 assert(scip != NULL);
909 assert(scip->set != NULL);
910
911 return scip->set->exprhdlrproduct;
912}
913
914/** returns expression handler for power expressions (or NULL if not included) */
916 SCIP* scip /**< SCIP data structure */
917 )
918{
919 assert(scip != NULL);
920 assert(scip->set != NULL);
921
922 return scip->set->exprhdlrpow;
923}
924
925/**@} */
926
927
928/**@name Expression Methods */
929/**@{ */
930
931#ifdef NDEBUG
932#undef SCIPappendExprChild
933#undef SCIPreplaceExprChild
934#undef SCIPremoveExprChildren
935#undef SCIPduplicateExpr
936#undef SCIPduplicateExprShallow
937#undef SCIPcaptureExpr
938#undef SCIPreleaseExpr
939#undef SCIPisExprVar
940#undef SCIPisExprValue
941#undef SCIPisExprSum
942#undef SCIPisExprProduct
943#undef SCIPisExprPower
944#undef SCIPprintExpr
945#undef SCIPevalExpr
946#undef SCIPgetExprNewSoltag
947#undef SCIPevalExprGradient
948#undef SCIPevalExprHessianDir
949#undef SCIPevalExprActivity
950#undef SCIPcompareExpr
951#undef SCIPsimplifyExpr
952#undef SCIPcallExprCurvature
953#undef SCIPcallExprMonotonicity
954#undef SCIPcallExprEval
955#undef SCIPcallExprEvalFwdiff
956#undef SCIPcallExprInteval
957#undef SCIPcallExprEstimate
958#undef SCIPcallExprInitestimates
959#undef SCIPcallExprSimplify
960#undef SCIPcallExprReverseprop
961#endif
962
963/** creates and captures an expression with given expression data and children */
965 SCIP* scip, /**< SCIP data structure */
966 SCIP_EXPR** expr, /**< pointer where to store expression */
967 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
968 SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */
969 int nchildren, /**< number of children */
970 SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */
971 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
972 void* ownercreatedata /**< data to pass to ownercreate */
973 )
974{
975 assert(scip != NULL);
976 assert(scip->set != NULL);
977
978 SCIP_CALL( SCIPexprCreate(scip->set, scip->mem->probmem, expr, exprhdlr, exprdata, nchildren, children, ownercreate,
980
981 return SCIP_OKAY;
982}
983
984/** creates and captures an expression with given expression data and up to two children */
986 SCIP* scip, /**< SCIP data structure */
987 SCIP_EXPR** expr, /**< pointer where to store expression */
988 SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
989 SCIP_EXPRDATA* exprdata, /**< expression data */
990 SCIP_EXPR* child1, /**< first child (can be NULL) */
991 SCIP_EXPR* child2, /**< second child (can be NULL) */
992 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
993 void* ownercreatedata /**< data to pass to ownercreate */
994 )
995{
996 assert(scip != NULL);
997 assert(expr != NULL);
998 assert(exprhdlr != NULL);
999
1000 if( child1 != NULL && child2 != NULL )
1001 {
1002 SCIP_EXPR* pair[2];
1003 pair[0] = child1;
1004 pair[1] = child2;
1005
1006 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 2, pair, ownercreate, ownercreatedata) );
1007 }
1008 else if( child2 == NULL )
1009 {
1010 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, child1 == NULL ? 0 : 1, &child1, ownercreate,
1011 ownercreatedata) );
1012 }
1013 else
1014 {
1015 /* child2 != NULL, child1 == NULL */
1016 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child2, ownercreate, ownercreatedata) );
1017 }
1018
1019 return SCIP_OKAY;
1020}
1021
1022/** creates and captures an expression representing a quadratic function */
1024 SCIP* scip, /**< SCIP data structure */
1025 SCIP_EXPR** expr, /**< pointer where to store expression */
1026 int nlinvars, /**< number of linear terms */
1027 SCIP_VAR** linvars, /**< array with variables in linear part */
1028 SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part */
1029 int nquadterms, /**< number of quadratic terms */
1030 SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms */
1031 SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms */
1032 SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms */
1033 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1034 void* ownercreatedata /**< data to pass to ownercreate */
1035 )
1036{
1037 SCIP_EXPR** children;
1038 SCIP_Real* coefs;
1039 int i;
1040
1041 assert(scip != NULL);
1042 assert(expr != NULL);
1043 assert(nlinvars == 0 || (linvars != NULL && lincoefs != NULL));
1044 assert(nquadterms == 0 || (quadvars1 != NULL && quadvars2 != NULL && quadcoefs != NULL));
1045
1046 /* allocate memory */
1047 SCIP_CALL( SCIPallocBufferArray(scip, &children, nquadterms + nlinvars) );
1048 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nquadterms + nlinvars) );
1049
1050 /* create children for quadratic terms */
1051 for( i = 0; i < nquadterms; ++i )
1052 {
1053 assert(quadvars1 != NULL && quadvars1[i] != NULL);
1054 assert(quadvars2 != NULL && quadvars2[i] != NULL);
1055
1056 /* quadratic term */
1057 if( quadvars1[i] == quadvars2[i] )
1058 {
1060
1061 /* create variable expression; intentionally not using createExprVar here,
1062 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1063 */
1065
1066 /* create pow expression */
1068
1069 /* release variable expression; note that the variable expression is still captured by children[i] */
1071 }
1072 else /* bilinear term */
1073 {
1074 SCIP_EXPR* exprs[2];
1075
1076 /* create variable expressions; intentionally not using createExprVar here,
1077 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1078 */
1081
1082 /* create product expression */
1083 SCIP_CALL( SCIPcreateExprProduct(scip, &children[i], 2, exprs, 1.0, ownercreate, ownercreatedata) );
1084
1085 /* release variable expressions; note that the variable expressions are still captured by children[i] */
1086 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[1]) );
1087 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[0]) );
1088 }
1089
1090 /* store coefficient */
1091 coefs[i] = quadcoefs[i];
1092 }
1093
1094 /* create children for linear terms */
1095 for( i = 0; i < nlinvars; ++i )
1096 {
1097 assert(linvars != NULL && linvars[i] != NULL);
1098
1099 /* create variable expression; intentionally not using createExprVar here,
1100 * since expression created here is not part of a constraint (they will be copied when a constraint is created);
1101 * release variable expression after the sum expression has been created
1102 */
1104
1105 /* store coefficient */
1106 coefs[nquadterms + i] = lincoefs[i];
1107 }
1108
1109 /* create sum expression */
1110 SCIP_CALL( SCIPcreateExprSum(scip, expr, nquadterms + nlinvars, children, coefs, 0.0, ownercreate, ownercreatedata) );
1111
1112 /* release children */
1113 for( i = 0; i < nquadterms + nlinvars; ++i )
1114 {
1115 assert(children[i] != NULL);
1116 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1117 }
1118
1119 /* free memory */
1120 SCIPfreeBufferArray(scip, &coefs);
1121 SCIPfreeBufferArray(scip, &children);
1122
1123 return SCIP_OKAY;
1124}
1125
1126/** creates and captures an expression representing a monomial
1127 *
1128 * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents.
1129 * So this function actually creates an expression for a signomial that has exactly one term.
1130 */
1132 SCIP* scip, /**< SCIP data structure */
1133 SCIP_EXPR** expr, /**< pointer where to store expression */
1134 int nfactors, /**< number of factors in monomial */
1135 SCIP_VAR** vars, /**< variables in the monomial */
1136 SCIP_Real* exponents, /**< exponent in each factor, or NULL if all 1.0 */
1137 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1138 void* ownercreatedata /**< data to pass to ownercreate */
1139 )
1140{
1141 assert(scip != NULL);
1142 assert(expr != NULL);
1143 assert(nfactors >= 0);
1144
1145 /* return 1 as constant expression if there are no factors */
1146 if( nfactors == 0 )
1147 {
1149 }
1150 else if( nfactors == 1 )
1151 {
1152 /* only one factor and exponent is 1 => return factors[0] */
1153 if( exponents == NULL || exponents[0] == 1.0 )
1154 {
1155 /* intentionally not using createExprVar here, since expression created here is not part of
1156 * a constraint (they will be copied when a constraint is created)
1157 */
1159 }
1160 else
1161 {
1163
1164 /* create variable and power expression; intentionally not using createExprVar here,
1165 * since expression created here is not part of a constraint (they will be copied when a constraint is created)
1166 */
1170 }
1171 }
1172 else
1173 {
1174 SCIP_EXPR** children;
1175 int i;
1176
1177 /* allocate memory to store the children */
1179
1180 /* create children */
1181 for( i = 0; i < nfactors; ++i )
1182 {
1183 /* check whether to create a power expression or not, i.e., exponent == 1 */
1184 if( exponents == NULL || exponents[i] == 1.0 )
1185 {
1187 }
1188 else
1189 {
1191
1192 /* create variable and pow expression */
1196 }
1197 }
1198
1199 /* create product expression */
1201
1202 /* release children */
1203 for( i = 0; i < nfactors; ++i )
1204 {
1205 assert(children[i] != NULL);
1206 SCIP_CALL( SCIPreleaseExpr(scip, &children[i]) );
1207 }
1208
1209 /* free memory */
1210 SCIPfreeBufferArray(scip, &children);
1211 }
1212
1213 return SCIP_OKAY;
1214}
1215
1216/** appends child to the children list of expr
1217 *
1218 * @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.
1219 */
1221 SCIP* scip, /**< SCIP data structure */
1222 SCIP_EXPR* expr, /**< expression */
1223 SCIP_EXPR* child /**< expression to be appended */
1224 )
1225{
1226 assert(scip != NULL);
1227 assert(scip->mem != NULL);
1228
1229 SCIP_CALL( SCIPexprAppendChild(scip->set, scip->mem->probmem, expr, child) );
1230
1231 return SCIP_OKAY;
1232}
1233
1234/** overwrites/replaces a child of an expressions
1235 *
1236 * The old child is released and the newchild is captured, unless they are the same (=same pointer).
1237 */
1239 SCIP* scip, /**< SCIP data structure */
1240 SCIP_EXPR* expr, /**< expression which is going to replace a child */
1241 int childidx, /**< index of child being replaced */
1242 SCIP_EXPR* newchild /**< the new child */
1243 )
1244{
1245 assert(scip != NULL);
1246 assert(scip->mem != NULL);
1247
1248 SCIP_CALL( SCIPexprReplaceChild(scip->set, scip->stat, scip->mem->probmem, expr, childidx, newchild) );
1249
1250 return SCIP_OKAY;
1251}
1252
1253/** remove all children of expr
1254 *
1255 * @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.
1256 */
1258 SCIP* scip, /**< SCIP data structure */
1259 SCIP_EXPR* expr /**< expression */
1260 )
1261{
1262 assert(scip != NULL);
1263 assert(scip->mem != NULL);
1264
1265 SCIP_CALL( SCIPexprRemoveChildren(scip->set, scip->stat, scip->mem->probmem, expr) );
1266
1267 return SCIP_OKAY;
1268}
1269
1270/** duplicates the given expression and its children */
1272 SCIP* scip, /**< SCIP data structure */
1273 SCIP_EXPR* expr, /**< original expression */
1274 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
1275 SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */
1276 void* mapexprdata, /**< data of expression mapping function */
1277 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1278 void* ownercreatedata /**< data to pass to ownercreate */
1279 )
1280{
1281 assert(scip != NULL);
1282 assert(scip->mem != NULL);
1283
1284 SCIP_CALL( SCIPexprCopy(scip->set, scip->stat, scip->mem->probmem, scip->set, scip->stat, scip->mem->probmem,
1286
1287 return SCIP_OKAY;
1288}
1289
1290/** duplicates the given expression, but reuses its children */
1292 SCIP* scip, /**< SCIP data structure */
1293 SCIP_EXPR* expr, /**< original expression */
1294 SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */
1295 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1296 void* ownercreatedata /**< data to pass to ownercreate */
1297 )
1298{
1299 assert(scip != NULL);
1300 assert(scip->mem != NULL);
1301
1303
1304 return SCIP_OKAY;
1305}
1306
1307/** copies an expression including children to use in a (possibly different) SCIP instance */
1309 SCIP* sourcescip, /**< source SCIP data structure */
1310 SCIP* targetscip, /**< target SCIP data structure */
1311 SCIP_EXPR* expr, /**< original expression */
1312 SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
1313 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
1314 void* ownercreatedata, /**< data to pass to ownercreate */
1315 SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding
1316 * variables of the target SCIP, or NULL */
1317 SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
1318 * target constraints, or NULL */
1319 SCIP_Bool global, /**< create a global or a local copy? */
1320 SCIP_Bool* valid /**< pointer to store whether all checked or enforced constraints were validly copied */
1321 )
1322{
1323#ifndef _MSC_VER
1325 .varmap = varmap,
1326 .consmap = consmap,
1327 .global = global,
1328 .valid = TRUE
1329 };
1330#else /* MS compiler doesn't have proper C99 support... */
1332 copydata.varmap = varmap;
1333 copydata.consmap = consmap;
1334 copydata.global = global;
1335 copydata.valid = TRUE;
1336#endif
1337
1338 assert(sourcescip != NULL);
1339 assert(sourcescip->mem != NULL);
1341 assert(targetscip->mem != NULL);
1342
1343 SCIP_CALL( SCIPexprCopy(sourcescip->set, sourcescip->stat, sourcescip->mem->probmem,
1344 targetscip->set, targetscip->stat, targetscip->mem->probmem,
1346
1347 *valid = copydata.valid;
1348
1349 return SCIP_OKAY;
1350}
1351
1352/** creates an expression from a string
1353 *
1354 * We specify the grammar that defines the syntax of an expression.
1355 * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power,
1356 * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`.
1357 *
1358 * The actual definition:
1359 * <pre>
1360 * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
1361 * Term -> Factor { ("*" | "/" ) Factor }
1362 * Factor -> Base [ "^" "number" | "^(" "number" ")" ]
1363 * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
1364 * </pre>
1365 * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`.
1366 *
1367 * Note that `Op` and `OpExpression` are undefined.
1368 * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method).
1369 */
1371 SCIP* scip, /**< SCIP data structure */
1372 SCIP_EXPR** expr, /**< pointer to store the expr parsed */
1373 const char* exprstr, /**< string with the expr to parse */
1374 const char** finalpos, /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */
1375 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1376 void* ownercreatedata /**< data to pass to ownercreate */
1377 )
1378{
1379 const char* finalpos_;
1380 SCIP_RETCODE retcode;
1382
1383 assert(scip != NULL);
1384
1386
1387 /* if parseExpr fails, we still want to free hashmap */
1389
1391
1392 if( finalpos != NULL )
1394
1395 return retcode;
1396}
1397
1398/** captures an expression (increments usage count) */
1400 SCIP_EXPR* expr /**< expression to be captured */
1401 )
1402{
1403 SCIPexprCapture(expr);
1404}
1405
1406/** releases an expression (decrements usage count and possibly frees expression) */
1408 SCIP* scip, /**< SCIP data structure */
1409 SCIP_EXPR** expr /**< pointer to expression to be released */
1410 )
1411{
1412 assert(scip != NULL);
1413 assert(scip->mem != NULL);
1414
1415 SCIP_CALL( SCIPexprRelease(scip->set, scip->stat, scip->mem->probmem, expr) );
1416
1417 return SCIP_OKAY;
1418}
1419
1420/** returns whether an expression is a variable expression */
1422 SCIP* scip, /**< SCIP data structure */
1423 SCIP_EXPR* expr /**< expression */
1424 )
1425{
1426 assert(scip != NULL);
1427
1428 return SCIPexprIsVar(scip->set, expr);
1429}
1430
1431/** returns whether an expression is a value expression */
1433 SCIP* scip, /**< SCIP data structure */
1434 SCIP_EXPR* expr /**< expression */
1435 )
1436{
1437 assert(scip != NULL);
1438
1439 return SCIPexprIsValue(scip->set, expr);
1440}
1441
1442/** returns whether an expression is a sum expression */
1444 SCIP* scip, /**< SCIP data structure */
1445 SCIP_EXPR* expr /**< expression */
1446 )
1447{
1448 assert(scip != NULL);
1449
1450 return SCIPexprIsSum(scip->set, expr);
1451}
1452
1453/** returns whether an expression is a product expression */
1455 SCIP* scip, /**< SCIP data structure */
1456 SCIP_EXPR* expr /**< expression */
1457 )
1458{
1459 assert(scip != NULL);
1460
1461 return SCIPexprIsProduct(scip->set, expr);
1462}
1463
1464/** returns whether an expression is a power expression */
1466 SCIP* scip, /**< SCIP data structure */
1467 SCIP_EXPR* expr /**< expression */
1468 )
1469{
1470 assert(scip != NULL);
1471
1472 return SCIPexprIsPower(scip->set, expr);
1473}
1474
1475/** print an expression as info-message */
1477 SCIP* scip, /**< SCIP data structure */
1478 SCIP_EXPR* expr, /**< expression to be printed */
1479 FILE* file /**< file to print to, or NULL for stdout */
1480 )
1481{
1482 assert(scip != NULL);
1483 assert(scip->mem != NULL);
1484
1485 SCIP_CALL( SCIPexprPrint(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1486
1487 return SCIP_OKAY;
1488}
1489
1490/** initializes printing of expressions in dot format to a give FILE* pointer */
1492 SCIP* scip, /**< SCIP data structure */
1493 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
1494 FILE* file, /**< file to print to, or NULL for stdout */
1495 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
1496 )
1497{
1498 assert(scip != NULL);
1499 assert(scip->mem != NULL);
1500
1501 SCIP_CALL( SCIPexprPrintDotInit(scip->set, scip->stat, scip->mem->probmem, printdata, file, whattoprint) );
1502
1503 return SCIP_OKAY;
1504}
1505
1506/** initializes printing of expressions in dot format to a file with given filename */
1508 SCIP* scip, /**< SCIP data structure */
1509 SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
1510 const char* filename, /**< name of file to print to */
1511 SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
1512 )
1513{
1514 assert(scip != NULL);
1515 assert(scip->mem != NULL);
1516
1517 SCIP_CALL( SCIPexprPrintDotInit2(scip->set, scip->stat, scip->mem->probmem, printdata, filename, whattoprint) );
1518
1519 return SCIP_OKAY;
1520}
1521
1522/** main part of printing an expression in dot format */
1524 SCIP* scip, /**< SCIP data structure */
1525 SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */
1526 SCIP_EXPR* expr /**< expression to be printed */
1527 )
1528{
1529 assert(scip != NULL);
1530
1531 SCIP_CALL( SCIPexprPrintDot(scip->set, scip->messagehdlr, printdata, expr) );
1532
1533 return SCIP_OKAY;
1534}
1535
1536/** finishes printing of expressions in dot format */
1538 SCIP* scip, /**< SCIP data structure */
1539 SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */
1540 )
1541{
1542 assert(scip != NULL);
1543 assert(scip->mem != NULL);
1544
1545 SCIP_CALL( SCIPexprPrintDotFinal(scip->set, scip->stat, scip->mem->probmem, printdata) );
1546
1547 return SCIP_OKAY;
1548}
1549
1550/** shows a single expression by use of dot and gv
1551 *
1552 * This function is meant for debugging purposes.
1553 * It's signature is kept as simple as possible to make it
1554 * easily callable from gdb, for example.
1555 *
1556 * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file,
1557 * then calls ghostview (gv) to show the file. SCIP will hold until ghostscript is closed.
1558 */
1560 SCIP* scip, /**< SCIP data structure */
1561 SCIP_EXPR* expr /**< expression to be printed */
1562 )
1563{
1564 /* this function is for developers, so don't bother with C variants that don't have popen() */
1565#if _POSIX_C_SOURCE < 2
1566 SCIPerrorMessage("No POSIX version 2. Try http://distrowatch.com/.");
1567 return SCIP_ERROR;
1568#else
1570 FILE* f;
1571 SCIP_RETCODE retcode = SCIP_OKAY;
1572
1573 assert(scip != NULL);
1574 assert(expr != NULL);
1575
1576 /* call dot to generate postscript output and show it via ghostview */
1577 f = popen("dot -Tps | gv --media=a3 -", "w");
1578 if( f == NULL )
1579 {
1580 SCIPerrorMessage("Calling popen() failed");
1581 return SCIP_FILECREATEERROR;
1582 }
1583
1584 /* print all of the expression into the pipe */
1588
1589 TERMINATE:
1590 /* close the pipe */
1591 (void) pclose(f);
1592
1593 return retcode;
1594#endif
1595}
1596
1597/** prints structure of an expression a la Maple's dismantle */
1599 SCIP* scip, /**< SCIP data structure */
1600 FILE* file, /**< file to print to, or NULL for stdout */
1601 SCIP_EXPR* expr /**< expression to dismantle */
1602 )
1603{
1604 assert(scip != NULL);
1605 assert(scip->mem != NULL);
1606
1607 SCIP_CALL( SCIPexprDismantle(scip->set, scip->stat, scip->mem->probmem, scip->messagehdlr, file, expr) );
1608
1609 return SCIP_OKAY;
1610}
1611
1612/** evaluate an expression in a point
1613 *
1614 * Iterates over expressions to also evaluate children, if necessary.
1615 * Value can be received via SCIPexprGetEvalValue().
1616 * If an evaluation error (division by zero, ...) occurs, this value will
1617 * be set to SCIP_INVALID.
1618 *
1619 * If a nonzero \p soltag is passed, then only (sub)expressions are
1620 * reevaluated that have a different solution tag. If a soltag of 0
1621 * is passed, then subexpressions are always reevaluated.
1622 * The tag is stored together with the value and can be received via
1623 * SCIPexprGetEvalTag().
1624 */
1626 SCIP* scip, /**< SCIP data structure */
1627 SCIP_EXPR* expr, /**< expression to be evaluated */
1628 SCIP_SOL* sol, /**< solution to be evaluated */
1629 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
1630 )
1631{
1632 assert(scip != NULL);
1633 assert(scip->mem != NULL);
1634
1635 SCIP_CALL( SCIPexprEval(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1636
1637 return SCIP_OKAY;
1638}
1639
1640/** returns a previously unused solution tag for expression evaluation */
1642 SCIP* scip /**< SCIP data structure */
1643 )
1644{
1645 assert(scip != NULL);
1646
1647 return ++(scip->stat->exprlastsoltag);
1648}
1649
1650/** evaluates gradient of an expression for a given point
1651 *
1652 * Initiates an expression walk to also evaluate children, if necessary.
1653 * Value can be received via SCIPgetExprPartialDiffNonlinear().
1654 * If an error (division by zero, ...) occurs, this value will
1655 * be set to SCIP_INVALID.
1656 */
1658 SCIP* scip, /**< SCIP data structure */
1659 SCIP_EXPR* expr, /**< expression to be differentiated */
1660 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
1661 SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
1662 )
1663{
1664 assert(scip != NULL);
1665 assert(scip->mem != NULL);
1666
1667 SCIP_CALL( SCIPexprEvalGradient(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag) );
1668
1669 return SCIP_OKAY;
1670}
1671
1672/** evaluates Hessian-vector product of an expression for a given point and direction
1673 *
1674 * Evaluates children, if necessary.
1675 * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear().
1676 * If an error (division by zero, ...) occurs, this value will
1677 * be set to SCIP_INVALID.
1678 */
1680 SCIP* scip, /**< SCIP data structure */
1681 SCIP_EXPR* expr, /**< expression to be differentiated */
1682 SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
1683 SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */
1684 SCIP_SOL* direction /**< direction */
1685 )
1686{
1687 assert(scip != NULL);
1688 assert(scip->mem != NULL);
1689
1690 SCIP_CALL( SCIPexprEvalHessianDir(scip->set, scip->stat, scip->mem->probmem, expr, sol, soltag, direction) );
1691
1692 return SCIP_OKAY;
1693}
1694
1695/** possibly reevaluates and then returns the activity of the expression
1696 *
1697 * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation).
1698 *
1699 * The owner of the expression may overwrite the methods used to evaluate the activity,
1700 * including whether the local or global domain of variables is used.
1701 * By default (no owner, or owner doesn't overwrite activity evaluation),
1702 * the local domain of variables is used.
1703 *
1704 * @note If expression is set to be integral, then activities are tightened to integral values.
1705 * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
1706 */
1708 SCIP* scip, /**< SCIP data structure */
1709 SCIP_EXPR* expr /**< expression */
1710 )
1711{
1712 assert(scip != NULL);
1713 assert(scip->mem != NULL);
1714
1715 SCIP_CALL( SCIPexprEvalActivity(scip->set, scip->stat, scip->mem->probmem, expr) );
1716
1717 return SCIP_OKAY;
1718}
1719
1720/** compare expressions
1721 * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
1722 * @note The given expressions are assumed to be simplified.
1723 */
1725 SCIP* scip, /**< SCIP data structure */
1726 SCIP_EXPR* expr1, /**< first expression */
1727 SCIP_EXPR* expr2 /**< second expression */
1728 )
1729{
1730 assert(scip != NULL);
1731
1732 return SCIPexprCompare(scip->set, expr1, expr2);
1733}
1734
1735/** compute the hash value of an expression */
1737 SCIP* scip, /**< SCIP data structure */
1738 SCIP_EXPR* expr, /**< expression */
1739 unsigned int* hashval /**< pointer to store the hash value */
1740 )
1741{
1743
1744 assert(scip != NULL);
1745 assert(scip->mem != NULL);
1746 assert(expr != NULL);
1747 assert(hashval != NULL);
1748
1749 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1752
1753 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, expr, it, NULL) );
1754
1756
1758
1759 return SCIP_OKAY;
1760}
1761
1762/* simplifies an expression (duplication of long doxygen comment omitted here) */
1764 SCIP* scip, /**< SCIP data structure */
1765 SCIP_EXPR* rootexpr, /**< expression to be simplified */
1766 SCIP_EXPR** simplified, /**< buffer to store simplified expression */
1767 SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */
1768 SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */
1769 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1770 void* ownercreatedata /**< data to pass to ownercreate */
1771 )
1772{
1773 assert(scip != NULL);
1774 assert(scip->mem != NULL);
1775
1776 SCIP_CALL( SCIPexprSimplify(scip->set, scip->stat, scip->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) );
1777
1778 return SCIP_OKAY;
1779}
1780
1781/** replaces common sub-expressions in a given expression graph by using a hash key for each expression
1782 *
1783 * The algorithm consists of two steps:
1784 *
1785 * 1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash
1786 *
1787 * 2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a
1788 * structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the
1789 * hash table, otherwise we add it to the hash table
1790 *
1791 * @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions
1792 * (with the same hash) are structurally the same we use the function SCIPexprCompare().
1793 */
1795 SCIP* scip, /**< SCIP data structure */
1796 SCIP_EXPR** exprs, /**< expressions (possibly replaced by equivalent on output) */
1797 int nexprs, /**< total number of expressions */
1798 SCIP_Bool* replacedroot /**< buffer to store whether any root expression (expression in exprs) was replaced */
1799 )
1800{
1802 SCIP_EXPRITER* hashiterator;
1805 int i;
1806 int nvisitedexprs = 0;
1807
1808 assert(scip != NULL);
1809 assert(scip->mem != NULL);
1810 assert(exprs != NULL);
1811 assert(nexprs >= 0);
1813
1815
1816 if( nexprs == 0 )
1817 return SCIP_OKAY;
1818
1819 SCIP_CALL( SCIPcreateExpriter(scip, &hashiterator) );
1822
1823 /* compute all hashes for each sub-expression */
1824 for( i = 0; i < nexprs; ++i )
1825 {
1826 assert(exprs[i] != NULL);
1827 SCIP_CALL( hashExpr(scip->set, scip->mem->buffer, exprs[i], hashiterator, &nvisitedexprs) );
1828 }
1829
1830 /* replace equivalent sub-expressions */
1831 hashdata.hashiterator = hashiterator;
1832 hashdata.set = scip->set;
1835
1837
1838 for( i = 0; i < nexprs; ++i )
1839 {
1842 SCIP_EXPR* child;
1843
1844 /* check the root for equivalence separately first */
1845 SCIP_CALL( findEqualExpr(scip->set, exprs[i], key2expr, &newroot) );
1846
1847 if( newroot != NULL )
1848 {
1849 assert(newroot != exprs[i]);
1850 assert(SCIPexprCompare(scip->set, exprs[i], newroot) == 0);
1851
1852 SCIPdebugMsg(scip, "replacing common root expression of %dth expr: %p -> %p\n", i, (void*)exprs[i], (void*)newroot);
1853
1854 SCIP_CALL( SCIPreleaseExpr(scip, &exprs[i]) );
1855
1856 exprs[i] = newroot;
1858
1859 *replacedroot = TRUE;
1860
1861 continue;
1862 }
1863
1864 /* replace equivalent sub-expressions in the tree */
1867
1869 {
1871 assert(child != NULL);
1872
1873 /* try to find an equivalent expression */
1874 SCIP_CALL( findEqualExpr(scip->set, child, key2expr, &newchild) );
1875
1876 /* replace child with newchild */
1877 if( newchild != NULL )
1878 {
1879 assert(child != newchild);
1880 assert(SCIPexprCompare(scip->set, child, newchild) == 0);
1881
1882 SCIPdebugMsg(scip, "replacing common child expression %p -> %p\n", (void*)child, (void*)newchild);
1883
1885
1887 }
1888 else
1889 {
1891 }
1892 }
1893 }
1894
1895 /* free memory */
1898 SCIPexpriterFree(&hashiterator);
1899
1900 return SCIP_OKAY;
1901}
1902
1903/** computes the curvature of a given expression and all its subexpressions
1904 *
1905 * @note this function also evaluates all subexpressions w.r.t. current variable bounds
1906 * @note this function relies on information from the curvature callback of expression handlers only,
1907 * consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity
1908 */
1910 SCIP* scip, /**< SCIP data structure */
1911 SCIP_EXPR* expr /**< expression */
1912 )
1913{
1915 SCIP_EXPRCURV curv;
1917 int childcurvsize;
1918 SCIP_Bool success;
1920 int i, c;
1921
1922 assert(scip != NULL);
1923 assert(scip->mem != NULL);
1924 assert(expr != NULL);
1925
1926 childcurvsize = 5;
1928
1929 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
1932
1934 {
1935 curv = SCIP_EXPRCURV_UNKNOWN;
1936
1938 {
1939 /* set curvature in expression */
1940 SCIPexprSetCurvature(expr, curv);
1941 continue;
1942 }
1943
1945 {
1948 }
1949
1950 for( i = 0; i < 3; ++i )
1951 {
1952 /* check if expression can have a curvature trialcurv[i] */
1954 if( !success )
1955 continue;
1956
1957 /* check if conditions on children are satisfied */
1958 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1959 {
1961 {
1962 success = FALSE;
1963 break;
1964 }
1965 }
1966
1967 if( success )
1968 {
1969 curv = trialcurv[i];
1970 break;
1971 }
1972 }
1973
1974 /* set curvature in expression */
1975 SCIPexprSetCurvature(expr, curv);
1976 }
1977
1979
1981
1982 return SCIP_OKAY;
1983}
1984
1985/** computes integrality information of a given expression and all its subexpressions
1986 *
1987 * The integrality information can be accessed via SCIPexprIsIntegral().
1988 */
1990 SCIP* scip, /**< SCIP data structure */
1991 SCIP_EXPR* expr /**< expression */
1992 )
1993{
1995 SCIP_Bool isintegral;
1996
1997 assert(scip != NULL);
1998 assert(scip->mem != NULL);
1999 assert(expr != NULL);
2000
2001 /* shortcut for expr without children */
2002 if( SCIPexprGetNChildren(expr) == 0 )
2003 {
2004 /* compute integrality information */
2005 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2006 SCIPexprSetIntegrality(expr, isintegral);
2007
2008 return SCIP_OKAY;
2009 }
2010
2011 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2014
2016 {
2017 /* compute integrality information */
2018 SCIP_CALL( SCIPexprhdlrIntegralityExpr(SCIPexprGetHdlr(expr), scip->set, expr, &isintegral) );
2019 SCIPexprSetIntegrality(expr, isintegral);
2020 }
2021
2023
2024 return SCIP_OKAY;
2025}
2026
2027/** returns the total number of variable expressions in an expression
2028 *
2029 * The function counts variable expressions in common sub-expressions only once, but
2030 * counts variables appearing in several variable expressions multiple times.
2031 */
2033 SCIP* scip, /**< SCIP data structure */
2034 SCIP_EXPR* expr, /**< expression */
2035 int* nvars /**< buffer to store the total number of variables */
2036 )
2037{
2039
2040 assert(scip != NULL);
2041 assert(scip->mem != NULL);
2042 assert(expr != NULL);
2043 assert(nvars != NULL);
2044
2045 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2047
2048 *nvars = 0;
2049 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2050 if( SCIPexprIsVar(scip->set, expr) )
2051 ++(*nvars);
2052
2054
2055 return SCIP_OKAY;
2056}
2057
2058/** returns all variable expressions contained in a given expression
2059 *
2060 * The array to store all variable expressions needs to be at least of size
2061 * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars().
2062 *
2063 * If every variable is represented by only one variable expression (common subexpression have been removed)
2064 * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars().
2065 * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying,
2066 * then SCIPgetExprNVars() can be bounded by SCIPgetNVars().
2067 *
2068 * @note function captures variable expressions
2069 */
2071 SCIP* scip, /**< SCIP data structure */
2072 SCIP_EXPR* expr, /**< expression */
2073 SCIP_EXPR** varexprs, /**< array to store all variable expressions */
2074 int* nvarexprs /**< buffer to store the total number of variable expressions */
2075 )
2076{
2078
2079 assert(scip != NULL);
2080 assert(scip->mem != NULL);
2081 assert(expr != NULL);
2082 assert(varexprs != NULL);
2083 assert(nvarexprs != NULL);
2084
2085 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, &it) );
2087
2088 *nvarexprs = 0;
2089 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) )
2090 {
2091 assert(expr != NULL);
2092
2093 if( SCIPexprIsVar(scip->set, expr) )
2094 {
2095 varexprs[(*nvarexprs)++] = expr;
2096
2097 /* capture expression */
2098 SCIPcaptureExpr(expr);
2099 }
2100 }
2101
2102 /* @todo sort variable expressions here? */
2103
2105
2106 return SCIP_OKAY;
2107}
2108
2109/** calls the print callback for an expression
2110 *
2111 * @see SCIP_DECL_EXPRPRINT
2112 */
2114{
2115 assert(scip != NULL);
2116
2117 SCIP_CALL( SCIPexprhdlrPrintExpr(SCIPexprGetHdlr(expr), scip->set, scip->messagehdlr, expr, stage, currentchild, parentprecedence, file) );
2118
2119 return SCIP_OKAY;
2120}
2121
2122/** calls the curvature callback for an expression
2123 *
2124 * @see SCIP_DECL_EXPRCURVATURE
2125 *
2126 * Returns unknown curvature if callback not implemented.
2127 */
2136
2137/** calls the monotonicity callback for an expression
2138 *
2139 * @see SCIP_DECL_EXPRMONOTONICITY
2140 *
2141 * Returns unknown monotonicity if callback not implemented.
2142 */
2151
2152/** calls the eval callback for an expression with given values for children
2153 *
2154 * Does not iterates over expressions, but requires values for children to be given.
2155 * Value is not stored in expression, but returned in `val`.
2156 * If an evaluation error (division by zero, ...) occurs, this value will
2157 * be set to `SCIP_INVALID`.
2158 */
2160 SCIP* scip, /**< SCIP data structure */
2161 SCIP_EXPR* expr, /**< expression to be evaluated */
2162 SCIP_Real* childrenvalues, /**< values for children */
2163 SCIP_Real* val /**< buffer to store evaluated value */
2164 )
2165{
2166 assert(scip != NULL);
2167 assert(scip->mem != NULL);
2169 assert(val != NULL);
2170
2171 SCIP_CALL( SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, childrenvalues, NULL) );
2172
2173 return SCIP_OKAY;
2174}
2175
2176/** calls the eval and fwdiff callback of an expression with given values for children
2177 *
2178 * Does not iterates over expressions, but requires values for children and direction to be given.
2179 *
2180 * Value is not stored in expression, but returned in `val`.
2181 * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2182 *
2183 * Direction is not stored in expression, but returned in `dot`.
2184 * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
2185 */
2187 SCIP* scip, /**< SCIP data structure */
2188 SCIP_EXPR* expr, /**< expression to be evaluated */
2189 SCIP_Real* childrenvalues, /**< values for children */
2190 SCIP_Real* direction, /**< direction in which to differentiate */
2191 SCIP_Real* val, /**< buffer to store evaluated value */
2192 SCIP_Real* dot /**< buffer to store derivative value */
2193 )
2194{
2195 assert(scip != NULL);
2196 assert(scip->mem != NULL);
2197
2198 SCIP_CALL( SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), scip->set, scip->mem->buffer, expr, val, dot,
2200
2201 return SCIP_OKAY;
2202}
2203
2204/** calls the interval evaluation callback for an expression
2205 *
2206 * @see SCIP_DECL_EXPRINTEVAL
2207 *
2208 * Returns entire interval if callback not implemented.
2209 */
2218
2219/** calls the estimate callback for an expression
2220 *
2221 * @see SCIP_DECL_EXPRESTIMATE
2222 *
2223 * Returns without success if callback not implemented.
2224 */
2226{
2227 assert(scip != NULL);
2228
2230 overestimate, targetvalue, coefs, constant, islocal, success, branchcand) );
2231
2232 return SCIP_OKAY;
2233}
2234
2235/** calls the initial estimators callback for an expression
2236 *
2237 * @see SCIP_DECL_EXPRINITESTIMATES
2238 *
2239 * Returns no estimators if callback not implemented.
2240 */
2242{
2243 assert(scip != NULL);
2244
2245 SCIP_CALL( SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, overestimate, coefs,
2246 constant, nreturned) );
2247
2248 return SCIP_OKAY;
2249}
2250
2251/** calls the simplify callback for an expression
2252 *
2253 * @see SCIP_DECL_EXPRSIMPLIFY
2254 *
2255 * Returns unmodified expression if simplify callback not implemented.
2256 *
2257 * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that.
2258 */
2260{
2261 assert(scip != NULL);
2262
2263 /* use simplification of expression handlers */
2265 ownercreatedata) );
2266
2267 return SCIP_OKAY;
2268}
2269
2270/** calls the reverse propagation callback for an expression
2271 *
2272 * @see SCIP_DECL_EXPRREVERSEPROP
2273 *
2274 * Returns unmodified childrenbounds if reverseprop callback not implemented.
2275 */
2277{
2278 assert(scip != NULL);
2279
2280 SCIP_CALL( SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), scip->set, expr, bounds, childrenbounds, infeasible) );
2281
2282 return SCIP_OKAY;
2283}
2284
2285/**@} */
2286
2287/**@name Expression Iterator Methods */
2288/**@{ */
2289
2290#ifdef NDEBUG
2291#undef SCIPcreateExpriter
2292#undef SCIPfreeExpriter
2293#endif
2294
2295/** creates an expression iterator */
2297 SCIP* scip, /**< SCIP data structure */
2298 SCIP_EXPRITER** iterator /**< buffer to store expression iterator */
2299 )
2300{
2301 assert(scip != NULL);
2302 assert(scip->mem != NULL);
2303
2304 SCIP_CALL( SCIPexpriterCreate(scip->stat, scip->mem->probmem, iterator) );
2305
2306 return SCIP_OKAY;
2307}
2308
2309/** frees an expression iterator */
2311 SCIP_EXPRITER** iterator /**< pointer to the expression iterator */
2312 )
2313{
2314 SCIPexpriterFree(iterator);
2315}
2316
2317/**@} */
2318
2319
2320/**@name Quadratic expression functions */
2321/**@{ */
2322
2323#ifdef NDEBUG
2324#undef SCIPcheckExprQuadratic
2325#undef SCIPfreeExprQuadratic
2326#undef SCIPcomputeExprQuadraticCurvature
2327#endif
2328
2329/** checks whether an expression is quadratic
2330 *
2331 * An expression is quadratic if it is either a square (of some expression), a product (of two expressions),
2332 * or a sum of terms where at least one is a square or a product.
2333 *
2334 * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic.
2335 */
2337 SCIP* scip, /**< SCIP data structure */
2338 SCIP_EXPR* expr, /**< expression */
2339 SCIP_Bool* isquadratic /**< buffer to store result */
2340 )
2341{
2342 assert(scip != NULL);
2343 assert(scip->mem != NULL);
2344
2345 SCIP_CALL( SCIPexprCheckQuadratic(scip->set, scip->mem->probmem, expr, isquadratic) );
2346
2347 return SCIP_OKAY;
2348}
2349
2350/** frees information on quadratic representation of an expression
2351 *
2352 * Before doing changes to an expression, it can be useful to call this function.
2353 */
2355 SCIP* scip, /**< SCIP data structure */
2356 SCIP_EXPR* expr /**< expression */
2357 )
2358{
2359 assert(scip != NULL);
2360 assert(scip->mem != NULL);
2361
2362 SCIPexprFreeQuadratic(scip->mem->probmem, expr);
2363}
2364
2365/** evaluates quadratic term in a solution
2366 *
2367 * \note This requires that every expression used in the quadratic data is a variable expression.
2368 */
2370 SCIP* scip, /**< SCIP data structure */
2371 SCIP_EXPR* expr, /**< quadratic expression */
2372 SCIP_SOL* sol /**< solution to evaluate, or NULL for LP solution */
2373 )
2374{
2375 SCIP_Real auxvalue;
2376 int nlinexprs;
2377 SCIP_Real* lincoefs;
2378 SCIP_EXPR** linexprs;
2379 int nquadexprs;
2380 int nbilinexprs;
2381 int i;
2382
2383 assert(scip != NULL);
2384 assert(expr != NULL);
2385
2386 SCIPexprGetQuadraticData(expr, &auxvalue, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2387
2388 /* linear terms */
2389 for( i = 0; i < nlinexprs; ++i )
2390 {
2391 assert(SCIPexprIsVar(scip->set, linexprs[i]));
2392 auxvalue += lincoefs[i] * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(linexprs[i]));
2393 }
2394
2395 /* quadratic terms */
2396 for( i = 0; i < nquadexprs; ++i )
2397 {
2399 SCIP_Real lincoef;
2400 SCIP_Real sqrcoef;
2401 SCIP_Real solval;
2402
2403 SCIPexprGetQuadraticQuadTerm(expr, i, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2404
2406
2408 auxvalue += (lincoef + sqrcoef * solval) * solval;
2409 }
2410
2411 /* bilinear terms */
2412 for( i = 0; i < nbilinexprs; ++i )
2413 {
2414 SCIP_EXPR* expr1;
2415 SCIP_EXPR* expr2;
2416 SCIP_Real coef;
2417
2418 SCIPexprGetQuadraticBilinTerm(expr, i, &expr1, &expr2, &coef, NULL, NULL);
2419
2420 assert(SCIPexprIsVar(scip->set, expr1));
2421 assert(SCIPexprIsVar(scip->set, expr2));
2422 auxvalue += coef * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr1)) * SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr2));
2423 }
2424
2425 return auxvalue;
2426}
2427
2428/** prints quadratic expression */
2430 SCIP* scip, /**< SCIP data structure */
2431 SCIP_EXPR* expr /**< quadratic expression */
2432 )
2433{
2434 SCIP_Real constant;
2435 int nlinexprs;
2436 SCIP_Real* lincoefs;
2437 SCIP_EXPR** linexprs;
2438 int nquadexprs;
2439 int nbilinexprs;
2440 int c;
2441
2442 assert(scip != NULL);
2443 assert(expr != NULL);
2444
2445 SCIPexprGetQuadraticData(expr, &constant, &nlinexprs, &linexprs, &lincoefs, &nquadexprs, &nbilinexprs, NULL, NULL);
2446
2447 SCIPinfoMessage(scip, NULL, "Constant: %g\n", constant);
2448
2449 SCIPinfoMessage(scip, NULL, "Linear: ");
2450 for( c = 0; c < nlinexprs; ++c )
2451 {
2452 SCIPinfoMessage(scip, NULL, "%g * ", lincoefs[c]);
2453 SCIP_CALL( SCIPprintExpr(scip, linexprs[c], NULL) );
2454 if( c < nlinexprs - 1 )
2455 SCIPinfoMessage(scip, NULL, " + ");
2456 }
2457 SCIPinfoMessage(scip, NULL, "\n");
2458
2459 SCIPinfoMessage(scip, NULL, "Quadratic: ");
2460 for( c = 0; c < nquadexprs; ++c )
2461 {
2463 SCIP_Real lincoef;
2464 SCIP_Real sqrcoef;
2465
2466 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, &lincoef, &sqrcoef, NULL, NULL, NULL);
2467 SCIPinfoMessage(scip, NULL, "(%g * sqr(", sqrcoef);
2469 SCIPinfoMessage(scip, NULL, ") + %g) * ", lincoef);
2471 if( c < nquadexprs - 1 )
2472 SCIPinfoMessage(scip, NULL, " + ");
2473 }
2474 SCIPinfoMessage(scip, NULL, "\n");
2475
2476 if( nbilinexprs == 0 )
2477 {
2478 SCIPinfoMessage(scip, NULL, "Bilinear: none\n");
2479 return SCIP_OKAY;
2480 }
2481
2482 SCIPinfoMessage(scip, NULL, "Bilinear: ");
2483 for( c = 0; c < nbilinexprs; ++c )
2484 {
2485 SCIP_EXPR* expr1;
2486 SCIP_EXPR* expr2;
2487 SCIP_Real coef;
2488
2489 SCIPexprGetQuadraticBilinTerm(expr, c, &expr1, &expr2, &coef, NULL, NULL);
2490
2491 SCIPinfoMessage(scip, NULL, "%g * ", coef);
2492 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2493 SCIPinfoMessage(scip, NULL, " * ");
2494 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2495 if( c < nbilinexprs - 1 )
2496 SCIPinfoMessage(scip, NULL, " + ");
2497 }
2498 SCIPinfoMessage(scip, NULL, "\n");
2499
2500 SCIPinfoMessage(scip, NULL, "Bilinear of quadratics: \n");
2501 for( c = 0; c < nquadexprs; ++c )
2502 {
2504 int nadjbilin;
2505 int* adjbilin;
2506 int i;
2507
2508 SCIPexprGetQuadraticQuadTerm(expr, c, &quadexprterm, NULL, NULL, &nadjbilin, &adjbilin, NULL);
2509
2510 SCIPinfoMessage(scip, NULL, " For ");
2512 SCIPinfoMessage(scip, NULL, " we see: ");
2513 for( i = 0; i < nadjbilin; ++i )
2514 {
2515 SCIP_EXPR* expr1;
2516 SCIP_EXPR* expr2;
2517 SCIP_Real coef;
2518
2519 SCIPexprGetQuadraticBilinTerm(expr, adjbilin[i], &expr1, &expr2, &coef, NULL, NULL);
2520
2521 SCIPinfoMessage(scip, NULL, "%g * ", coef);
2522 SCIP_CALL( SCIPprintExpr(scip, expr1, NULL) );
2523 SCIPinfoMessage(scip, NULL, " * ");
2524 SCIP_CALL( SCIPprintExpr(scip, expr2, NULL) );
2525 if( i < nadjbilin - 1 )
2526 SCIPinfoMessage(scip, NULL, " + ");
2527 }
2528 SCIPinfoMessage(scip, NULL, "\n");
2529 }
2530
2531 return SCIP_OKAY;
2532}
2533
2534/** checks the curvature of the quadratic expression
2535 *
2536 * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
2537 * If Q is
2538 * - semidefinite positive -> curv is set to convex,
2539 * - semidefinite negative -> curv is set to concave,
2540 * - otherwise -> curv is set to unknown.
2541 *
2542 * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
2543 * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
2544 */
2546 SCIP* scip, /**< SCIP data structure */
2547 SCIP_EXPR* expr, /**< quadratic expression */
2548 SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */
2549 SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
2550 SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */
2551 )
2552{
2553 assert(scip != NULL);
2554 assert(scip->mem != NULL);
2555
2556 SCIP_CALL( SCIPexprComputeQuadraticCurvature(scip->set, scip->mem->probmem, scip->mem->buffer, scip->messagehdlr,
2557 expr, curv, assumevarfixed, storeeigeninfo) );
2558
2559 return SCIP_OKAY;
2560}
2561
2562/**@} */
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_SPACECONTROL
Definition def.h:303
#define SCIP_ALLOC(x)
Definition def.h:399
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_CALL_TERMINATE(retcode, x, TERM)
Definition def.h:409
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPexprPrint(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_EXPR *expr)
Definition expr.c:2243
SCIP_Bool SCIPexprIsPower(SCIP_SET *set, SCIP_EXPR *expr)
Definition expr.c:2231
SCIP_RETCODE SCIPexprEvalActivity(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *rootexpr)
Definition expr.c:2927
SCIP_RETCODE SCIPexprPrintDotInit(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
Definition expr.c:2292
SCIP_RETCODE SCIPexprhdlrIntegralityExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_Bool *isintegral)
Definition expr.c:1060
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:1855
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:2324
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:3166
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:1577
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:3576
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:1612
SCIP_RETCODE SCIPexprEvalGradient(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *rootexpr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition expr.c:2722
SCIP_RETCODE SCIPexprReplaceChild(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition expr.c:1793
SCIP_RETCODE SCIPexprhdlrReversePropExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_INTERVAL bounds, SCIP_INTERVAL *childrenbounds, SCIP_Bool *infeasible)
Definition expr.c:1657
SCIP_Bool SCIPexprIsVar(SCIP_SET *set, SCIP_EXPR *expr)
Definition expr.c:2183
SCIP_RETCODE SCIPexprCheckQuadratic(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition expr.c:3263
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:894
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:2821
int SCIPexprCompare(SCIP_SET *set, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition expr.c:3059
SCIP_RETCODE SCIPexprhdlrMonotonicityExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, int childidx, SCIP_MONOTONE *result)
Definition expr.c:1031
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:1182
SCIP_RETCODE SCIPexprRemoveChildren(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition expr.c:1823
SCIP_RETCODE SCIPexprhdlrHashExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, unsigned int *hashkey, unsigned int *childrenhashes)
Definition expr.c:1090
SCIP_Bool SCIPexprIsValue(SCIP_SET *set, SCIP_EXPR *expr)
Definition expr.c:2195
void SCIPexprCapture(SCIP_EXPR *expr)
Definition expr.c:2041
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:1502
SCIP_RETCODE SCIPexprPrintDotFinal(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRPRINTDATA **printdata)
Definition expr.c:2470
SCIP_RETCODE SCIPexprAppendChild(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition expr.c:1762
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:2010
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:963
SCIP_RETCODE SCIPexprhdlrCurvatureExpr(SCIP_EXPRHDLR *exprhdlr, SCIP_SET *set, SCIP_EXPR *expr, SCIP_EXPRCURV exprcurvature, SCIP_Bool *success, SCIP_EXPRCURV *childcurv)
Definition expr.c:1002
SCIP_RETCODE SCIPexprDismantle(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_MESSAGEHDLR *messagehdlr, FILE *file, SCIP_EXPR *expr)
Definition expr.c:2523
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:1705
SCIP_Bool SCIPexprIsProduct(SCIP_SET *set, SCIP_EXPR *expr)
Definition expr.c:2219
SCIP_RETCODE SCIPexprPrintDot(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
Definition expr.c:2356
SCIP_Bool SCIPexprIsSum(SCIP_SET *set, SCIP_EXPR *expr)
Definition expr.c:2207
SCIP_RETCODE SCIPexprRelease(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR **rootexpr)
Definition expr.c:2051
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:1533
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:1363
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:303
void SCIPexprFreeQuadratic(BMS_BLKMEM *blkmem, SCIP_EXPR *expr)
Definition expr.c:3531
SCIP_RETCODE SCIPexprEval(SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition expr.c:2631
private functions to work with algebraic expressions
void SCIPexpriterFree(SCIP_EXPRITER **iterator)
Definition expriter.c:445
SCIP_RETCODE SCIPexpriterCreate(SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_EXPRITER **iterator)
Definition expriter.c:426
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:1116
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:1079
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:3174
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition misc.c:3106
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
void SCIPmultihashFree(SCIP_MULTIHASH **multihash)
Definition misc.c:1943
SCIP_RETCODE SCIPmultihashInsert(SCIP_MULTIHASH *multihash, void *element)
Definition misc.c:1974
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:1910
void * SCIPmultihashRetrieveNext(SCIP_MULTIHASH *multihash, SCIP_MULTIHASHLIST **multihashlist, void *key)
Definition misc.c:2063
int SCIPgetNExprhdlrs(SCIP *scip)
Definition scip_expr.c:848
SCIP_Bool SCIPexprhdlrHasCurvature(SCIP_EXPRHDLR *exprhdlr)
Definition expr.c:642
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct(SCIP *scip)
Definition scip_expr.c:904
SCIP_EXPRHDLR * SCIPgetExprhdlrVar(SCIP *scip)
Definition scip_expr.c:871
SCIP_EXPRHDLR ** SCIPgetExprhdlrs(SCIP *scip)
Definition scip_expr.c:837
SCIP_EXPRHDLR * SCIPgetExprhdlrValue(SCIP *scip)
Definition scip_expr.c:882
SCIP_EXPRHDLR * SCIPgetExprhdlrSum(SCIP *scip)
Definition scip_expr.c:893
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:814
SCIP_EXPRHDLR * SCIPgetExprhdlrPower(SCIP *scip)
Definition scip_expr.c:915
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition scip_expr.c:859
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:1023
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:1131
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:964
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition scip_expr.c:1220
SCIP_RETCODE SCIPevalExprHessianDir(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag, SCIP_SOL *direction)
Definition scip_expr.c:1679
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition scip_expr.c:1625
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_RETCODE SCIPprintExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:2429
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
Definition expr.c:4145
SCIP_RETCODE SCIPcomputeExprIntegrality(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1989
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1454
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition scip_expr.c:1657
SCIP_RETCODE SCIPprintExprDotInit2(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, const char *filename, SCIP_EXPRPRINT_WHAT whattoprint)
Definition scip_expr.c:1507
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition expriter.c:968
SCIP_Longint SCIPgetExprNewSoltag(SCIP *scip)
Definition scip_expr.c:1641
void SCIPexprSetCurvature(SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
Definition expr.c:4009
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:929
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1443
SCIP_RETCODE SCIPgetExprNVars(SCIP *scip, SCIP_EXPR *expr, int *nvars)
Definition scip_expr.c:2032
SCIP_RETCODE SCIPduplicateExprShallow(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition scip_expr.c:1291
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:4060
SCIP_RETCODE SCIPreplaceExprChild(SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition scip_expr.c:1238
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1432
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:985
void SCIPfreeExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:2354
SCIP_RETCODE SCIPprintExprDot(SCIP *scip, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
Definition scip_expr.c:1523
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition scip_expr.c:1724
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition scip_expr.c:1407
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition expriter.c:682
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition expriter.c:663
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1421
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:1370
SCIP_RETCODE SCIPhashExpr(SCIP *scip, SCIP_EXPR *expr, unsigned int *hashval)
Definition scip_expr.c:1736
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition scip_expr.c:2545
SCIP_RETCODE SCIPcallExprEval(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
Definition scip_expr.c:2159
SCIP_EXPR * SCIPexpriterRestartDFS(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition expriter.c:629
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition scip_expr.c:2296
SCIP_RETCODE SCIPcallExprEvalFwdiff(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *direction, SCIP_Real *val, SCIP_Real *dot)
Definition scip_expr.c:2186
void SCIPexprSetIntegrality(SCIP_EXPR *expr, SCIP_Bool isintegral)
Definition expr.c:4030
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition scip_expr.c:1476
SCIP_EXPRCURV SCIPexprGetCurvature(SCIP_EXPR *expr)
Definition expr.c:3999
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition expr_value.c:294
void SCIPexpriterSetCurrentUserData(SCIP_EXPRITER *iterator, SCIP_EXPRITER_USERDATA userdata)
Definition expriter.c:805
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1465
SCIP_RETCODE SCIPreplaceCommonSubexpressions(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Bool *replacedroot)
Definition scip_expr.c:1794
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition expriter.c:857
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition scip_expr.c:2336
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition expr.c:3811
SCIP_RETCODE SCIPprintExprDotFinal(SCIP *scip, SCIP_EXPRPRINTDATA **printdata)
Definition scip_expr.c:1537
SCIP_RETCODE SCIPprintExprDotInit(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
Definition scip_expr.c:1491
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:1308
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition expr_var.c:416
SCIP_RETCODE SCIPshowExpr(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1559
SCIP_Real SCIPevalExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol)
Definition scip_expr.c:2369
SCIP_RETCODE SCIPcomputeExprCurvature(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1909
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:4105
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:706
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition scip_expr.c:2310
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:695
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:1271
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition scip_expr.c:1399
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition expriter.c:500
SCIP_RETCODE SCIPgetExprVarExprs(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **varexprs, int *nvarexprs)
Definition scip_expr.c:2070
SCIP_EXPRITER_USERDATA SCIPexpriterGetExprUserData(SCIP_EXPRITER *iterator, SCIP_EXPR *expr)
Definition expriter.c:789
SCIP_RETCODE SCIPdismantleExpr(SCIP *scip, FILE *file, SCIP_EXPR *expr)
Definition scip_expr.c:1598
SCIP_RETCODE SCIPremoveExprChildren(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1257
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:1763
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1707
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3824
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition expriter.c:720
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:1361
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:17241
SCIP_Bool SCIPstrToRealValue(const char *str, SCIP_Real *value, char **endptr)
Definition misc.c:10889
SCIP_RETCODE SCIPskipSpace(char **s)
Definition misc.c:10777
return SCIP_OKAY
int c
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
#define BMSreallocBufferMemoryArray(mem, ptr, num)
Definition memory.h:735
#define BMSfreeBufferMemoryArray(mem, ptr)
Definition memory.h:744
#define BMSallocBufferMemoryArray(mem, ptr, num)
Definition memory.h:733
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_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_RETCODE hashExpr(SCIP_SET *set, BMS_BUFMEM *bufmem, SCIP_EXPR *expr, SCIP_EXPRITER *hashiterator, int *nvisitedexprs)
Definition scip_expr.c:746
static SCIP_RETCODE findEqualExpr(SCIP_SET *set, SCIP_EXPR *expr, SCIP_MULTIHASH *key2expr, SCIP_EXPR **newexpr)
Definition scip_expr.c:646
#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
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:5058
SCIP_RETCODE SCIPsetIncludeExprhdlr(SCIP_SET *set, SCIP_EXPRHDLR *exprhdlr)
Definition set.c:5024
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition set.c:5712
internal methods for global SCIP settings
SCIP_EXPRITER * hashiterator
Definition scip_expr.c:695
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:71
SCIP_STAT * stat
Definition struct_scip.h:79
SCIP_SET * set
Definition struct_scip.h:72
datastructures for block memory pools and memory buffers
SCIP main data structure.
datastructures for problem statistics
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition type_expr.h:140
#define SCIP_DECL_EXPRREVERSEPROP(x)
Definition type_expr.h:654
#define SCIP_DECL_EXPRINITESTIMATES(x)
Definition type_expr.h:605
#define SCIP_DECL_EXPRCURVATURE(x)
Definition type_expr.h:337
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition type_expr.h:192
struct SCIP_ExprData SCIP_EXPRDATA
Definition type_expr.h:53
SCIP_EXPRCURV
Definition type_expr.h:58
@ SCIP_EXPRCURV_CONVEX
Definition type_expr.h:60
@ SCIP_EXPRCURV_LINEAR
Definition type_expr.h:62
@ SCIP_EXPRCURV_UNKNOWN
Definition type_expr.h:59
@ SCIP_EXPRCURV_CONCAVE
Definition type_expr.h:61
#define SCIP_DECL_EXPRINTEVAL(x)
Definition type_expr.h:536
#define SCIP_DECL_EXPRMONOTONICITY(x)
Definition type_expr.h:355
#define SCIP_EXPRITER_VISITINGCHILD
Definition type_expr.h:677
unsigned int SCIP_EXPRPRINT_WHAT
Definition type_expr.h:724
#define SCIP_DECL_EXPRSIMPLIFY(x)
Definition type_expr.h:629
#define SCIP_DECL_EXPREVAL(x)
Definition type_expr.h:423
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
#define SCIP_DECL_EXPRPRINT(x)
Definition type_expr.h:286
#define SCIP_DECL_EXPR_MAPEXPR(x)
Definition type_expr.h:179
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition type_expr.h:725
#define SCIP_EXPRITER_LEAVEEXPR
Definition type_expr.h:679
#define SCIP_EXPRPRINT_ALL
Definition type_expr.h:722
#define SCIP_DECL_EXPRESTIMATE(x)
Definition type_expr.h:572
#define SCIP_DECL_HASHKEYEQ(x)
Definition type_misc.h:194
#define SCIP_DECL_HASHGETKEY(x)
Definition type_misc.h:191
#define SCIP_DECL_HASHKEYVAL(x)
Definition type_misc.h:197
@ SCIP_FILECREATEERROR
@ SCIP_READERROR
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
unsigned int uintval
Definition type_expr.h:691