SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
expr_sum.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_sum.c
26 * @ingroup DEFPLUGINS_EXPR
27 * @brief sum expression handler
28 * @author Stefan Vigerske
29 * @author Benjamin Mueller
30 * @author Felipe Serrano
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#include <string.h>
36#include <stddef.h>
37
38#include "scip/expr_sum.h"
39#include "scip/expr_value.h"
40#include "scip/expr_product.h"
41#include "scip/expr_exp.h"
42
43#define EXPRHDLR_NAME "sum"
44#define EXPRHDLR_DESC "summation with coefficients and a constant"
45#define EXPRHDLR_PRECEDENCE 40000
46#define EXPRHDLR_HASHKEY SCIPcalcFibHash(47161.0)
47
48/** macro to activate/deactivate debugging information of simplify method */
49/*lint -emacro(774,debugSimplify) */
50#ifdef SIMPLIFY_DEBUG
51#define debugSimplify printf
52#else
53#define debugSimplify while( FALSE ) printf
54#endif
55
56/*
57 * Data structures
58 */
59
60/** expression data */
61struct SCIP_ExprData
62{
63 SCIP_Real constant; /**< constant coefficient */
64 SCIP_Real* coefficients; /**< coefficients of children */
65 int coefssize; /**< size of the coefficients array */
66};
67
68/*
69 * Local methods
70 */
71
72/** creates expression data */
73static
75 SCIP* scip, /**< SCIP data structure */
76 SCIP_EXPRDATA** exprdata, /**< pointer where to store expression data */
77 int ncoefficients, /**< number of coefficients (i.e., number of children) */
78 SCIP_Real* coefficients, /**< array with coefficients for all children (or NULL if all 1.0) */
79 SCIP_Real constant /**< constant term of sum */
80 )
81{
82 assert(exprdata != NULL);
84
86
87 if( coefficients != NULL )
88 {
89 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*exprdata)->coefficients, coefficients, ncoefficients) );
90 }
91 else
92 {
93 int i;
94
95 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*exprdata)->coefficients, ncoefficients) );
96 for( i = 0; i < ncoefficients; ++i )
97 (*exprdata)->coefficients[i] = 1.0;
98 }
99
100 (*exprdata)->coefssize = ncoefficients;
101 (*exprdata)->constant = constant;
102
103 return SCIP_OKAY;
104}
105
106/** simplifies the `idx`-th child of the sum expression `duplicate` in order for it to be able to be a child of a simplified sum
107 *
108 * for example, this means that the `idx`-th child cannot be itself a sum
109 * if it is, we have to flatten it, i.e., take all its children and make them children of `duplicate`
110 */
111static
113 SCIP* scip, /**< SCIP data structure */
114 SCIP_EXPR* duplicate, /**< expression to be simplified */
115 int idx, /**< idx of children to be simplified */
116 SCIP_Bool* changed, /**< pointer to store if some term actually got simplified */
117 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
118 void* ownercreatedata /**< data to pass to ownercreate */
119 )
120{
121 SCIP_EXPR** children;
122 SCIP_EXPR* expr;
123 SCIP_Real* coefs;
124 SCIP_Real constant ;
125 SCIP_Real coef;
126
128 assert(idx >= 0);
130 assert(changed != NULL);
131
132 children = SCIPexprGetChildren(duplicate);
135
136 coef = coefs[idx];
137 expr = children[idx];
138 assert(expr != NULL);
139
140 /* enforces SS3 */
141 if( SCIPisExprValue(scip, expr) )
142 {
143 *changed = TRUE;
144 constant += coef * SCIPgetValueExprValue(expr);
146
147 /* TODO: remove child? */
148 coefs[idx] = 0.0;
149
150 return SCIP_OKAY;
151 }
152
153 /* enforces SS2 */
154 if( SCIPisExprSum(scip, expr) )
155 {
156 *changed = TRUE;
157
158 /* pass constant to parent */
159 constant += coef * SCIPgetConstantExprSum(expr);
161
162 /* append all children of expr on parent except the first one */
163 if( SCIPexprGetNChildren(expr) > 1 )
164 {
165 int i;
166
167 for( i = 1; i < SCIPexprGetNChildren(expr); ++i )
168 {
171 coef * SCIPgetCoefsExprSum(expr)[i]) );
172 }
173 }
174
175 /* replace expr with first child; need to get data again since it might be re-allocated */
177
179
180 coefs[idx] = coef * SCIPgetCoefsExprSum(expr)[0];
182
183 return SCIP_OKAY;
184 }
185
186 /* enforce SS9 */
187 if( REALABS(coef) != 1.0 && SCIPisExprProduct(scip, expr) )
188 {
190 int i;
191
192 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
193 {
194 SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
195 assert(child != NULL);
196
197 if( SCIPisExprExp(scip, child) )
198 {
199 expchild = child;
200 break;
201 }
202 }
203
204 /* coef != +- 1, term is product and one factor is an exponential -> enforce SS9 */
205 if( expchild != NULL )
206 {
207 SCIP_EXPR* sum;
213 SCIP_Real expconstant;
214
215 /* inform that expression will change */
216 *changed = TRUE;
217
218 /* compute expchild's coefficient as +- 1.0 * exp(log(abs(coef))) */
219 if( coef > 0.0 )
220 {
221 expconstant = log(coef);
222 coefs[idx] = 1.0;
223 }
224 else
225 {
226 expconstant = log(-coef);
227 coefs[idx] = -1.0;
228 }
229
230 /* add constant to exponential's child */
233
234 /* simplify sum */
237
238 /* create exponential with new child */
241
242 /* simplify exponential */
245
246 /* create product with new child */
248
249 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
250 {
251 if( SCIPexprGetChildren(expr)[i] == expchild )
252 {
254 }
255 else
256 {
258 }
259 }
261
262 /* simplify product */
265
266 /* replace current child with simplified product */
269
270 /* since the simplified product can be a sum ( exp(-1)*exp(log(x+y)+1) -> x+y ),
271 * we call the function we are in again
272 * this is no endless recursion, since the coef is now +- 1
273 */
275
276 return SCIP_OKAY;
277 }
278 }
279
280 /* enforce SS10 */
281 if( REALABS(coef) != 1.0 && SCIPisExprExp(scip, expr) )
282 {
283 /* coef != +- 1, term is exponential -> enforce SS10 by moving |coef| into argument of exponential */
284
285 SCIP_EXPR* sum;
289 SCIP_Real expconstant;
290
291 /* inform that expression will change */
292 *changed = TRUE;
293
294 /* compute expchild's coefficient as +- 1.0 * exp(log(abs(coef))) */
295 if( coef > 0.0 )
296 {
297 expconstant = log(coef);
298 coefs[idx] = 1.0;
299 }
300 else
301 {
302 expconstant = log(-coef);
303 coefs[idx] = -1.0;
304 }
305
306 /* add constant to exponential's child */
308 ownercreatedata) ); /* expconstant+expchild */
309
310 /* simplify sum */
313
314 /* create exponential with new child */
317
318 /* simplify exponential */
321
322 /* replace current child with simplified exponential */
325
326 return SCIP_OKAY;
327 }
328
329 /* other types of (simplified) expressions can be a child of a simplified sum */
330 assert(!SCIPisExprSum(scip, expr));
331 assert(!SCIPisExprValue(scip, expr));
332
333 return SCIP_OKAY;
334}
335
336/** helper struct for expressions sort */
337typedef struct
338{
339 SCIP* scip; /**< SCIP data structure */
340 SCIP_EXPR** exprs; /**< expressions */
342
343static
345{
346 SORTEXPRDATA* data = (SORTEXPRDATA*)dataptr;
347
348 return SCIPcompareExpr(data->scip, data->exprs[ind1], data->exprs[ind2]);
349}
350
351/*
352 * Callback methods of expression handler
353 */
354
355/** simplifies a sum expression
356 *
357 * goes through each child and simplifies it; then sorts the simplified children; then sum the children that are equal;
358 * finally creates a sum expression with all the children that do not have a 0 coefficient and post-process so that SS6
359 * and SS7 are satisfied
360 */
361static
363{ /*lint --e{715}*/
364 SCIP_EXPR** children;
367 SCIP_Real* newcoefs = NULL;
368 int nnewchildren;
369 SCIP_Real newconstant;
370 SCIP_Real* coefs;
371 int i;
372 int nchildren;
373 SCIP_Bool changed;
375 int* order = NULL;
376
377 assert(expr != NULL);
380
381 changed = FALSE;
382
383 /* TODO: maybe have a flag to know if it is simplified ? */
384 /* TODO: can we do this with a shallow duplicate + copy of children pointer? currently simplifyTerm may modify children,
385 * so one would need to be careful
386 */
389
390 nchildren = SCIPexprGetNChildren(duplicate);
391 for( i = 0; i < nchildren; i++ )
392 {
393 /* enforces SS8 TODO: remove child? */
394 /* we have to ask for the coefs everytime, since it might get realloced in simpifyTerm */
395 if( SCIPgetCoefsExprSum(duplicate)[i] == 0.0 )
396 {
397 changed = TRUE;
398 continue;
399 }
400
401 /* enforces SS2, SS3, SS9, and SS10 */
403 }
404
405 /* simplifyTerm can add new children to duplicate and realloc them; so get them again */
406 nchildren = SCIPexprGetNChildren(duplicate);
407 children = SCIPexprGetChildren(duplicate);
409
410 /* treat zero term case */
411 if( nchildren == 0 )
412 {
414 goto CLEANUP;
415 }
416
417 /* treat one term case */
418 if( nchildren == 1 )
419 {
420 if( coefs[0] == 0.0 )
421 {
423 goto CLEANUP;
424 }
425
426 if( coefs[0] == 1.0 && SCIPgetConstantExprSum(duplicate) == 0.0 )
427 *simplifiedexpr = children[0]; /* SS7 */
428 else
429 *simplifiedexpr = changed ? duplicate : expr;
430
432
433 goto CLEANUP;
434 }
435
436 /* enforces SS5: sort children */
437 SCIP_CALL( SCIPallocBufferArray(scip, &order, nchildren) );
438 for( i = 0; i < nchildren; i++ )
439 order[i] = i;
440 sortdata.scip = scip;
441 sortdata.exprs = children;
442 SCIPsortInd(order, sortExprComp, (void*)&sortdata, nchildren);
443
444 /* create sorted variant of children and coefs */
447 for( i = 0; i < nchildren; ++i )
448 {
449 newchildren[i] = children[order[i]];
450 newcoefs[i] = coefs[order[i]];
451 if( order[i] != i )
452 changed = TRUE;
453 }
454
455 /* post-process */
456
457 /* enforces SS4 */
458 nnewchildren = 0;
459 for( i = 0; i < nchildren; i++ )
460 {
461 /* eliminate zero-coefficients */
462 if( newcoefs[i] == 0.0 )
463 {
464 changed = TRUE;
465 continue;
466 }
467
468 /* sum equal expressions */
469 if( i < nchildren-1 && SCIPcompareExpr(scip, newchildren[i], newchildren[i+1]) == 0 )
470 {
471 changed = TRUE;
472 /* if we substract two almost equal not-so-small numbers, then set new coefficient to 0.0
473 * instead of some tiny value that is likely the result of some random round-off error
474 * E.g., on instance ex1221, we have x1^2 + b3 = 1.25.
475 * Probing finds an aggregation x1 = 1.11803 - 0.618034 b3.
476 * Simplify would then produce 1.25 + 1e-16 x1 = 1.25.
477 */
478 if( SCIPisEQ(scip, newcoefs[i], -newcoefs[i+1]) && REALABS(newcoefs[i]) >= 1.0 )
479 newcoefs[i+1] = 0.0;
480 else
481 newcoefs[i+1] += newcoefs[i];
482 continue;
483 }
484
485 /* move i-th child to new position */
488 nnewchildren++;
489 }
490
491 /* build sum expression from finalchildren and post-simplify */
493
494 debugSimplify("what to do? finalchildren has length %d\n", nnewchildren); /*lint !e506 !e681*/
495
496 /* enforces SS6: if they are no children, return value */
497 if( nnewchildren == 0 )
498 {
499 debugSimplify("[sum] got empty list, return value %g\n", newconstant); /*lint !e506 !e681*/
501
502 goto CLEANUP;
503 }
504
505 /* enforces SS7: if list consists of one expr with coef 1.0 and constant is 0, return that expr */
506 if( nnewchildren == 1 && newcoefs[0] == 1.0 && newconstant == 0.0 )
507 {
510
511 goto CLEANUP;
512 }
513
514 /* build sum expression from children */
515 if( changed )
516 {
519
520 goto CLEANUP;
521 }
522
523 *simplifiedexpr = expr;
524
525 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
527
528 /* free memory */
529 CLEANUP:
534
535 return SCIP_OKAY;
536}
537
538/** compares two sum expressions
539 *
540 * The order of two sum expressions is a lexicographical order on the terms.
541 *
542 * Starting from the *last*, we find the first child where they differ, say, the i-th.
543 * Then u < v <=> u_i < v_i.
544 * If there are no such children and they have different number of children, then u < v <=> nchildren(u) < nchildren(v).
545 * If there are no such children and they have the same number of children, then u < v <=> const(u) < const(v).
546 * Otherwise, they are the same.
547 *
548 * Note: we are assuming expression are simplified, so within u, we have u_1 < u_2, etc
549 *
550 * Example: y + z < x + y + z, 2*x + 3*y < 3*x + 3*y
551 */
552static
554{ /*lint --e{715}*/
555 SCIP_Real const1;
556 SCIP_Real* coefs1;
558 int nchildren1;
559 SCIP_Real const2;
560 SCIP_Real* coefs2;
562 int nchildren2;
563 int compareresult;
564 int i;
565 int j;
566
575
576 for( i = nchildren1 - 1, j = nchildren2 - 1; i >= 0 && j >= 0; --i, --j )
577 {
579 if( compareresult != 0 )
580 return compareresult;
581 else
582 {
583 /* expressions are equal, compare coefficient */
584 if( (coefs1 ? coefs1[i] : 1.0) < (coefs2 ? coefs2[j] : 1.0) )
585 return -1;
586 if( (coefs1 ? coefs1[i] : 1.0) > (coefs2 ? coefs2[j] : 1.0) )
587 return 1;
588
589 /* coefficients are equal, continue */
590 }
591 }
592
593 /* all children of one expression are children of the other expression, use number of children as a tie-breaker */
594 if( i < j )
595 {
596 assert(i == -1);
597 /* expr1 has less elements, hence expr1 < expr2 */
598 return -1;
599 }
600 if( i > j )
601 {
602 assert(j == -1);
603 /* expr1 has more elements, hence expr1 > expr2 */
604 return 1;
605 }
606
607 /* everything is equal, use constant/coefficient as tie-breaker */
608 assert(i == -1 && j == -1);
609 if( const1 < const2 )
610 return -1;
611 if( const1 > const2 )
612 return 1;
613
614 /* they are equal */
615 return 0;
616}
617
618/** expression handler copy callback */
619static
621{ /*lint --e{715}*/
623
624 return SCIP_OKAY;
625}
626
627/** expression data copy callback */
628static
644
645/** expression data free callback */
646static
648{ /*lint --e{715}*/
649 SCIP_EXPRDATA* exprdata;
650
651 assert(expr != NULL);
652
653 exprdata = SCIPexprGetData(expr);
654 assert(exprdata != NULL);
655
656 SCIPfreeBlockMemoryArray(scip, &(exprdata->coefficients), exprdata->coefssize);
657 SCIPfreeBlockMemory(scip, &exprdata);
658
659 SCIPexprSetData(expr, NULL);
660
661 return SCIP_OKAY;
662}
663
664/** expression print callback */
665static
667{ /*lint --e{715}*/
668 SCIP_EXPRDATA* exprdata;
669
670 assert(expr != NULL);
671
672 exprdata = SCIPexprGetData(expr);
673 assert(exprdata != NULL);
674
675 /**! [SnippetExprPrintSum] */
676 switch( stage )
677 {
679 {
680 /* print opening parenthesis, if necessary */
682 {
683 SCIPinfoMessage(scip, file, "(");
684 }
685
686 /* print constant, if nonzero */
687 if( exprdata->constant != 0.0 )
688 {
689 SCIPinfoMessage(scip, file, "%g", exprdata->constant);
690 }
691 break;
692 }
693
695 {
696 SCIP_Real coef;
697
698 coef = exprdata->coefficients[currentchild];
699
700 /* print coefficient, if necessary */
701 if( coef == 1.0 )
702 {
703 /* if coefficient is 1.0, then print only "+" if not the first term */
704 if( exprdata->constant != 0.0 || currentchild > 0 )
705 {
706 SCIPinfoMessage(scip, file, "+");
707 }
708 }
709 else if( coef == -1.0 )
710 {
711 /* if coefficient is -1.0, then print only "-" */
712 SCIPinfoMessage(scip, file, "-");
713 }
714 else
715 {
716 /* force "+" sign on positive coefficient if not the first term */
717 SCIPinfoMessage(scip, file, (exprdata->constant != 0.0 || currentchild > 0) ? "%+g*" : "%g*", coef);
718 }
719
720 break;
721 }
722
724 {
725 /* print closing parenthesis, if necessary */
727 {
728 SCIPinfoMessage(scip, file, ")");
729 }
730 break;
731 }
732
734 default: ;
735 }
736 /**! [SnippetExprPrintSum] */
737
738 return SCIP_OKAY;
739}
740
741/** expression point evaluation callback */
742static
744{ /*lint --e{715}*/
745 SCIP_EXPRDATA* exprdata;
746 int c;
747
748 assert(expr != NULL);
749
750 exprdata = SCIPexprGetData(expr);
751 assert(exprdata != NULL);
752
753 /**! [SnippetExprEvalSum] */
754 *val = exprdata->constant;
755 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
756 {
758
759 *val += exprdata->coefficients[c] * SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[c]);
760 }
761 /**! [SnippetExprEvalSum] */
762
763 return SCIP_OKAY;
764}
765
766/** expression forward derivative evaluation callback */
767static
769{ /*lint --e{715}*/
770 SCIP_EXPRDATA* exprdata;
771 int c;
772
773 assert(expr != NULL);
774 assert(dot != NULL);
775
776 exprdata = SCIPexprGetData(expr);
777 assert(exprdata != NULL);
778
779 *dot = 0.0;
780 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
781 {
782 assert(SCIPexprGetDot(SCIPexprGetChildren(expr)[c]) != SCIP_INVALID); /*lint !e777*/
783
784 *dot += exprdata->coefficients[c] * SCIPexprGetDot(SCIPexprGetChildren(expr)[c]);
785 }
786
787 return SCIP_OKAY;
788}
789
790/** expression derivative evaluation callback */
791static
793{ /*lint --e{715}*/
794 assert(expr != NULL);
795 assert(SCIPexprGetData(expr) != NULL);
799
800 *val = SCIPgetCoefsExprSum(expr)[childidx];
801
802 return SCIP_OKAY;
803}
804
805/** expression backward forward derivative evaluation callback */
806static
808{ /*lint --e{715}*/
809 assert(bardot != NULL);
810
811 *bardot = 0.0;
812
813 return SCIP_OKAY;
814}
815
816/** expression interval evaluation callback */
817static
819{ /*lint --e{715}*/
820 SCIP_EXPRDATA* exprdata;
822 int c;
823
824 assert(expr != NULL);
825
826 exprdata = SCIPexprGetData(expr);
827 assert(exprdata != NULL);
828
829 SCIPintervalSet(interval, exprdata->constant);
830
831 SCIPdebugMsg(scip, "inteval %p with %d children: %.20g", (void*)expr, SCIPexprGetNChildren(expr), exprdata->constant);
832
833 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
834 {
836
839 {
841 break;
842 }
843
844 /* compute coefficients[c] * childinterval and add the result to the so far computed interval */
845 if( exprdata->coefficients[c] == 1.0 )
846 {
848 }
849 else
850 {
853 }
854
855 SCIPdebugMsgPrint(scip, " %+.20g*[%.20g,%.20g]", exprdata->coefficients[c], childinterval.inf, childinterval.sup);
856 }
857 SCIPdebugMsgPrint(scip, " = [%.20g,%.20g]\n", interval->inf, interval->sup);
858
859 return SCIP_OKAY;
860}
861
862/** initial estimators callback */
863static
865{ /*lint --e{715}*/
866 SCIP_EXPRDATA* exprdata;
867
868#ifdef SCIP_DEBUG
869 SCIPinfoMessage(scip, NULL, "initEstimatesSum %d children: ", SCIPexprGetNChildren(expr));
870 SCIPprintExpr(scip, expr, NULL);
871 SCIPinfoMessage(scip, NULL, "\n");
872#endif
873 assert(scip != NULL);
874 assert(expr != NULL);
876
877 assert(coefs[0] != NULL);
878 assert(constant != NULL);
880
881 exprdata = SCIPexprGetData(expr);
882 assert(exprdata != NULL);
883
884 BMScopyMemoryArray(coefs[0], exprdata->coefficients, SCIPexprGetNChildren(expr));
885 *constant = exprdata->constant;
886 *nreturned = 1;
887
888 return SCIP_OKAY;
889}
890
891/** expression estimate callback */
892static
894{ /*lint --e{715}*/
895 SCIP_EXPRDATA* exprdata;
896
897 assert(scip != NULL);
898 assert(expr != NULL);
900 assert(islocal != NULL);
901 assert(success != NULL);
902 assert(branchcand != NULL);
903
904 exprdata = SCIPexprGetData(expr);
905 assert(exprdata != NULL);
906
907 /* NOTE: nlhdlr_default assumes in nlhdlrInitSepaDefault that this estimator can be used for both under- and overestimation */
908
909 BMScopyMemoryArray(coefs, exprdata->coefficients, SCIPexprGetNChildren(expr));
910 *constant = exprdata->constant;
911 *islocal = FALSE;
912 *success = TRUE;
913
914 /* for none of our children, branching would improve the underestimator, so set branchcand[i]=FALSE everywhere
915 * if we branch for numerical reasons, then cons-expr-core should figure out what the candidates are
916 */
917 BMSclearMemoryArray(branchcand, SCIPexprGetNChildren(expr));
918
919 return SCIP_OKAY;
920}
921
922/** expression reverse propagation callback */
923static
925{ /*lint --e{715}*/
926 SCIP_EXPRDATA* exprdata;
928 int nchildren;
929 int nreductions;
930
931 assert(scip != NULL);
932 assert(expr != NULL);
933 assert(infeasible != NULL);
934
935 nchildren = SCIPexprGetNChildren(expr);
936 assert(nchildren > 0);
937
938 exprdata = SCIPexprGetData(expr);
939 assert(exprdata != NULL);
940
942
944 exprdata->coefficients, exprdata->constant, bounds, newbounds, infeasible);
945
946 if( !*infeasible && nreductions > 0 )
948
950
951 return SCIP_OKAY;
952}
953
954/** sum hash callback */
955static
957{ /*lint --e{715}*/
958 SCIP_EXPRDATA* exprdata;
959 int c;
960
961 assert(scip != NULL);
962 assert(expr != NULL);
963 assert(hashkey != NULL);
965
966 exprdata = SCIPexprGetData(expr);
967 assert(exprdata != NULL);
968
969 /**! [SnippetExprHashSum] */
971 *hashkey ^= SCIPcalcFibHash(exprdata->constant);
972
973 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
974 *hashkey ^= SCIPcalcFibHash(exprdata->coefficients[c]) ^ childrenhashes[c];
975 /**! [SnippetExprHashSum] */
976
977 return SCIP_OKAY;
978}
979
980/** expression curvature detection callback */
981static
983{ /*lint --e{715}*/
984 SCIP_EXPRDATA* exprdata;
985 int i;
986
987 assert(scip != NULL);
988 assert(expr != NULL);
990 assert(success != NULL);
991
992 exprdata = SCIPexprGetData(expr);
993 assert(exprdata != NULL);
994
995 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
996 childcurv[i] = SCIPexprcurvMultiply(exprdata->coefficients[i], exprcurvature);
997
998 *success = TRUE;
999
1000 return SCIP_OKAY;
1001}
1002
1003/** expression monotonicity detection callback */
1004static
1006{ /*lint --e{715}*/
1007 SCIP_EXPRDATA* exprdata;
1008
1009 assert(scip != NULL);
1010 assert(expr != NULL);
1011 assert(result != NULL);
1013
1014 exprdata = SCIPexprGetData(expr);
1015 assert(exprdata != NULL);
1016
1017 *result = exprdata->coefficients[childidx] >= 0.0 ? SCIP_MONOTONE_INC : SCIP_MONOTONE_DEC;
1018
1019 return SCIP_OKAY;
1020}
1021
1022/** expression integrality detection callback */
1023static
1025{ /*lint --e{715}*/
1026 SCIP_EXPRDATA* exprdata;
1027 int i;
1028
1029 assert(scip != NULL);
1030 assert(expr != NULL);
1031 assert(isintegral != NULL);
1032
1033 exprdata = SCIPexprGetData(expr);
1034 assert(exprdata != NULL);
1035
1036 /**! [SnippetExprIntegralitySum] */
1037 *isintegral = EPSISINT(exprdata->constant, 0.0); /*lint !e835*/
1038
1039 for( i = 0; i < SCIPexprGetNChildren(expr) && *isintegral; ++i )
1040 {
1041 SCIP_EXPR* child = SCIPexprGetChildren(expr)[i];
1042 assert(child != NULL);
1043
1044 *isintegral = EPSISINT(exprdata->coefficients[i], 0.0) && SCIPexprIsIntegral(child); /*lint !e835*/
1045 }
1046 /**! [SnippetExprIntegralitySum] */
1047
1048 return SCIP_OKAY;
1049}
1050
1051/** creates the handler for sum expressions and includes it into SCIP */
1077
1078/** creates a sum expression */
1080 SCIP* scip, /**< SCIP data structure */
1081 SCIP_EXPR** expr, /**< pointer where to store expression */
1082 int nchildren, /**< number of children */
1083 SCIP_EXPR** children, /**< children */
1084 SCIP_Real* coefficients, /**< array with coefficients for all children (or NULL if all 1.0) */
1085 SCIP_Real constant, /**< constant term of sum */
1086 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
1087 void* ownercreatedata /**< data to pass to ownercreate */
1088 )
1089{
1090 SCIP_EXPRDATA* exprdata;
1091
1092 SCIP_CALL( createData(scip, &exprdata, nchildren, coefficients, constant) );
1093
1094 SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrSum(scip), exprdata, nchildren, children, ownercreate, ownercreatedata) );
1095
1096 return SCIP_OKAY;
1097}
1098
1099/** sets the constant of a summation expression */
1101 SCIP_EXPR* expr, /**< sum expression */
1102 SCIP_Real constant /**< constant */
1103 )
1104{
1105 SCIP_EXPRDATA* exprdata;
1106
1107 assert(expr != NULL);
1108
1109 exprdata = SCIPexprGetData(expr);
1110 assert(exprdata != NULL);
1111
1112 exprdata->constant = constant;
1113}
1114
1115/** appends an expression to a sum expression */
1117 SCIP* scip, /**< SCIP data structure */
1118 SCIP_EXPR* expr, /**< sum expression */
1119 SCIP_EXPR* child, /**< expression to be appended */
1120 SCIP_Real childcoef /**< child's coefficient */
1121 )
1122{
1123 SCIP_EXPRDATA* exprdata;
1124 int nchildren;
1125
1126 assert(expr != NULL);
1127 assert(SCIPisExprSum(scip, expr));
1128
1129 exprdata = SCIPexprGetData(expr);
1130 assert(exprdata != NULL);
1131
1132 nchildren = SCIPexprGetNChildren(expr);
1133
1134 SCIP_CALL( SCIPensureBlockMemoryArray(scip, &exprdata->coefficients, &exprdata->coefssize, nchildren + 1) );
1135
1136 assert(exprdata->coefssize > nchildren);
1137 exprdata->coefficients[nchildren] = childcoef;
1138
1139 SCIP_CALL( SCIPappendExprChild(scip, expr, child) );
1140
1141 return SCIP_OKAY;
1142}
1143
1144/** multiplies given sum expression by a constant */
1146 SCIP_EXPR* expr, /**< sum expression */
1147 SCIP_Real constant /**< constant that multiplies sum expression */
1148 )
1149{
1150 int i;
1151 SCIP_EXPRDATA* exprdata;
1152
1153 assert(expr != NULL);
1154
1155 exprdata = SCIPexprGetData(expr);
1156 assert(exprdata != NULL);
1157
1158 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
1159 exprdata->coefficients[i] *= constant;
1160 exprdata->constant *= constant;
1161}
1162
1163/* from pub_expr.h */
1164
1165/** gets the coefficients of a summation expression */
1167 SCIP_EXPR* expr /**< sum expression */
1168 )
1169{
1170 SCIP_EXPRDATA* exprdata;
1171
1172 assert(expr != NULL);
1173
1174 exprdata = SCIPexprGetData(expr);
1175 assert(exprdata != NULL);
1176
1177 return exprdata->coefficients;
1178}
1179
1180/** gets the constant of a summation expression */
1182 SCIP_EXPR* expr /**< sum expression */
1183 )
1184{
1185 SCIP_EXPRDATA* exprdata;
1186
1187 assert(expr != NULL);
1188
1189 exprdata = SCIPexprGetData(expr);
1190 assert(exprdata != NULL);
1191
1192 return exprdata->constant;
1193}
#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 REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
exponential expression handler
product expression handler
#define debugSimplify
Definition expr_sum.c:53
#define EXPRHDLR_HASHKEY
Definition expr_sum.c:46
#define EXPRHDLR_NAME
Definition expr_sum.c:43
static SCIP_RETCODE createData(SCIP *scip, SCIP_EXPRDATA **exprdata, int ncoefficients, SCIP_Real *coefficients, SCIP_Real constant)
Definition expr_sum.c:74
static SCIP_RETCODE simplifyTerm(SCIP *scip, SCIP_EXPR *duplicate, int idx, SCIP_Bool *changed, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_sum.c:112
#define EXPRHDLR_DESC
Definition expr_sum.c:44
#define EXPRHDLR_PRECEDENCE
Definition expr_sum.c:45
sum expression handler
constant value expression handler
SCIP_RETCODE SCIPcreateExprProduct(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
void SCIPsetConstantExprSum(SCIP_EXPR *expr, SCIP_Real constant)
Definition expr_sum.c:1100
void SCIPmultiplyByConstantExprSum(SCIP_EXPR *expr, SCIP_Real constant)
Definition expr_sum.c:1145
SCIP_RETCODE SCIPappendExprSumExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child, SCIP_Real childcoef)
Definition expr_sum.c:1116
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_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 SCIPincludeExprhdlrSum(SCIP *scip)
Definition expr_sum.c:1052
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsgPrint
#define SCIPdebugMsg
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition misc.c:10258
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
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_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
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
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition scip_expr.c:1220
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition expr.c:3849
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
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_RETCODE SCIPreplaceExprChild(SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition scip_expr.c:1238
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition expr_sum.c:1166
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1432
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_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
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_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3824
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
int SCIPintervalPropagateWeightedSum(SCIP_Real infinity, int noperands, SCIP_INTERVAL *operands, SCIP_Real *weights, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_INTERVAL *resultants, SCIP_Bool *infeasible)
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition scip_mem.h:107
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
#define BMScopyMemoryArray(ptr, source, num)
Definition memory.h:136
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
SCIP_EXPR ** exprs
Definition expr_sum.c:340
SCIP * scip
Definition expr_sum.c:339
#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_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_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_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
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:180
enum SCIP_Retcode SCIP_RETCODE