SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
expr_product.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 expr_product.c
26 * @ingroup DEFPLUGINS_EXPR
27 * @brief product expression handler
28 * @author Stefan Vigerske
29 * @author Benjamin Mueller
30 * @author Felipe Serrano
31 * @author Ksenia Bestuzheva
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36#include <string.h>
37
38#include "scip/pub_expr.h"
39#include "scip/expr_product.h"
40#include "scip/expr_sum.h"
41#include "scip/expr_pow.h"
42#include "scip/expr_value.h"
43#include "scip/expr_exp.h"
44#include "scip/expr_abs.h"
45#include "scip/expr_entropy.h"
46#include "scip/cons_nonlinear.h"
47#include "scip/pub_misc.h"
49
50#define EXPRHDLR_NAME "prod"
51#define EXPRHDLR_DESC "product expression"
52#define EXPRHDLR_PRECEDENCE 50000
53#define EXPRHDLR_HASHKEY SCIPcalcFibHash(54949.0)
54
55/** macro to activate/deactivate debugging information of simplify method */
56/*lint -emacro(681,debugSimplify) */
57/*lint -emacro(506,debugSimplify) */
58/*lint -emacro(774,debugSimplify) */
59#ifdef SIMPLIFY_DEBUG
60#define debugSimplify printf
61#else
62#define debugSimplify while( FALSE ) printf
63#endif
64
65
66/*lint -e777*/
67
68/*
69 * Data structures
70 */
71
72/** expression data */
73struct SCIP_ExprData
74{
75 SCIP_Real coefficient; /**< coefficient */
76};
77
78struct SCIP_ExprhdlrData
79{
80 SCIP_CONSHDLR* conshdlr; /**< nonlinear constraint handler (to compute estimates for > 2-dim products) */
81};
82
83/** node for linked list of expressions */
85{
86 SCIP_EXPR* expr; /**< expression in node */
87 struct exprnode* next; /**< next node */
88};
89
90typedef struct exprnode EXPRNODE;
91
92/*
93 * Local methods
94 */
95
96/** evaluation callback for (vertex-polyhedral) functions used as input for facet computation of its envelopes */
97static
99{
100 /* funcdata is a pointer to the double holding the coefficient */
101 SCIP_Real ret = *(SCIP_Real*)funcdata;
102 int i;
103
104 for( i = 0; i < nargs; ++i )
105 ret *= args[i];
106
107 return ret;
108}
109
110static
112 SCIP* scip, /**< SCIP data structure */
113 SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
114 EXPRNODE** simplifiedfactors, /**< factors of simplified product */
115 SCIP_Bool changed, /**< indicates whether some of the simplified factors was changed */
116 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
117 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
118 void* ownercreatedata /**< data to pass to ownercreate */
119 );
120
121/* methods for handling linked list of expressions */
122
123/** inserts newnode at beginning of list */
124static
126 EXPRNODE* newnode, /**< node to insert */
127 EXPRNODE** list /**< list */
128 )
129{
130 assert(list != NULL);
131 assert(newnode != NULL);
132
133 newnode->next = *list;
134 *list = newnode;
135}
136
137/** removes first element of list and returns it */
138static
140 EXPRNODE** list /**< list */
141 )
142{
143 EXPRNODE* first;
144
145 assert(list != NULL);
146
147 if( *list == NULL )
148 return NULL;
149
150 first = *list;
151 *list = (*list)->next;
152 first->next = NULL;
153
154 return first;
155}
156
157/** returns length of list */
158static
160 EXPRNODE* list /**< list */
161 )
162{
163 int length;
164
165 if( list == NULL )
166 return 0;
167
168 length = 1;
169 while( (list=list->next) != NULL )
170 ++length;
171
172 return length;
173}
174
175/** creates expression node and captures expression */
176static
178 SCIP* scip, /**< SCIP data structure */
179 SCIP_EXPR* expr, /**< expression stored at node */
180 EXPRNODE** newnode /**< pointer to store node */
181 )
182{
184
185 (*newnode)->expr = expr;
186 (*newnode)->next = NULL;
188
189 return SCIP_OKAY;
190}
191
192/** creates expression list from expressions */
193static
195 SCIP* scip, /**< SCIP data structure */
196 SCIP_EXPR** exprs, /**< expressions stored in list */
197 int nexprs, /**< number of expressions */
198 EXPRNODE** list /**< pointer to store list */
199 )
200{
201 int i;
202
203 assert(*list == NULL);
204 assert(nexprs > 0);
205
206 debugSimplify("building expr list from %d expressions\n", nexprs);
207 for( i = nexprs - 1; i >= 0; --i )
208 {
210
211 SCIP_CALL( createExprNode(scip, exprs[i], &newnode) );
213 }
214 assert(nexprs > 1 || (*list)->next == NULL);
215
216 return SCIP_OKAY;
217}
218
219/** frees expression node and releases expressions */
220static
222 SCIP* scip, /**< SCIP data structure */
223 EXPRNODE** node /**< node to be freed */
224 )
225{
226 assert(node != NULL && *node != NULL);
227
228 SCIP_CALL( SCIPreleaseExpr(scip, &(*node)->expr) );
230
231 return SCIP_OKAY;
232}
233
234/** frees an expression list */
235static
237 SCIP* scip, /**< SCIP data structure */
238 EXPRNODE** exprlist /**< list */
239 )
240{
242
243 if( *exprlist == NULL )
244 return SCIP_OKAY;
245
246 current = *exprlist;
247 while( current != NULL )
248 {
250
251 tofree = current;
252 current = current->next;
254 }
255 assert(current == NULL);
256 *exprlist = NULL;
257
258 return SCIP_OKAY;
259}
260
261/* helper functions for simplifying expressions */
262
263/** creates a product expression with the elements of exprlist as its children */
264static
266 SCIP* scip, /**< SCIP data structure */
267 EXPRNODE* exprlist, /**< list containing the children of expr */
268 SCIP_Real coef, /**< coef of expr */
269 SCIP_EXPR** expr, /**< pointer to store the product expression */
270 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
271 void* ownercreatedata /**< data to pass to ownercreate */
272 )
273{
274 int i;
275 int nchildren;
276 SCIP_EXPR** children;
277
278 /* asserts SP8 */
279 assert(coef == 1.0);
280 nchildren = listLength(exprlist);
281
282 SCIP_CALL( SCIPallocBufferArray(scip, &children, nchildren) );
283
284 for( i = 0; i < nchildren; ++i )
285 {
286 children[i] = exprlist->expr;
287 exprlist = exprlist->next;
288 }
289
290 assert(exprlist == NULL);
291
292 SCIP_CALL( SCIPcreateExprProduct(scip, expr, nchildren, children, coef, ownercreate, ownercreatedata) );
293
294 SCIPfreeBufferArray(scip, &children);
295
296 return SCIP_OKAY;
297}
298
299/** simplifies a factor of a product expression: base, so that it is a valid children of a simplified product expr
300 *
301 * @note In contrast to other simplify methods, this does *not* return a simplified expression.
302 * Instead, the method is intended to be called only when simplifying a product expression.
303 * Since in general, base is not a simplified child of a product expression, this method returns
304 * a list of expressions L, such that (prod L) = baset *and* each expression in L
305 * is a valid child of a simplified product expression.
306 */
307static
309 SCIP* scip, /**< SCIP data structure */
310 SCIP_EXPR* factor, /**< expression to be simplified */
311 SCIP_Real* simplifiedcoef, /**< coefficient of parent product expression */
312 EXPRNODE** simplifiedfactor, /**< pointer to store the resulting expression node/list of nodes */
313 SCIP_Bool* changed /**< pointer to store if some term actually got simplified */
314 )
315{
318 assert(factor != NULL);
319 assert(changed != NULL);
320
321 /* enforces SP7 */
323 {
324 *changed = TRUE;
326 return SCIP_OKAY;
327 }
328
329 /* enforces SP2 */
331 {
332 *changed = TRUE;
333
334 /* assert SP8 */
336 debugSimplify("[simplifyFactor] seeing a product: include its children\n");
337
339
340 return SCIP_OKAY;
341 }
342
343 /* enforces SP13: a sum with a unique child and no constant -> take the coefficient and use its child as factor */
345 {
346 *changed = TRUE;
347
348 /* assert SS8 and SS7 */
350 debugSimplify("[simplifyFactor] seeing a sum of the form coef * child : take coef and child apart\n");
351
353 {
354 /* if child is a product, then add its children to exprlist */
357 }
358 else
359 {
361 }
363
364 return SCIP_OKAY;
365 }
366
367 /* the given (simplified) expression `factor`, can be a child of a simplified product */
370
372
373 return SCIP_OKAY;
374}
375
376/** merges tomerge into finalchildren
377 *
378 * Both, tomerge and finalchildren contain expressions that could be the children of a simplified product
379 * (except for SP8 and SP10 which are enforced later).
380 * However, the concatenation of both lists will not in general yield a simplified product expression,
381 * because SP4, SP5 and SP14 could be violated. So the purpose of this method is to enforce SP4, SP5 and SP14.
382 * In the process of enforcing SP4, it could happen that SP2 is violated. Since enforcing SP2
383 * could generate further violations, we remove the affected children from finalchildren
384 * and include them in unsimplifiedchildren for further processing.
385 * @note if tomerge has more than one element, then they are the children of a simplified product expression
386 */
387static
389 SCIP* scip, /**< SCIP data structure */
390 EXPRNODE* tomerge, /**< list to merge */
391 EXPRNODE** finalchildren, /**< pointer to store the result of merge between tomerge and *finalchildren */
392 EXPRNODE** unsimplifiedchildren,/**< the list of children that should go to the product expression;
393 * they are unsimplified when seen as children of a simplified product */
394 SCIP_Bool* changed, /**< pointer to store if some term actually got simplified */
395 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
396 void* ownercreatedata /**< data to pass to ownercreate */
397 )
398{
402
403 if( tomerge == NULL )
404 return SCIP_OKAY;
405
406 if( *finalchildren == NULL )
407 {
409 return SCIP_OKAY;
410 }
411
414 previous = NULL;
415
416 while( tomergenode != NULL && current != NULL )
417 {
418 int compareres;
419 EXPRNODE* aux;
422 SCIP_Real expo1;
423 SCIP_Real expo2;
424 SCIP_Bool issignpower1;
425 SCIP_Bool issignpower2;
426
427 /* assert invariants */
430 assert(previous == NULL || previous->next == current);
431
432 /* we are going to multiply the two exprs: current and tomergenode
433 * we first check if they are both exponentials
434 * if so, we multiply them
435 * otherwise, we interpret them as base^exponent
436 * the base of an expr is the expr itself
437 * if type(expr) != pow, otherwise it is the child of pow
438 */
439
440 /* if both are exponentials, create a new exponential with the sum of their children */
441 if( SCIPisExprExp(scip, current->expr) && SCIPisExprExp(scip, tomergenode->expr) )
442 {
443 SCIP_EXPR* sum;
447
448 /* inform that expressions changed */
449 *changed = TRUE;
450
451 /* create sum */
454
455 /* simplify sum */
458
459 /* create exponential */
462
463 /* simplify exponential */
466
467 /* note that simplified exponential might be a product exp(x) * exp(-x + log(y*z)) -> y*z and so it is not a
468 * valid child of a simplified product; therefore we add it to the unsimplifiedchildren's list
469 */
470
471 /* replace tomergenode's expression with simplifiedexp */
472 /* TODO: this code repeats below; add new function to avoid duplication */
475
476 /* move tomergenode to unsimplifiedchildren */
477 aux = tomergenode;
478 tomergenode = tomergenode->next;
480
481 /* remove current */
482 if( current == *finalchildren )
483 {
484 assert(previous == NULL);
486 assert(aux == current);
488 }
489 else
490 {
491 assert(previous != NULL);
492 aux = current;
493 current = current->next;
494 previous->next = current;
495 }
496 SCIP_CALL( freeExprNode(scip, &aux) );
497
498 continue;
499 }
500
501 /* they were not exponentials, so collect bases and exponents */
502 if( SCIPisExprPower(scip, current->expr) )
503 {
507 }
508 else if( SCIPisExprSignpower(scip, current->expr) )
509 {
513 }
514 else
515 {
516 base1 = current->expr;
517 expo1 = 1.0;
519 }
520 if( SCIPisExprPower(scip, tomergenode->expr) )
521 {
525 }
526 else if( SCIPisExprSignpower(scip, tomergenode->expr) )
527 {
531 }
532 else
533 {
534 base2 = tomergenode->expr;
535 expo2 = 1.0;
537 }
538
539 if( SCIPcompareExpr(scip, base1, base2) == 0 )
540 {
541 /* the bases are the same, so we should try to merge the multiplication of the powers */
543
544 if( !issignpower1 && !issignpower2 )
545 {
546 /* and both are normal power, then add to unsimplifiedchildren the resulting expr of simplify(base^(expo1 + expo2)) */
547#if 0 /* TODO we should not loose the implicit base >= 0 constraint, if there is one, but then we should look at bounds on base; simplify currently doesn't */
548 /*
549 * unless expo1 or expo2 are fractional but expo1+expo2 is not fractional, then we better keep the original
550 * the reason for that is that x^fractional implies a constraint x >= 0
551 */
552 if( (EPSISINT(expo1, 0.0) && EPSISINT(expo2, 0.0)) || !EPSISINT(expo1+expo2, 0.0) ) /*lint !e835*/
553#endif
554 {
556 }
557 }
558 else if( issignpower1 ^ issignpower2 )
559 {
560 /* exactly one is signpower: sign(x) |x|^expo1 x^expo2 = sign(x)^(1+expo2) |x|^(expo1+expo2), with x = base */
561 if( EPSISINT(expo2, 0.0) ) /*lint !e835*/
562 {
563 if( (int)expo2 % 2 == 0 )
564 {
565 /* if expo2 is even, then sign(x)^(1+expo2) = sign(x), so we have signpower: sign(x) |x|^(expo1+expo2)
566 * TODO: we can remove this case distinction once the simplification of power expressions tranform
567 * |expr|^even -> expr^even, since the call to SCIPcallExprSimplify(scip, conshdlr, power,
568 * &simplifiedpower) below will take care of this.
569 */
571 }
572 else
573 {
574 /* if expo2 is odd, then sign(x)^(1+expo2) = 1, so we have |x|^(expo1+expo2) */
576
580 }
581 }
582 else if( !EPSISINT(expo1+expo2, 0.0) ) /*lint !e835*/
583 {
584 /* if expo2 is fractional and expo1+expo2 is fractional, then we need x >= 0, so we can use x^(expo1+expo2) */
586 }
587 /* else: expo2 is fractional but expo1+expo2 is integral, then we better do not do anything for now
588 * (leave power at NULL)
589 */
590 }
591 else
592 {
593 /* if both are signpower, then we have |base|^(expo1+expo2)
594 * if expo1+expo2 is even, then we can change this to base^(expo1+expo2)
595 */
596 if( EPSISINT(expo1+expo2, 0.0) && (int)(expo1+expo2)%2 == 0 ) /*lint !e835*/
597 {
599 }
600 else
601 {
603
607 }
608 }
609
610 if( power != NULL )
611 {
612 /* we have created a new power: simplify again and continue */
614
615 /* call simplifyPow or simplifySignpower */
618
619 /* replace tomergenode's expression with simplifiedpower */
622
623 *changed = TRUE;
624
625 /* move tomergenode to unsimplifiedchildren */
626 aux = tomergenode;
627 tomergenode = tomergenode->next;
629
630 /* remove current */
631 if( current == *finalchildren )
632 {
633 assert(previous == NULL);
635 assert(aux == current);
637 }
638 else
639 {
640 assert(previous != NULL);
641 aux = current;
642 current = current->next;
643 previous->next = current;
644 }
645 SCIP_CALL( freeExprNode(scip, &aux) );
646
647 continue;
648 }
649 }
650
651 /* bases are not the same, or we do not want to merge them
652 * then expressions cannot be the same
653 * therefore we need to insert tomergenode in finalchildren
654 * for this, we need to take care of the order
655 */
657 if( compareres == -1 )
658 {
659 /* current < tomergenode => move current */
661 current = current->next;
662 }
663 else
664 {
665 *changed = TRUE;
666 assert(compareres == 1);
667
668 /* insert: if current is the first node, then insert at beginning; otherwise, insert between previous and current */
669 if( current == *finalchildren )
670 {
671 assert(previous == NULL);
672 aux = tomergenode;
673 tomergenode = tomergenode->next;
676 }
677 else
678 {
679 assert(previous != NULL);
680 /* extract */
681 aux = tomergenode;
682 tomergenode = tomergenode->next;
683 /* insert */
684 previous->next = aux;
685 aux->next = current;
686 previous = aux;
687 }
688 }
689 }
690
691 /* if all nodes of tomerge were merged, we are done */
692 if( tomergenode == NULL )
693 return SCIP_OKAY;
694
695 assert(current == NULL);
696
697 /* if all nodes of finalchildren were cancelled by nodes of tomerge (i.e., transfered to unsimplifiedchildren),
698 * then the rest of tomerge is finalchildren
699 */
700 if( *finalchildren == NULL )
701 {
702 assert(previous == NULL);
704 return SCIP_OKAY;
705 }
706
707 /* there are still nodes of tomerge unmerged; these nodes are larger than finalchildren, so append at end */
708 assert(previous != NULL && previous->next == NULL);
709 previous->next = tomergenode;
710
711 return SCIP_OKAY;
712}
713
714/** simplifies the given (simplified) exprs so that they can be factors of a simplified product
715 *
716 * in particular, it will sort and multiply factors whose product leads to new expressions
717 */
718static
720 SCIP* scip, /**< SCIP data structure */
721 SCIP_EXPR** exprs, /**< factors to be simplified */
722 int nexprs, /**< number of factors */
723 SCIP_Real* simplifiedcoef, /**< buffer to store coefficient of PI exprs; needs to be initialized */
724 EXPRNODE** finalchildren, /**< expr node list to store the simplified factors */
725 SCIP_Bool* changed, /**< buffer to store whether some factor changed */
726 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
727 void* ownercreatedata /**< data to pass to ownercreate */
728 )
729{
731
732 /* set up list of current children (when looking at each of them individually, they are simplified, but as
733 * children of a product expression they might be unsimplified)
734 */
737
738 *changed = FALSE;
739
740 /* while there are still children to process */
742 while( unsimplifiedchildren != NULL )
743 {
745 EXPRNODE* first;
746
748 assert(first != NULL);
749
750#ifdef SIMPLIFY_DEBUG
751 debugSimplify("simplifying factor:\n");
752 SCIP_CALL( SCIPprintExpr(scip, first->expr, NULL) );
753 SCIPinfoMessage(scip, NULL, "\n");
754#endif
755
756 /* enforces SP2, SP7 and SP13 */
757 tomerge = NULL;
758 SCIP_CALL( simplifyFactor(scip, first->expr, simplifiedcoef, &tomerge, changed) );
759
760 /* enforces SP4 and SP5 note: merge frees (or uses) the nodes of the tomerge list */
762
763 /* free first */
764 SCIP_CALL( freeExprlist(scip, &first) );
765
766 /* if the simplified coefficient is 0, we can return value 0 */
767 if( *simplifiedcoef == 0.0 )
768 {
769 *changed = TRUE;
773 break;
774 }
775 }
776 return SCIP_OKAY;
777}
778
779/* make sure product has at least two children
780 * - if it is empty; return value
781 * - if it has one child and coef = 1; return child
782 * - if it has one child and coef != 1; return (sum 0 coef expr)
783 */
784static
786 SCIP* scip, /**< SCIP data structure */
787 SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
788 EXPRNODE* finalchildren, /**< factors of simplified product */
789 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
790 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
791 void* ownercreatedata /**< data to pass to ownercreate */
792 )
793{
794 /* empty list --> return value */
795 if( finalchildren == NULL )
796 {
798 return SCIP_OKAY;
799 }
800
801 /* one child and coef equal to 1 --> return child */
802 if( finalchildren->next == NULL && simplifiedcoef == 1.0 )
803 {
806 return SCIP_OKAY;
807 }
808
809 /* one child and coef different from 1 --> return (sum 0 coef child) */
810 if( finalchildren->next == NULL )
811 {
812 SCIP_EXPR* sum;
813
815
816 /* simplifying here is necessary, the product could have sums as children e.g., (prod 2 (sum 1 <x>))
817 * -> (sum 0 2 (sum 1 <x>)) and that needs to be simplified to (sum 0 2 <x>)
818 */
821 return SCIP_OKAY;
822 }
823
824 return SCIP_OKAY;
825}
826
827/** checks if it is entropy expression */
828static
830 SCIP* scip, /**< SCIP data structure */
831 SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
832 EXPRNODE* finalchildren, /**< factors of simplified product */
833 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
834 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
835 void* ownercreatedata /**< data to pass to ownercreate */
836 )
837{
839
840 if( !(finalchildren != NULL && finalchildren->next != NULL && finalchildren->next->next == NULL) )
841 return SCIP_OKAY;
842
843 /* could be log(expr) * expr, e.g., log(sin(x)) * sin(x) (OR11) */
845 {
847 if( 0 == SCIPcompareExpr(scip, SCIPexprGetChildren(finalchildren->expr)[0], finalchildren->next->expr) )
848 entropicchild = finalchildren->next->expr;
849 }
850 /* could be expr * log(expr), e.g., (1 + abs(x)) log(1 + abs(x)) (OR11) */
851 else if( strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(finalchildren->next->expr)), "log") == 0 )
852 {
853 assert(SCIPexprGetNChildren(finalchildren->next->expr) == 1);
854 if( 0 == SCIPcompareExpr(scip, SCIPexprGetChildren(finalchildren->next->expr)[0], finalchildren->expr) )
856 }
857
858 /* success --> replace finalchildren by entropy expression */
859 if( entropicchild != NULL )
860 {
862
863 simplifiedcoef *= -1.0;
864
866
867 /* enforces SP8: if simplifiedcoef != 1.0, transform it into a sum with the (simplified) entropy as child */
868 if( simplifiedcoef != 1.0 )
869 {
872 }
873 else
875 }
876
877 return SCIP_OKAY;
878}
879
880/* expands product of two sums or one sum and another expression
881 * -) two sums: (prod (sum c1 s1 ... sn) (sum c2 t1 ... tm)
882 * Builds a sum representing the expansion, where all of its children are simplified, and then simplify the sum
883 * - constant != 0 --> c1 ti or c2 * sj is simplified (ti, sj are not sums, because they are children of a simplified sum)
884 * - sj * ti may be not be simplified, so put them in a product list and simplify them from there
885 * -) one sum: (prod factor (sum c s1 ... sn))
886 * - c != 0 --> c * factor is simplified (i.e. factor is not sum!)
887 * - factor * si may be not be simplified, so put them in a product list and simplify them from there
888 */
889static
891 SCIP* scip, /**< SCIP data structure */
892 SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
893 EXPRNODE* finalchildren, /**< factors of simplified product */
894 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
895 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
896 void* ownercreatedata /**< data to pass to ownercreate */
897 )
898{
899 /* we need only two children */
900 if( ! (finalchildren != NULL && finalchildren->next != NULL && finalchildren->next->next == NULL) )
901 return SCIP_OKAY;
902
903 /* handle both sums case */
904 if( SCIPisExprSum(scip, finalchildren->expr) && SCIPisExprSum(scip, finalchildren->next->expr) )
905 {
907 SCIP_Real c1 = SCIPgetConstantExprSum(finalchildren->expr);
908 SCIP_Real c2 = SCIPgetConstantExprSum(finalchildren->next->expr);
911 int j;
912 int k;
913
914#ifdef SIMPLIFY_DEBUG
915 debugSimplify("Multiplying sum1 * sum2\n");
916 debugSimplify("sum1: \n");
918 SCIPinfoMessage(scip, NULL, "\n");
919 debugSimplify("sum2: \n");
921 SCIPinfoMessage(scip, NULL, "\n");
922#endif
924
925 /* multiply c1 * sum2 */
926 if( c1 != 0.0 )
927 {
928 int i;
929
930 for( i = 0; i < nchildren2; ++i )
931 {
933
934 term = SCIPexprGetChildren(finalchildren->next->expr)[i];
936 /* we are just re-using a child here, so do not release term! */
937#ifdef SIMPLIFY_DEBUG
938 debugSimplify("Multiplying %f * summand2_i\n", c1);
939 debugSimplify("summand2_i: \n");
941 SCIPinfoMessage(scip, NULL, "\n");
942#endif
943 }
944 }
945 /* multiply c2 * sum1 */
946 if( c2 != 0.0 )
947 {
948 int i;
949
950 for( i = 0; i < nchildren1; ++i )
951 {
953
956 /* we are just re-using a child here, so do not release term! */
957#ifdef SIMPLIFY_DEBUG
958 debugSimplify("Multiplying summand1_i * %f\n", c2);
959 debugSimplify("summand1_i: \n");
961 SCIPinfoMessage(scip, NULL, "\n");
962#endif
963 }
964 }
965 /* multiply sum1 * sum2 without constants */
966 for( j = 0; j < nchildren1; ++j )
967 {
968 SCIP_EXPR* factors[2];
969 SCIP_Real coef1;
970
973 for( k = 0; k < nchildren2; ++k )
974 {
976 SCIP_Real factorscoef;
977 SCIP_Real coef2;
979 SCIP_Bool dummy;
980
982 factors[1] = SCIPexprGetChildren(finalchildren->next->expr)[k];
983
984#ifdef SIMPLIFY_DEBUG
985 debugSimplify("multiplying %g expr1 * %g expr2\n", coef1, coef2);
986 debugSimplify("expr1:\n");
988 SCIPinfoMessage(scip, NULL, "\n");
989 debugSimplify("expr2\n");
991 SCIPinfoMessage(scip, NULL, "\n");
992#endif
993
996 assert(factorscoef != 0.0);
997
998#ifdef SIMPLIFY_DEBUG
999 {
1000 EXPRNODE* node;
1001 int i;
1002
1003 debugSimplify("Building product from simplified factors\n");
1004 node = finalfactors;
1005 i = 0;
1006 while( node != NULL )
1007 {
1008 debugSimplify("factor %d (nuses %d):\n", i, SCIPexprGetNUses(node->expr));
1009 SCIP_CALL( SCIPprintExpr(scip, node->expr, NULL) );
1010 SCIPinfoMessage(scip, NULL, "\n");
1011 node = node->next;
1012 i++;
1013 }
1014 }
1015#endif
1016
1019 assert(term != NULL);
1020
1021#ifdef SIMPLIFY_DEBUG
1022 debugSimplify("%g expr1 * %g expr2 = %g * product\n", coef1, coef2, coef1 * coef2);
1023 debugSimplify("product: (nused %d)\n", SCIPexprGetNUses(term));
1025 SCIPinfoMessage(scip, NULL, "\n");
1026#endif
1027
1029
1031 }
1032 }
1033
1034 /* simplify the sum */
1037
1038 return SCIP_OKAY;
1039 }
1040
1041 /* handle one sum case */
1042 if( SCIPisExprSum(scip, finalchildren->expr) || SCIPisExprSum(scip, finalchildren->next->expr) )
1043 {
1045 SCIP_EXPR* factors[2];
1046 SCIP_EXPR* sum = NULL;
1047 SCIP_Real constant;
1048 int nchildren;
1049 int j;
1050
1051 if( SCIPisExprSum(scip, finalchildren->expr) )
1052 {
1053 assert(!SCIPisExprSum(scip, finalchildren->next->expr));
1054 sum = finalchildren->expr;
1055 factors[0] = finalchildren->next->expr;
1056 }
1057 else
1058 {
1060 sum = finalchildren->next->expr;
1061 factors[0] = finalchildren->expr;
1062 }
1063 constant = simplifiedcoef * SCIPgetConstantExprSum(sum);
1064 nchildren = SCIPexprGetNChildren(sum);
1065
1067 /* we are just re-using a child here, so do not release factor! */
1068
1069 for( j = 0; j < nchildren; ++j )
1070 {
1071 SCIP_Real coef;
1072 SCIP_Real termcoef;
1073 SCIP_Bool dummy;
1075 SCIP_EXPR* term = NULL;
1076
1077 coef = SCIPgetCoefsExprSum(sum)[j];
1078 factors[1] = SCIPexprGetChildren(sum)[j];
1079
1080 termcoef = coef;
1082 assert(termcoef != 0.0);
1083
1086 assert(term != NULL);
1087
1090 }
1091
1092 /* simplify the sum */
1095 }
1096
1097 return SCIP_OKAY;
1098}
1099
1100/** builds a simplified product from simplifiedfactors
1101 *
1102 * @note this function also releases simplifiedfactors
1103 */
1104static
1106 SCIP* scip, /**< SCIP data structure */
1107 SCIP_Real simplifiedcoef, /**< simplified product should be simplifiedcoef * PI simplifiedfactors */
1108 EXPRNODE** simplifiedfactors, /**< factors of simplified product */
1109 SCIP_Bool changed, /**< indicates whether some of the simplified factors was changed */
1110 SCIP_EXPR** simplifiedexpr, /**< buffer to store the simplified expression */
1111 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1112 void* ownercreatedata /**< data to pass to ownercreate */
1113 )
1114{
1116
1117 /* build product expression from finalchildren and post-simplify */
1118 debugSimplify("[simplifyProduct] finalchildren has length %d\n", listLength(finalchildren));
1119
1121
1123 if( *simplifiedexpr != NULL )
1124 goto CLEANUP;
1125
1127 if( *simplifiedexpr != NULL )
1128 goto CLEANUP;
1129
1131 if( *simplifiedexpr != NULL )
1132 goto CLEANUP;
1133
1134 /* enforces SP8: if simplifiedcoef != 1.0, transform it into a sum with the (simplified) product as child */
1135 if( simplifiedcoef != 1.0 )
1136 {
1137 SCIP_EXPR* aux;
1138 SCIP_EXPR* sum;
1139
1140 /* create sum */
1143 SCIP_CALL( SCIPreleaseExpr(scip, &aux) );
1144
1145 /* simplify sum */
1147 SCIP_CALL( SCIPreleaseExpr(scip, &sum) );
1148
1149 goto CLEANUP;
1150 }
1151
1152 /* build product expression from list */
1153 if( changed )
1154 {
1156 goto CLEANUP;
1157 }
1158
1159CLEANUP:
1160
1162 return SCIP_OKAY;
1163}
1164
1165/** computes an estimator for a product as a vertex polyhedral function
1166 *
1167 * Since the product is multilinear, its convex and concave envelopes are piecewise linear.
1168 */
1169static
1171 SCIP* scip, /**< SCIP data structure */
1172 SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
1173 int nfactors, /**< number of factors */
1174 SCIP_INTERVAL* bounds, /**< bound for each factor */
1175 SCIP_Real constantfactor, /**< another constant factor */
1176 SCIP_Real* refpoint, /**< reference point where to estimate, or NULL if called from initestimates */
1177 SCIP_Bool overestimate, /**< should estimator overestimate expr (TRUE) or underestimate (FALSE) */
1178 SCIP_Real targetvalue, /**< no need to compute facet if value in xstar would be worse than target value */
1179 SCIP_Real* coefs, /**< array to store cut coefficients */
1180 SCIP_Real* constant, /**< pointer to store cut constant */
1181 SCIP_Bool* success /**< pointer to store whether estimation was successful */
1182 )
1183{
1184 SCIP_Real* box;
1185 SCIP_Real* xstar;
1186 int nfixed;
1187 int i;
1188
1189 assert(conshdlr != NULL);
1190 assert(nfactors > 0);
1191 assert(bounds != NULL);
1192 assert(constantfactor != 0.0);
1193 assert(coefs != NULL);
1194 assert(constant != NULL);
1195 assert(success != NULL);
1196
1197 *success = FALSE;
1198
1199 /* assemble box, check for unbounded variables, assemble xstar */
1202 for( i = 0, nfixed = 0; i < nfactors; ++i )
1203 {
1205
1206 if( SCIPisInfinity(scip, -bounds[i].inf) || SCIPisInfinity(scip, bounds[i].sup) )
1207 {
1208 SCIPdebugMsg(scip, "a factor is unbounded, no cut is possible\n");
1209 goto CLEANUP;
1210 }
1211
1212 box[2*i] = bounds[i].inf;
1213 box[2*i+1] = bounds[i].sup;
1214
1215 xstar[i] = refpoint != NULL ? refpoint[i] : 0.5 * (box[2*i] + box[2*i+1]);
1216
1217 if( SCIPisRelEQ(scip, box[2*i], box[2*i+1]) )
1218 ++nfixed;
1219 }
1220
1222 {
1224 overestimate, prodfunction, &constantfactor, xstar, box, nfactors, targetvalue, success, coefs, constant) );
1225 }
1226
1227CLEANUP:
1230
1231 return SCIP_OKAY;
1232}
1233
1234/*
1235 * Callback methods of expression handler
1236 */
1237
1238/** simplifies a product expression
1239 *
1240 * Summary: we first build a list of expressions (called finalchildren) which will be the children of the simplified product
1241 * and then we process this list in order to enforce SP8 and SP10.
1242 *
1243 * Description: In order to build finalchildren, we first build a list of unsimplified children (called unsimplifiedchildren)
1244 * with the children of the product. Each node of the list is manipulated (see simplifyFactor) in order to satisfy
1245 * SP2 and SP7 as follows:
1246 * - SP7: if the node's expression is a value, multiply the value to the products's coef
1247 * - SP2: if the node's expression is a product, then build a list with the child's children
1248 *
1249 * Then, we merge the built list (or the simplified node) into finalchildren. While merging, nodes from finalchildren
1250 * can go back to unsimplifiedchildren for further processing (see mergeProductExprlist() for more details).
1251 * After building finalchildren, we create the simplified product out of it, taking care that SP8 and SP10 are satisfied
1252 */
1253static
1255{ /*lint --e{715}*/
1257 SCIP_Real simplifiedcoef;
1258 SCIP_Bool changed;
1259
1260 assert(expr != NULL);
1262
1264
1265#ifdef SIMPLIFY_DEBUG
1266 debugSimplify("Simplifying expr:\n");
1268 SCIPinfoMessage(scip, NULL, "\n");
1269 debugSimplify("First multiplying children\n");
1270#endif
1271
1272 /* simplify and multiply factors */
1275
1276#ifdef SIMPLIFY_DEBUG
1277 {
1278 EXPRNODE* node;
1279 int i;
1280
1281 debugSimplify("Building product from simplified factors\n");
1282 node = finalchildren;
1283 i = 0;
1284 while( node != NULL )
1285 {
1286 debugSimplify("factor %d:\n", i);
1287 SCIP_CALL( SCIPprintExpr(scip, node->expr, NULL) );
1288 SCIPinfoMessage(scip, NULL, "\n");
1289 node = node->next;
1290 i++;
1291 }
1292 }
1293#endif
1294
1295 /* get simplified product from simplified factors in finalchildren */
1297 ownercreatedata) );
1299
1300 if( *simplifiedexpr == NULL )
1301 {
1303
1304 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
1306 }
1308
1309 return SCIP_OKAY;
1310}
1311
1312/** compare two product expressions
1313 *
1314 * The order of two product expressions, u and v, is a lexicographical order on the factors.
1315 *
1316 * Starting from the *last*, we find the first child where they differ, say, the i-th.
1317 * Then u < v <=> u_i < v_i.
1318 * If there is no such children and they have different number of children, then u < v <=> nchildren(u) < nchildren(v).
1319 * If all children are the same and they have the same number of children, then u < v <=> coeff(u) < coeff(v).
1320 * Otherwise, they are the same.
1321 *
1322 * Note: we are assuming expression are simplified, so within u, we have u_1 < u_2, etc.
1323 *
1324 * Example: y * z < x * y * z
1325 */
1326static
1328{ /*lint --e{715}*/
1329 int compareresult;
1330 int i;
1331 int j;
1332 int nchildren1;
1333 int nchildren2;
1336
1341
1342 for( i = nchildren1 - 1, j = nchildren2 - 1; i >= 0 && j >= 0; --i, --j )
1343 {
1345 if( compareresult != 0 )
1346 return compareresult;
1347 /* expressions are equal, continue */
1348 }
1349
1350 /* all children of one expression are children of the other expression, use number of children as a tie-breaker */
1351 if( i < j )
1352 {
1353 assert(i == -1);
1354 /* expr1 has less elements, hence expr1 < expr2 */
1355 return -1;
1356 }
1357 if( i > j )
1358 {
1359 assert(j == -1);
1360 /* expr1 has more elements, hence expr1 > expr2 */
1361 return 1;
1362 }
1363
1364 /* everything is equal, use coefficient as tie-breaker */
1365 assert(i == -1 && j == -1);
1367 return -1;
1369 return 1;
1370
1371 /* they are equal */
1372 return 0;
1373}
1374
1375/** expression handler copy callback */
1376static
1378{ /*lint --e{715}*/
1380
1381 return SCIP_OKAY;
1382}
1383
1384/** expression handler free callback */
1385static
1387{ /*lint --e{715}*/
1388 assert(scip != NULL);
1389 assert(exprhdlr != NULL);
1392
1395
1396 return SCIP_OKAY;
1397}
1398
1399/** expression data copy callback */
1400static
1415
1416/** expression data free callback */
1417static
1419{ /*lint --e{715}*/
1420 SCIP_EXPRDATA* exprdata;
1421
1422 assert(expr != NULL);
1423
1424 exprdata = SCIPexprGetData(expr);
1425 assert(exprdata != NULL);
1426
1427 SCIPfreeBlockMemory(scip, &exprdata);
1428
1430
1431 return SCIP_OKAY;
1432}
1433
1434/** expression print callback */
1435static
1437{ /*lint --e{715}*/
1438 SCIP_EXPRDATA* exprdata;
1439
1440 assert(expr != NULL);
1441
1442 exprdata = SCIPexprGetData(expr);
1443 assert(exprdata != NULL);
1444
1445 switch( stage )
1446 {
1448 {
1449 /* print opening parenthesis, if necessary */
1451 {
1452 SCIPinfoMessage(scip, file, "(");
1453 }
1454
1455 /* print coefficient, if not one */
1456 if( exprdata->coefficient != 1.0 )
1457 {
1458 if( exprdata->coefficient < 0.0 && EXPRHDLR_PRECEDENCE > parentprecedence )
1459 {
1460 SCIPinfoMessage(scip, file, "(%g)", exprdata->coefficient);
1461 }
1462 else
1463 {
1464 SCIPinfoMessage(scip, file, "%g", exprdata->coefficient);
1465 }
1466 }
1467 break;
1468 }
1469
1471 {
1472 /* print multiplication sign, if not first factor */
1473 if( exprdata->coefficient != 1.0 || currentchild > 0 )
1474 {
1475 SCIPinfoMessage(scip, file, "*");
1476 }
1477 break;
1478 }
1479
1481 {
1482 break;
1483 }
1484
1486 {
1487 /* print closing parenthesis, if necessary */
1489 {
1490 SCIPinfoMessage(scip, file, ")");
1491 }
1492 break;
1493 }
1494
1495 default:
1496 /* all stages should have been covered above */
1497 SCIPABORT();
1498 }
1499
1500 return SCIP_OKAY;
1501}
1502
1503/** product hash callback */
1504static
1506{ /*lint --e{715}*/
1507 SCIP_EXPRDATA* exprdata;
1508 int c;
1509
1510 assert(scip != NULL);
1511 assert(expr != NULL);
1512 assert(hashkey != NULL);
1514
1515 exprdata = SCIPexprGetData(expr);
1516 assert(exprdata != NULL);
1517
1519 *hashkey ^= SCIPcalcFibHash(exprdata->coefficient);
1520
1521 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1523
1524 return SCIP_OKAY;
1525}
1526
1527/** expression point evaluation callback */
1528static
1530{ /*lint --e{715}*/
1531 SCIP_EXPRDATA* exprdata;
1532 SCIP_Real childval;
1533 int c;
1534
1535 assert(expr != NULL);
1536
1537 exprdata = SCIPexprGetData(expr);
1538 assert(exprdata != NULL);
1539
1540 *val = exprdata->coefficient;
1541 for( c = 0; c < SCIPexprGetNChildren(expr) && (*val != 0.0); ++c )
1542 {
1545
1546 *val *= childval;
1547 }
1548
1549 return SCIP_OKAY;
1550}
1551
1552/** derivative evaluation callback computing <gradient, children.dot>
1553 *
1554 * If expr is \f$\prod_i x_i\f$, then computes \f$\sum_j \prod_{i\neq j} x_i x^{\text{dot}}_j\f$.
1555 */
1556static
1558{ /*lint --e{715}*/
1559 int c;
1560
1561 assert(expr != NULL);
1562 assert(dot != NULL);
1563
1565
1566 /* TODO add special handling for nchildren == 2 */
1567
1568 /**! [SnippetExprFwdiffProduct] */
1569 *dot = 0.0;
1570 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1571 {
1572 SCIP_EXPR* child;
1573
1574 child = SCIPexprGetChildren(expr)[c];
1575
1578
1579 if( SCIPexprGetDot(child) == 0.0 )
1580 continue;
1581
1582 if( SCIPexprGetEvalValue(child) != 0.0 )
1584 else
1585 {
1586 SCIP_Real partial;
1587 int i;
1588
1589 partial = SCIPexprGetData(expr)->coefficient;
1590 for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
1591 {
1592 if( i == c )
1593 continue;
1594
1596 }
1597 *dot += partial * SCIPexprGetDot(child);
1598 }
1599 }
1600 /**! [SnippetExprFwdiffProduct] */
1601
1602 return SCIP_OKAY;
1603}
1604
1605/** expression backward forward derivative evaluation callback
1606 *
1607 * Computes \f$\frac{\partial}{\partial \text{childidx}} ( \langle \text{gradient}, \text{children.dot}\rangle )\f$.
1608 *
1609 * If expr is \f$\prod_i x_i\f$, and childidx is \f$k\f$ then computes
1610 * \f$\partial_k \sum_j \prod_{i \neq j} x_i x^{\text{dot}}_j
1611 * = \sum_{j \neq k} \prod_{i \neq j, k} x_i x^{\text{dot}}_j\f$
1612 */
1613static
1615{ /*lint --e{715}*/
1617 int c;
1618
1619 assert(expr != NULL);
1620 assert(bardot != NULL);
1623
1628
1629 /* TODO add special handling for nchildren == 2 */
1630
1631 /**! [SnippetExprBwfwdiffProduct] */
1632 *bardot = 0.0;
1633 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1634 {
1635 SCIP_EXPR* child;
1636
1637 if( c == childidx )
1638 continue;
1639
1640 child = SCIPexprGetChildren(expr)[c];
1641
1644
1645 if( SCIPexprGetDot(child) == 0.0 )
1646 continue;
1647
1648 if( SCIPexprGetEvalValue(child) != 0.0 && SCIPexprGetEvalValue(partialchild) != 0.0 )
1650 else
1651 {
1652 SCIP_Real partial;
1653 int i;
1654
1655 partial = SCIPexprGetData(expr)->coefficient;
1656 for( i = 0; i < SCIPexprGetNChildren(expr) && (partial != 0.0); ++i )
1657 {
1658 if( i == c || i == childidx )
1659 continue;
1660
1662 }
1663 *bardot += partial * SCIPexprGetDot(child);
1664 }
1665 }
1666 /**! [SnippetExprBwfwdiffProduct] */
1667
1668 return SCIP_OKAY;
1669}
1670
1671/** expression derivative evaluation callback */
1672static
1674{ /*lint --e{715}*/
1675 SCIP_EXPR* child;
1676
1677 assert(expr != NULL);
1680
1682 assert(child != NULL);
1683 assert(!SCIPisExprValue(scip, child));
1685
1686 /* TODO add special handling for nchildren == 2 */
1687
1688 /**! [SnippetExprBwdiffProduct] */
1689 if( !SCIPisZero(scip, SCIPexprGetEvalValue(child)) )
1690 {
1692 }
1693 else
1694 {
1695 int i;
1696
1697 *val = SCIPexprGetData(expr)->coefficient;
1698 for( i = 0; i < SCIPexprGetNChildren(expr) && (*val != 0.0); ++i )
1699 {
1700 if( i == childidx )
1701 continue;
1702
1704 }
1705 }
1706 /**! [SnippetExprBwdiffProduct] */
1707
1708 return SCIP_OKAY;
1709}
1710
1711/** expression interval evaluation callback */
1712static
1714{ /*lint --e{715}*/
1715 SCIP_EXPRDATA* exprdata;
1716 int c;
1717
1718 assert(expr != NULL);
1719
1720 exprdata = SCIPexprGetData(expr);
1721 assert(exprdata != NULL);
1722
1723 /**! [SnippetExprIntevalProduct] */
1724 SCIPintervalSet(interval, exprdata->coefficient);
1725
1726 SCIPdebugMsg(scip, "inteval %p with %d children: %.20g", (void*)expr, SCIPexprGetNChildren(expr), exprdata->coefficient);
1727
1728 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1729 {
1731
1734 {
1736 break;
1737 }
1738
1739 /* multiply childinterval with the so far computed interval */
1741
1742 SCIPdebugMsgPrint(scip, " *[%.20g,%.20g]", childinterval.inf, childinterval.sup);
1743 }
1744 SCIPdebugMsgPrint(scip, " = [%.20g,%.20g]\n", interval->inf, interval->sup);
1745 /**! [SnippetExprIntevalProduct] */
1746
1747 return SCIP_OKAY;
1748}
1749
1750/** estimates a multilinear function of the form \f$ f(x) := a \prod_{i = 1}^n x_i \f$
1751 *
1752 * \f$ x_i \f$ are the auxiliary variables of the children.
1753 * If !overestimate, then we look for an affine underestimator of \f$ f(x) \f$ which has a value above targetvalue at \f$ x^* \f$,
1754 * i.e., \f$ g(x) := \alpha^T x + \beta \le f(x)\f$ for all \f$ x \f$ in the domain, such that \f$ \alpha x^* + \beta > \text{targetvalue}\f$.
1755 *
1756 * Since \f$ f(x) \f$ is componentwise linear, its convex envelope is piecewise linear and its value can be computed by
1757 * finding the largest affine underestimator.
1758 * This is done either explicitly (if n=2) or by solving an LP, see SCIPcomputeFacetVertexPolyhedralNonlinear().
1759 */
1760static
1762{ /*lint --e{715}*/
1763 SCIP_EXPRDATA* exprdata;
1764 int nchildren;
1765
1766 assert(scip != NULL);
1767 assert(expr != NULL);
1769 assert(refpoint != NULL);
1770 assert(coefs != NULL);
1771 assert(constant != NULL);
1772 assert(islocal != NULL);
1773 assert(branchcand != NULL);
1774 assert(*branchcand == TRUE);
1775 assert(success != NULL);
1776
1777 exprdata = SCIPexprGetData(expr);
1778 assert(exprdata != NULL);
1779
1780 *success = FALSE;
1781 *islocal = TRUE;
1782
1783 nchildren = SCIPexprGetNChildren(expr);
1784
1785 /* debug output: prints expression we are trying to estimate, bounds of variables and point */
1786#ifdef SCIP_DEBUG
1787 {
1788 int c;
1789
1790 SCIPdebugMsg(scip, "%sestimating product with %d variables\n", overestimate ? "over": "under", SCIPexprGetNChildren(expr));
1791 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
1792 {
1793 SCIPdebugMsg(scip, "child %d = %g in [%g, %g]\n", c, refpoint[c], localbounds[c].inf, localbounds[c].sup);
1794
1796 {
1797 SCIPdebugMsg(scip, "unbounded factor related to\n");
1799 }
1800 }
1801 }
1802#endif
1803
1804 /* bilinear term */
1805 if( nchildren == 2 )
1806 {
1807 SCIP_Real refpointx;
1808 SCIP_Real refpointy;
1811
1812 /* collect first variable */
1813 refpointx = refpoint[0];
1814 bndx = localbounds[0];
1816
1817 /* collect second variable */
1818 refpointy = refpoint[1];
1819 bndy = localbounds[1];
1821
1822 /* adjust the reference points */
1823 refpointx = MIN(MAX(refpointx, bndx.inf), bndx.sup);
1824 refpointy = MIN(MAX(refpointy, bndy.inf), bndy.sup);
1825
1826 coefs[0] = 0.0;
1827 coefs[1] = 0.0;
1828 *constant = 0.0;
1829 *success = TRUE;
1830
1831 SCIPaddBilinMcCormick(scip, exprdata->coefficient, bndx.inf, bndx.sup, refpointx,
1832 bndy.inf, bndy.sup, refpointy, overestimate, &coefs[0], &coefs[1], constant,
1833 success);
1834 }
1835 else
1836 {
1838
1841
1842 if( exprhdlrdata->conshdlr != NULL )
1843 {
1844 SCIP_CALL( estimateVertexPolyhedralProduct(scip, exprhdlrdata->conshdlr, nchildren, localbounds, exprdata->coefficient, refpoint, overestimate,
1845 targetvalue, coefs, constant, success) );
1846 }
1847 else
1848 {
1849 SCIPdebugMsg(scip, "no cons_nonlinear included in SCIP, cannot estimate vertex-polyhedral product function\n");
1850 }
1851 }
1852
1853 return SCIP_OKAY;
1854}
1855
1856/** initial estimators callback */
1857static
1859{
1860 SCIP_EXPRDATA* exprdata;
1861 SCIP_Bool success = TRUE;
1862 int nchildren;
1863
1864 assert(scip != NULL);
1865 assert(expr != NULL);
1867 assert(nreturned != NULL);
1868
1869 nchildren = SCIPexprGetNChildren(expr);
1870
1871 exprdata = SCIPexprGetData(expr);
1872 assert(exprdata != NULL);
1873
1874 if( nchildren == 2 )
1875 {
1876 SCIP_INTERVAL bndx = bounds[0];
1877 SCIP_INTERVAL bndy = bounds[1];
1878
1879 constant[0] = 0.0;
1880 coefs[0][0] = 0.0;
1881 coefs[0][1] = 0.0;
1882
1883 /* build estimator */
1884 SCIPaddBilinMcCormick(scip, exprdata->coefficient, bndx.inf, bndx.sup, (bndx.inf + bndx.sup) / 2.0,
1885 bndy.inf, bndy.sup, (bndy.inf + bndy.sup ) / 2.0, overestimate, &coefs[0][0], &coefs[0][1],
1886 constant, &success);
1887 }
1888 else
1889 {
1891
1894
1895 if( exprhdlrdata->conshdlr != NULL )
1896 {
1897 SCIP_CALL( estimateVertexPolyhedralProduct(scip, exprhdlrdata->conshdlr, nchildren, bounds, exprdata->coefficient, NULL, overestimate,
1898 overestimate ? SCIPinfinity(scip) : -SCIPinfinity(scip), coefs[0], constant, &success) );
1899 }
1900 else
1901 {
1902 SCIPdebugMsg(scip, "no cons_nonlinear included in SCIP, cannot estimate vertex-polyhedral product function\n");
1903 }
1904 }
1905
1906 if( success )
1907 *nreturned = 1;
1908
1909 return SCIP_OKAY;
1910}
1911
1912/** expression reverse propagation callback */
1913static
1915{ /*lint --e{715}*/
1916 SCIP_EXPRDATA* exprdata;
1920 int i;
1921 int j;
1922
1923 assert(scip != NULL);
1924 assert(expr != NULL);
1926 assert(infeasible != NULL);
1928
1929 *infeasible = FALSE;
1930
1931 /* too expensive (runtime here is quadratic in number of children)
1932 * TODO implement something faster for larger numbers of factors, e.g., split product into smaller products
1933 */
1934 if( SCIPexprGetNChildren(expr) > 10 )
1935 return SCIP_OKAY;
1936
1937 /* not possible to learn bounds on children if expression bounds are unbounded in both directions */
1939 return SCIP_OKAY;
1940
1941 exprdata = SCIPexprGetData(expr);
1942 assert(exprdata != NULL);
1943
1944 /**! [SnippetExprReversepropProduct] */
1945 SCIPintervalSet(&zero, 0.0);
1946
1947 /* f = const * prod_k c_k => c_i solves c_i * (const * prod_{j:j!=i} c_j) = f */
1948 for( i = 0; i < SCIPexprGetNChildren(expr) && !(*infeasible); ++i )
1949 {
1950 SCIPintervalSet(&otherfactor, exprdata->coefficient);
1951
1952 /* compute prod_{j:j!=i} c_j */
1953 for( j = 0; j < SCIPexprGetNChildren(expr); ++j )
1954 {
1955 if( i == j )
1956 continue;
1957
1958 /* TODO we should compute these only one time instead of repeating this for almost every i */
1961 {
1962 *infeasible = TRUE;
1963 return SCIP_OKAY;
1964 }
1965
1967 }
1968
1971 {
1972 *infeasible = TRUE;
1973 return SCIP_OKAY;
1974 }
1975
1976 /* solve x*otherfactor = f for x in c_i */
1978
1979 SCIPdebugMsg(scip, "child %d: solved [%g,%g]*x = [%g,%g] with x in [%g,%g] -> x = [%g,%g]\n", i, otherfactor.inf, otherfactor.sup,
1980 bounds.inf, bounds.sup,
1981 childrenbounds[i].inf, childrenbounds[i].sup,
1982 childbounds.inf, childbounds.sup);
1983
1984 /* store computed bounds of the expression */
1987 {
1988 *infeasible = TRUE;
1989 return SCIP_OKAY;
1990 }
1991 }
1992 /**! [SnippetExprReversepropProduct] */
1993
1994 return SCIP_OKAY;
1995}
1996
1997/** expression curvature detection callback */
1998static
2000{ /*lint --e{715}*/
2001 assert(scip != NULL);
2002 assert(expr != NULL);
2003 assert(success != NULL);
2005
2006 if( SCIPexprGetNChildren(expr) == 1 )
2007 {
2009 *success = TRUE;
2010 }
2011 else
2012 {
2013 *success = FALSE;
2014 }
2015
2016 return SCIP_OKAY;
2017}
2018
2019/** expression monotonicity detection callback */
2020static
2022{ /*lint --e{715}*/
2023 SCIP_Real coef;
2024 int i;
2025 int nneg;
2026
2027 assert(scip != NULL);
2028 assert(expr != NULL);
2029 assert(result != NULL);
2031 assert(childidx >= 0);
2033
2035
2036 /* count the number of negative children (except for childidx); if some children changes sign
2037 * -> monotonicity unknown
2038 */
2039 nneg = 0;
2040 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
2041 {
2043
2044 if( i == childidx )
2045 continue;
2046
2050
2051 if( SCIPintervalGetSup(interval) <= 0.0 )
2052 nneg++;
2053 else if( SCIPintervalGetInf(interval) < 0.0 )
2054 {
2056 return SCIP_OKAY;
2057 }
2058 }
2059
2060 /* note that the monotonicity depends on the sign of the coefficient */
2061 if( nneg % 2 == 0 )
2062 *result = (coef >= 0.0) ? SCIP_MONOTONE_INC : SCIP_MONOTONE_DEC;
2063 else
2064 *result = (coef >= 0.0) ? SCIP_MONOTONE_DEC : SCIP_MONOTONE_INC;
2065
2066 return SCIP_OKAY;
2067}
2068
2069/** expression integrality detection callback */
2070static
2072{ /*lint --e{715}*/
2073 SCIP_EXPRDATA* exprdata;
2074 int i;
2075
2076 assert(scip != NULL);
2077 assert(expr != NULL);
2078 assert(isintegral != NULL);
2079
2080 exprdata = SCIPexprGetData(expr);
2081 assert(exprdata != NULL);
2082
2083 *isintegral = EPSISINT(exprdata->coefficient, 0.0); /*lint !e835*/
2084
2085 for( i = 0; i < SCIPexprGetNChildren(expr) && *isintegral; ++i )
2086 {
2088 assert(child != NULL);
2089
2090 *isintegral = SCIPexprIsIntegral(child);
2091 }
2092
2093 return SCIP_OKAY;
2094}
2095
2096/** creates the handler for product expressions and includes it into SCIP */
2128
2129/** creates a product expression */
2131 SCIP* scip, /**< SCIP data structure */
2132 SCIP_EXPR** expr, /**< pointer where to store expression */
2133 int nchildren, /**< number of children */
2134 SCIP_EXPR** children, /**< children */
2135 SCIP_Real coefficient, /**< constant coefficient of product */
2136 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
2137 void* ownercreatedata /**< data to pass to ownercreate */
2138 )
2139{
2140 SCIP_EXPRDATA* exprdata;
2141
2142 /**! [SnippetCreateExprProduct] */
2143 SCIP_CALL( SCIPallocBlockMemory(scip, &exprdata) );
2144 exprdata->coefficient = coefficient;
2145
2147 /**! [SnippetCreateExprProduct] */
2148
2149 return SCIP_OKAY;
2150}
2151
2152/* from pub_expr.h */
2153
2154/** gets the constant coefficient of a product expression */
2156 SCIP_EXPR* expr /**< product expression */
2157 )
2158{
2159 SCIP_EXPRDATA* exprdata;
2160
2161 assert(expr != NULL);
2162
2163 exprdata = SCIPexprGetData(expr);
2164 assert(exprdata != NULL);
2165
2166 return exprdata->coefficient;
2167}
constraint handler for nonlinear constraints specified by algebraic expressions
#define EPSISINT(x, eps)
Definition def.h:223
#define SCIP_INVALID
Definition def.h:206
#define SCIP_INTERVAL_INFINITY
Definition def.h:208
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define SCIP_CALL(x)
Definition def.h:388
absolute expression handler
handler for -x*log(x) expressions
exponential expression handler
power and signed power expression handlers
static int listLength(EXPRNODE *list)
#define debugSimplify
static SCIP_RETCODE enforceSP11(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
#define EXPRHDLR_HASHKEY
static SCIP_RETCODE enforceSP10(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
#define EXPRHDLR_NAME
static SCIP_RETCODE simplifyFactor(SCIP *scip, SCIP_EXPR *factor, SCIP_Real *simplifiedcoef, EXPRNODE **simplifiedfactor, SCIP_Bool *changed)
static SCIP_RETCODE createExprProductFromExprlist(SCIP *scip, EXPRNODE *exprlist, SCIP_Real coef, SCIP_EXPR **expr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE createExprNode(SCIP *scip, SCIP_EXPR *expr, EXPRNODE **newnode)
static EXPRNODE * listPopFirst(EXPRNODE **list)
static void insertFirstList(EXPRNODE *newnode, EXPRNODE **list)
static SCIP_RETCODE simplifyMultiplyChildren(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real *simplifiedcoef, EXPRNODE **finalchildren, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE enforceSP12(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE *finalchildren, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE freeExprlist(SCIP *scip, EXPRNODE **exprlist)
static SCIP_RETCODE freeExprNode(SCIP *scip, EXPRNODE **node)
#define EXPRHDLR_DESC
#define EXPRHDLR_PRECEDENCE
static SCIP_RETCODE createExprlistFromExprs(SCIP *scip, SCIP_EXPR **exprs, int nexprs, EXPRNODE **list)
static SCIP_RETCODE buildSimplifiedProduct(SCIP *scip, SCIP_Real simplifiedcoef, EXPRNODE **simplifiedfactors, SCIP_Bool changed, SCIP_EXPR **simplifiedexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE mergeProductExprlist(SCIP *scip, EXPRNODE *tomerge, EXPRNODE **finalchildren, EXPRNODE **unsimplifiedchildren, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
static SCIP_RETCODE estimateVertexPolyhedralProduct(SCIP *scip, SCIP_CONSHDLR *conshdlr, int nfactors, SCIP_INTERVAL *bounds, SCIP_Real constantfactor, SCIP_Real *refpoint, SCIP_Bool overestimate, SCIP_Real targetvalue, SCIP_Real *coefs, SCIP_Real *constant, SCIP_Bool *success)
product expression handler
sum expression handler
constant value expression handler
SCIP_RETCODE SCIPcomputeFacetVertexPolyhedralNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool overestimate, SCIP_DECL_VERTEXPOLYFUN((*function)), void *fundata, SCIP_Real *xstar, SCIP_Real *box, int nallvars, SCIP_Real targetvalue, SCIP_Bool *success, SCIP_Real *facetcoefs, SCIP_Real *facetconstant)
#define SCIP_DECL_VERTEXPOLYFUN(f)
#define SCIP_MAXVERTEXPOLYDIM
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 SCIPcreateExprAbs(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_abs.c:528
SCIP_RETCODE SCIPappendExprSumExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child, SCIP_Real childcoef)
Definition expr_sum.c:1116
SCIP_RETCODE SCIPcreateExprSignpower(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_pow.c:3198
SCIP_Bool SCIPisExprExp(SCIP *scip, SCIP_EXPR *expr)
Definition expr_exp.c:528
SCIP_RETCODE SCIPcreateExprExp(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_exp.c:510
SCIP_Bool SCIPisExprSignpower(SCIP *scip, SCIP_EXPR *expr)
Definition expr_pow.c:3223
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 SCIPcreateExprEntropy(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
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
SCIP_RETCODE SCIPincludeExprhdlrProduct(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsgPrint
#define SCIPdebugMsg
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition misc.c:10258
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition expr.c:532
void SCIPexprhdlrSetCompare(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:460
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:438
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:416
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct(SCIP *scip)
Definition scip_expr.c:904
SCIP_EXPRHDLRDATA * SCIPexprhdlrGetData(SCIP_EXPRHDLR *exprhdlr)
Definition expr.c:562
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:486
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:427
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:508
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:449
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
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:497
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)),)
Definition expr.c:471
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)),)
Definition expr.c:368
void SCIPexprhdlrSetPrint(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:394
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)),)
Definition expr.c:381
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)),)
Definition expr.c:519
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
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition expr.c:3849
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition expr_pow.c:3351
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1454
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1443
SCIP_Bool SCIPexprIsIntegral(SCIP_EXPR *expr)
Definition expr.c:4020
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition expr_sum.c:1166
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1432
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
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_Real SCIPexprGetDot(SCIP_EXPR *expr)
Definition expr.c:3915
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition expr.c:3834
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition exprcurv.c:87
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition scip_expr.c:1476
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition expr_value.c:294
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1465
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition expr.c:3875
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition expr.c:3811
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition expr_sum.c:1181
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition expr.c:3957
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition scip_expr.c:1399
int SCIPexprGetNUses(SCIP_EXPR *expr)
Definition expr.c:3791
SCIP_RETCODE SCIPdismantleExpr(SCIP *scip, FILE *file, SCIP_EXPR *expr)
Definition scip_expr.c:1598
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1707
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3824
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
#define SCIPallocClearBlockMemory(scip, ptr)
Definition scip_mem.h:91
#define SCIPduplicateBlockMemory(scip, ptr, source)
Definition scip_mem.h:103
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
bilinear nonlinear handler
public functions to work with algebraic expressions
public data structures and miscellaneous methods
SCIP_Real sup
SCIP_Real inf
struct exprnode * next
SCIP_EXPR * expr
#define MAX(x, y)
Definition tclique_def.h:92
#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_EXPRBWFWDIFF(x)
Definition type_expr.h:517
#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
#define SCIP_DECL_EXPRFREEDATA(x)
Definition type_expr.h:265
#define SCIP_DECL_EXPRBWDIFF(x)
Definition type_expr.h:446
#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
@ SCIP_MONOTONE_UNKNOWN
Definition type_expr.h:68
@ SCIP_MONOTONE_INC
Definition type_expr.h:69
@ SCIP_MONOTONE_DEC
Definition type_expr.h:70
#define SCIP_DECL_EXPRCOMPARE(x)
Definition type_expr.h:407
#define SCIP_DECL_EXPRSIMPLIFY(x)
Definition type_expr.h:629
#define SCIP_DECL_EXPREVAL(x)
Definition type_expr.h:423
#define SCIP_DECL_EXPRFWDIFF(x)
Definition type_expr.h:477
#define SCIP_DECL_EXPRHASH(x)
Definition type_expr.h:388
#define SCIP_DECL_EXPRCOPYHDLR(x)
Definition type_expr.h:207
#define SCIP_DECL_EXPRPRINT(x)
Definition type_expr.h:286
#define SCIP_DECL_EXPRFREEHDLR(x)
Definition type_expr.h:221
#define SCIP_DECL_EXPRINTEGRALITY(x)
Definition type_expr.h:372
#define SCIP_EXPRITER_VISITEDCHILD
Definition type_expr.h:678
#define SCIP_DECL_EXPRCOPYDATA(x)
Definition type_expr.h:246
#define SCIP_EXPRITER_LEAVEEXPR
Definition type_expr.h:679
#define SCIP_DECL_EXPRESTIMATE(x)
Definition type_expr.h:572
#define SCIP_EXPRITER_ENTEREXPR
Definition type_expr.h:676
enum SCIP_Retcode SCIP_RETCODE