Scippy

SCIP

Solving Constraint Integer Programs

expr_entropy.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file expr_entropy.c
26 * @ingroup DEFPLUGINS_EXPR
27 * @brief handler for -x*log(x) expressions
28 * @author Benjamin Mueller
29 * @author Fabian Wegscheider
30 * @author Ksenia Bestuzheva
31 *
32 * @todo replace exp(-1.0) by 1.0/M_E
33 */
34
35/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36
37#include "scip/expr_entropy.h"
38#include "scip/expr_value.h"
39#include "scip/expr.h"
40
41#include <string.h>
42
43/* fundamental expression handler properties */
44#define EXPRHDLR_NAME "entropy"
45#define EXPRHDLR_DESC "entropy expression (-x*log(x))"
46#define EXPRHDLR_PRECEDENCE 81000
47#define EXPRHDLR_HASHKEY SCIPcalcFibHash(7477.0)
48
49/*
50 * Data structures
51 */
52
53/*
54 * Local methods
55 */
56
57/** helper function for reverseProp() which returns an x* in [xmin,xmax] s.t. the distance -x*log(x) and a given target
58 * value is minimized; the function assumes that -x*log(x) is monotone on [xmin,xmax];
59 */
60static
62 SCIP* scip, /**< SCIP data structure */
63 SCIP_Real xmin, /**< smallest possible x */
64 SCIP_Real xmax, /**< largest possible x */
65 SCIP_Bool increasing, /**< -x*log(x) is increasing or decreasing on [xmin,xmax] */
66 SCIP_Real targetval /**< target value */
67 )
68{
69 SCIP_Real xminval = (xmin == 0.0) ? 0.0 : -xmin * log(xmin);
70 SCIP_Real xmaxval = (xmax == 0.0) ? 0.0 : -xmax * log(xmax);
71 int i;
72
73 assert(xmin <= xmax);
74 assert(increasing ? xminval <= xmaxval : xminval >= xmaxval);
75
76 /* function can not achieve -x*log(x) -> return xmin or xmax */
77 if( SCIPisGE(scip, xminval, targetval) && SCIPisGE(scip, xmaxval, targetval) )
78 return increasing ? xmin : xmax;
79 else if( SCIPisLE(scip, xminval, targetval) && SCIPisLE(scip, xmaxval, targetval) )
80 return increasing ? xmax : xmin;
81
82 /* binary search */
83 for( i = 0; i < 1000; ++i )
84 {
85 SCIP_Real x = (xmin + xmax) / 2.0;
86 SCIP_Real xval = (x == 0.0) ? 0.0 : -x * log(x);
87
88 /* found the corresponding point -> skip */
89 if( SCIPisEQ(scip, xval, targetval) )
90 return x;
91 else if( SCIPisLT(scip, xval, targetval) )
92 {
93 if( increasing )
94 xmin = x;
95 else
96 xmax = x;
97 }
98 else
99 {
100 if( increasing )
101 xmax = x;
102 else
103 xmin = x;
104 }
105 }
106
107 return SCIP_INVALID;
108}
109
110/** helper function for reverse propagation; needed for proper unittest */
111static
113 SCIP* scip, /**< SCIP data structure */
114 SCIP_INTERVAL exprinterval, /**< bounds on the expression */
115 SCIP_INTERVAL childinterval, /**< bounds on the interval of the child */
116 SCIP_INTERVAL* interval /**< resulting interval */
117 )
118{
119 SCIP_INTERVAL childentropy;
120 SCIP_INTERVAL intersection;
121 SCIP_INTERVAL tmp;
122 SCIP_Real childinf;
123 SCIP_Real childsup;
124 SCIP_Real extremum;
125 SCIP_Real boundinf;
126 SCIP_Real boundsup;
127
128 assert(scip != NULL);
129 assert(interval != NULL);
130
131 /* check whether domain is empty, i.e., bounds on -x*log(x) > 1/e */
132 if( SCIPisGT(scip, SCIPintervalGetInf(exprinterval), exp(-1.0))
134 {
135 SCIPintervalSetEmpty(interval);
136 return SCIP_OKAY;
137 }
138
139 /* compute the intersection between entropy([childinf,childsup]) and [expr.inf, expr.sup] */
140 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &childentropy, childinterval);
141 SCIPintervalIntersect(&intersection, childentropy, exprinterval);
142
143 /* intersection empty -> infeasible */
145 {
146 SCIPintervalSetEmpty(interval);
147 return SCIP_OKAY;
148 }
149
150 /* intersection = childentropy -> nothing can be learned */
151 if( SCIPintervalIsSubsetEQ(SCIP_INTERVAL_INFINITY, childentropy, intersection) )
152 {
154 SCIPintervalIntersect(interval, *interval, childinterval);
155 return SCIP_OKAY;
156 }
157
158 childinf = MAX(0.0, SCIPintervalGetInf(childinterval)); /*lint !e666*/
159 childsup = SCIPintervalGetSup(childinterval);
160 extremum = exp(-1.0);
161 boundinf = SCIP_INVALID;
162 boundsup = SCIP_INVALID;
163
164 /*
165 * check whether lower bound of child can be improved
166 */
167 SCIPintervalSet(&tmp, childinf);
169
170 /* entropy(childinf) < intersection.inf -> consider [childinf, MIN(childsup, extremum)] */
171 if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) )
172 {
173 boundinf = reversePropBinarySearch(scip, childinf, MIN(extremum, childsup), TRUE,
174 SCIPintervalGetInf(intersection));
175 }
176 /* entropy(childinf) > intersection.sup -> consider [MAX(childinf,extremum), childsup] */
177 else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) )
178 {
179 boundinf = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE,
180 SCIPintervalGetSup(intersection));
181 }
182 /* using a strict greater-than here because we expect a tightening because we saw an at-least-epsilon-potential above */
183 assert(boundinf == SCIP_INVALID || boundinf > childinf); /*lint !e777*/
184
185 /*
186 * check whether upper bound of child can be improved
187 */
188 if( childsup < SCIP_INTERVAL_INFINITY )
189 {
190 SCIPintervalSet(&tmp, childsup);
192 }
193 else
194 SCIPintervalSetBounds(&tmp, -SCIP_INTERVAL_INFINITY, -SCIP_INTERVAL_INFINITY); /* entropy(inf) = -inf */
195
196 /* entropy(childsup) < intersection.inf -> consider [MAX(childinf,extremum), childsup] */
197 if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) )
198 {
199 boundsup = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE,
200 SCIPintervalGetInf(intersection));
201 }
202 /* entropy(childsup) > intersection.sup -> consider [childinf, MIN(childsup,extremum)] */
203 else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) )
204 {
205 boundsup = reversePropBinarySearch(scip, childinf, MIN(childsup, extremum), TRUE,
206 SCIPintervalGetSup(intersection));
207 }
208 /* using a strict smaller-than here because we expect a tightening because we saw an at-least-epsilon-potential above */
209 assert(boundsup == SCIP_INVALID || boundsup < childsup); /*lint !e777*/
210
211 if( boundinf != SCIP_INVALID ) /*lint !e777*/
212 {
213 childinf = MAX(childinf, boundinf);
214 }
215 if( boundsup != SCIP_INVALID ) /*lint !e777*/
216 {
217 childsup = boundsup;
218 }
219 assert(childinf <= childsup); /* infeasible case has been handled already */
220
221 /* set the resulting bounds */
222 SCIPintervalSetBounds(interval, childinf, childsup);
223
224 return SCIP_OKAY;
225}
226
227/*
228 * Callback methods of expression handler
229 */
230
231/** expression handler copy callback */
232static
234{ /*lint --e{715}*/
236
237 return SCIP_OKAY;
238}
239
240/** simplifies an entropy expression */
241static
243{ /*lint --e{715}*/
244 SCIP_EXPR* child;
245
246 assert(scip != NULL);
247 assert(expr != NULL);
248 assert(simplifiedexpr != NULL);
249 assert(SCIPexprGetNChildren(expr) == 1);
250
251 child = SCIPexprGetChildren(expr)[0];
252 assert(child != NULL);
253
254 /* check for value expression */
255 if( SCIPisExprValue(scip, child) )
256 {
257 SCIP_Real childvalue = SCIPgetValueExprValue(child);
258
259 /* TODO how to handle a negative value? */
260 assert(childvalue >= 0.0);
261
262 if( childvalue == 0.0 || childvalue == 1.0 )
263 {
264 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, 0.0, ownercreate, ownercreatedata) );
265 }
266 else
267 {
268 SCIP_CALL( SCIPcreateExprValue(scip, simplifiedexpr, -childvalue * log(childvalue), ownercreate,
269 ownercreatedata) );
270 }
271 }
272 else
273 {
274 *simplifiedexpr = expr;
275
276 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
277 SCIPcaptureExpr(*simplifiedexpr);
278 }
279
280 /* TODO handle -x*log(x) = 0 if x in {0,1} */
281
282 return SCIP_OKAY;
283}
284
285/** expression data copy callback */
286static
288{ /*lint --e{715}*/
289 assert(targetexprdata != NULL);
290 assert(sourceexpr != NULL);
291 assert(SCIPexprGetData(sourceexpr) == NULL);
292
293 *targetexprdata = NULL;
294 return SCIP_OKAY;
295}
296
297/** expression data free callback */
298static
300{ /*lint --e{715}*/
301 assert(expr != NULL);
302
303 SCIPexprSetData(expr, NULL);
304 return SCIP_OKAY;
305}
306
307/** expression parse callback */
308static
310{ /*lint --e{715}*/
311 SCIP_EXPR* childexpr;
312
313 assert(expr != NULL);
314
315 /* parse child expression from remaining string */
316 SCIP_CALL( SCIPparseExpr(scip, &childexpr, string, endstring, ownercreate, ownercreatedata) );
317 assert(childexpr != NULL);
318
319 /* create entropy expression */
320 SCIP_CALL( SCIPcreateExprEntropy(scip, expr, childexpr, ownercreate, ownercreatedata) );
321 assert(*expr != NULL);
322
323 /* release child expression since it has been captured by the entropy expression */
324 SCIP_CALL( SCIPreleaseExpr(scip, &childexpr) );
325
326 *success = TRUE;
327
328 return SCIP_OKAY;
329}
330
331
332/** expression (point-) evaluation callback */
333static
335{ /*lint --e{715}*/
336 SCIP_Real childvalue;
337
338 assert(expr != NULL);
339 assert(SCIPexprGetData(expr) == NULL);
340 assert(SCIPexprGetNChildren(expr) == 1);
341 assert(SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]) != SCIP_INVALID); /*lint !e777*/
342
343 childvalue = SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]);
344
345 if( childvalue < 0.0 )
346 {
347 SCIPdebugMsg(scip, "invalid evaluation of entropy expression\n");
348 *val = SCIP_INVALID;
349 }
350 else if( childvalue == 0.0 || childvalue == 1.0 )
351 {
352 /* -x*log(x) = 0 iff x in {0,1} */
353 *val = 0.0;
354 }
355 else
356 {
357 *val = -childvalue * log(childvalue);
358 }
359
360 return SCIP_OKAY;
361}
362
363/** expression derivative evaluation callback */
364static
366{ /*lint --e{715}*/
367 SCIP_EXPR* child;
368 SCIP_Real childvalue;
369
370 assert(expr != NULL);
371 assert(childidx == 0);
372 assert(SCIPexprGetNChildren(expr) == 1);
373 assert(SCIPexprGetEvalValue(expr) != SCIP_INVALID); /*lint !e777*/
374
375 child = SCIPexprGetChildren(expr)[0];
376 assert(child != NULL);
377 assert(!SCIPisExprValue(scip, child));
378
379 childvalue = SCIPexprGetEvalValue(child);
380
381 /* derivative is not defined for x = 0 */
382 if( childvalue <= 0.0 )
383 *val = SCIP_INVALID;
384 else
385 *val = -1.0 - log(childvalue);
386
387 return SCIP_OKAY;
388}
389
390/** expression interval evaluation callback */
391static
393{ /*lint --e{715}*/
394 SCIP_INTERVAL childinterval;
395
396 assert(expr != NULL);
397 assert(SCIPexprGetData(expr) == NULL);
398 assert(SCIPexprGetNChildren(expr) == 1);
399
400 childinterval = SCIPexprGetActivity(SCIPexprGetChildren(expr)[0]);
401
402 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childinterval) )
403 SCIPintervalSetEmpty(interval);
404 else
405 SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, interval, childinterval);
406
407 return SCIP_OKAY;
408}
409
410/** expression estimator callback */
411static
413{ /*lint --e{715}*/
414 assert(scip != NULL);
415 assert(expr != NULL);
416 assert(localbounds != NULL);
417 assert(globalbounds != NULL);
418 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
419 assert(refpoint != NULL);
420 assert(coefs != NULL);
421 assert(constant != NULL);
422 assert(islocal != NULL);
423 assert(branchcand != NULL);
424 assert(*branchcand == TRUE);
425 assert(success != NULL);
426
427 *success = FALSE;
428
429 /* use secant for underestimate (locally valid) */
430 if( !overestimate )
431 {
432 SCIP_Real lb;
433 SCIP_Real ub;
434 SCIP_Real vallb;
435 SCIP_Real valub;
436
437 lb = localbounds[0].inf;
438 ub = localbounds[0].sup;
439
440 if( lb < 0.0 || SCIPisInfinity(scip, ub) || SCIPisEQ(scip, lb, ub) )
441 return SCIP_OKAY;
442
443 assert(lb >= 0.0 && ub >= 0.0);
444 assert(ub - lb != 0.0);
445
446 vallb = (lb == 0.0) ? 0.0 : -lb * log(lb);
447 valub = (ub == 0.0) ? 0.0 : -ub * log(ub);
448
449 coefs[0] = (valub - vallb) / (ub - lb);
450 *constant = valub - coefs[0] * ub;
451 assert(SCIPisEQ(scip, *constant, vallb - coefs[0] * lb));
452
453 *islocal = TRUE;
454 }
455 /* use gradient cut for overestimate (globally valid) */
456 else
457 {
458 if( !SCIPisPositive(scip, refpoint[0]) )
459 {
460 /* if refpoint is 0 (then lb=0 probably) or negative, then slope is infinite (or not defined), then try to move away from 0 */
461 if( SCIPisZero(scip, localbounds[0].sup) )
462 return SCIP_OKAY;
463
464 refpoint[0] = SCIPepsilon(scip);
465 }
466
467 /* -x*(1+log(x*)) + x* <= -x*log(x) */
468 coefs[0] = -(1.0 + log(refpoint[0]));
469 *constant = refpoint[0];
470
471 *islocal = FALSE;
472 *branchcand = FALSE;
473 }
474
475 /* give up if the constant or coefficient is too large */
476 if( SCIPisInfinity(scip, REALABS(*constant)) || SCIPisInfinity(scip, REALABS(coefs[0])) )
477 return SCIP_OKAY;
478
479 *success = TRUE;
480
481 return SCIP_OKAY;
482}
483
484/** initial estimates callback */
485static
486SCIP_DECL_EXPRINITESTIMATES(initestimatesEntropy)
487{ /*lint --e{715}*/
488 SCIP_Real refpointsover[3] = {SCIP_INVALID, SCIP_INVALID, SCIP_INVALID};
489 SCIP_Bool overest[4] = {TRUE, TRUE, TRUE, FALSE};
490 SCIP_Real lb;
491 SCIP_Real ub;
492 int i;
493
494 assert(scip != NULL);
495 assert(expr != NULL);
496 assert(SCIPexprGetNChildren(expr) == 1);
497 assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
498
499 lb = bounds[0].inf;
500 ub = bounds[0].sup;
501
502 if( SCIPisEQ(scip, lb, ub) )
503 return SCIP_OKAY;
504
505 if( overestimate )
506 {
507 /* adjust lb */
508 lb = MAX(lb, SCIPepsilon(scip)); /*lint !e666*/
509
510 refpointsover[0] = lb;
511 refpointsover[1] = SCIPisInfinity(scip, ub) ? lb + 2.0 : (lb + ub) / 2;
512 refpointsover[2] = SCIPisInfinity(scip, ub) ? lb + 20.0 : ub;
513 }
514
515 *nreturned = 0;
516
517 for( i = 0; i < 4; ++i )
518 {
519 if( (overest[i] && !overestimate) || (!overest[i] && (overestimate || SCIPisInfinity(scip, ub))) )
520 continue;
521
522 assert(!overest[i] || (SCIPisLE(scip, refpointsover[i], ub) && SCIPisGE(scip, refpointsover[i], lb))); /*lint !e661*/
523
524 if( overest[i] )
525 { /*lint !e661*/
526 /* -x*(1+log(x*)) + x* <= -x*log(x) */
527 assert(i < 3);
528 /* coverity[overrun] */
529 coefs[*nreturned][0] = -(1.0 + log(refpointsover[i]));
530 /* coverity[overrun] */
531 constant[*nreturned] = refpointsover[i];
532 }
533 else
534 {
535 assert(lb > 0.0 && ub >= 0.0);
536 assert(ub - lb != 0.0);
537
538 coefs[*nreturned][0] = (-ub * log(ub) + lb * log(lb)) / (ub - lb);
539 constant[*nreturned] = -ub * log(ub) - coefs[*nreturned][0] * ub;
540 assert(SCIPisEQ(scip, constant[*nreturned], -lb * log(lb) - coefs[*nreturned][0] * lb));
541 }
542
543 ++(*nreturned);
544 }
545
546 return SCIP_OKAY;
547}
548
549/** expression reverse propagation callback */
550static
551SCIP_DECL_EXPRREVERSEPROP(reversepropEntropy)
552{ /*lint --e{715}*/
553 SCIP_INTERVAL newinterval;
554
555 assert(scip != NULL);
556 assert(expr != NULL);
557 assert(SCIPexprGetNChildren(expr) == 1);
558 assert(childrenbounds != NULL);
559 assert(infeasible != NULL);
560
561 /* compute resulting intervals (reverseProp handles childinterval being empty) */
562 SCIP_CALL( reverseProp(scip, bounds, childrenbounds[0], &newinterval) );
563 assert(SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, newinterval) || newinterval.inf >= 0.0);
564
565 childrenbounds[0] = newinterval;
566
567 return SCIP_OKAY;
568}
569
570/** entropy hash callback */
571static
573{ /*lint --e{715}*/
574 assert(expr != NULL);
575 assert(SCIPexprGetNChildren(expr) == 1);
576 assert(hashkey != NULL);
577 assert(childrenhashes != NULL);
578
579 *hashkey = EXPRHDLR_HASHKEY;
580 *hashkey ^= childrenhashes[0];
581
582 return SCIP_OKAY;
583}
584
585/** expression curvature detection callback */
586static
587SCIP_DECL_EXPRCURVATURE(curvatureEntropy)
588{ /*lint --e{715}*/
589 assert(scip != NULL);
590 assert(expr != NULL);
591 assert(childcurv != NULL);
592 assert(success != NULL);
593 assert(SCIPexprGetNChildren(expr) == 1);
594
595 /* to be concave, the child needs to be concave, too; we cannot be convex or linear */
596 if( exprcurvature == SCIP_EXPRCURV_CONCAVE )
597 {
598 *childcurv = SCIP_EXPRCURV_CONCAVE;
599 *success = TRUE;
600 }
601 else
602 *success = FALSE;
603
604 return SCIP_OKAY;
605}
606
607/** expression monotonicity detection callback */
608static
609SCIP_DECL_EXPRMONOTONICITY(monotonicityEntropy)
610{ /*lint --e{715}*/
611 SCIP_EXPR* child;
612 SCIP_INTERVAL childbounds;
613 SCIP_Real brpoint = exp(-1.0);
614
615 assert(scip != NULL);
616 assert(expr != NULL);
617 assert(result != NULL);
618 assert(childidx == 0);
619
620 child = SCIPexprGetChildren(expr)[0];
621 assert(child != NULL);
622
624 childbounds = SCIPexprGetActivity(child);
625
626 if( childbounds.sup <= brpoint )
627 *result = SCIP_MONOTONE_INC;
628 else if( childbounds.inf >= brpoint )
629 *result = SCIP_MONOTONE_DEC;
630 else
631 *result = SCIP_MONOTONE_UNKNOWN;
632
633 return SCIP_OKAY;
634}
635
636/** expression integrality detection callback */
637static
638SCIP_DECL_EXPRINTEGRALITY(integralityEntropy)
639{ /*lint --e{715}*/
640 assert(scip != NULL);
641 assert(expr != NULL);
642 assert(isintegral != NULL);
643
644 /* TODO it is possible to check for the special case that the child is integral and its bounds are [0,1]; in
645 * this case the entropy expression can only achieve 0 and is thus integral
646 */
647 *isintegral = FALSE;
648
649 return SCIP_OKAY;
650}
651
652/** creates the handler for entropy expressions and includes it into SCIP */
654 SCIP* scip /**< SCIP data structure */
655 )
656{
657 SCIP_EXPRHDLRDATA* exprhdlrdata;
658 SCIP_EXPRHDLR* exprhdlr;
659
660 /* create expression handler data */
661 exprhdlrdata = NULL;
662
663 /* include expression handler */
665 evalEntropy, exprhdlrdata) );
666 assert(exprhdlr != NULL);
667
668 SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrEntropy, NULL);
669 SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataEntropy, freedataEntropy);
670 SCIPexprhdlrSetSimplify(exprhdlr, simplifyEntropy);
671 SCIPexprhdlrSetParse(exprhdlr, parseEntropy);
672 SCIPexprhdlrSetIntEval(exprhdlr, intevalEntropy);
673 SCIPexprhdlrSetEstimate(exprhdlr, initestimatesEntropy, estimateEntropy);
674 SCIPexprhdlrSetReverseProp(exprhdlr, reversepropEntropy);
675 SCIPexprhdlrSetHash(exprhdlr, hashEntropy);
676 SCIPexprhdlrSetDiff(exprhdlr, bwdiffEntropy, NULL ,NULL);
677 SCIPexprhdlrSetCurvature(exprhdlr, curvatureEntropy);
678 SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityEntropy);
679 SCIPexprhdlrSetIntegrality(exprhdlr, integralityEntropy);
680
681 return SCIP_OKAY;
682}
683
684/** creates an entropy expression */
686 SCIP* scip, /**< SCIP data structure */
687 SCIP_EXPR** expr, /**< pointer where to store expression */
688 SCIP_EXPR* child, /**< child expression */
689 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
690 void* ownercreatedata /**< data to pass to ownercreate */
691 )
692{
693 SCIP_EXPRHDLR* exprhdlr;
694 SCIP_EXPRDATA* exprdata;
695
696 assert(expr != NULL);
697 assert(child != NULL);
698
700 assert(exprhdlr != NULL);
701
702 /* create expression data */
703 exprdata = NULL;
704
705 /* create expression */
706 SCIP_CALL( SCIPcreateExpr(scip, expr, exprhdlr, exprdata, 1, &child, ownercreate, ownercreatedata) );
707
708 return SCIP_OKAY;
709}
710
711/** indicates whether expression is of entropy-type */ /*lint -e{715}*/
713 SCIP* scip, /**< SCIP data structure */
714 SCIP_EXPR* expr /**< expression */
715 )
716{ /*lint --e{715}*/
717 assert(expr != NULL);
718
719 return strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0;
720}
SCIP_VAR ** x
Definition: circlepacking.c:63
#define NULL
Definition: def.h:267
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_INTERVAL_INFINITY
Definition: def.h:195
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
private functions to work with algebraic expressions
static SCIP_DECL_EXPRFREEDATA(freedataEntropy)
Definition: expr_entropy.c:299
static SCIP_DECL_EXPRBWDIFF(bwdiffEntropy)
Definition: expr_entropy.c:365
static SCIP_DECL_EXPRSIMPLIFY(simplifyEntropy)
Definition: expr_entropy.c:242
static SCIP_DECL_EXPRREVERSEPROP(reversepropEntropy)
Definition: expr_entropy.c:551
#define EXPRHDLR_HASHKEY
Definition: expr_entropy.c:47
static SCIP_DECL_EXPRESTIMATE(estimateEntropy)
Definition: expr_entropy.c:412
static SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy)
Definition: expr_entropy.c:233
static SCIP_DECL_EXPRHASH(hashEntropy)
Definition: expr_entropy.c:572
static SCIP_DECL_EXPRINITESTIMATES(initestimatesEntropy)
Definition: expr_entropy.c:486
#define EXPRHDLR_NAME
Definition: expr_entropy.c:44
static SCIP_DECL_EXPRINTEVAL(intevalEntropy)
Definition: expr_entropy.c:392
static SCIP_DECL_EXPRCOPYDATA(copydataEntropy)
Definition: expr_entropy.c:287
static SCIP_DECL_EXPRCURVATURE(curvatureEntropy)
Definition: expr_entropy.c:587
static SCIP_RETCODE reverseProp(SCIP *scip, SCIP_INTERVAL exprinterval, SCIP_INTERVAL childinterval, SCIP_INTERVAL *interval)
Definition: expr_entropy.c:112
static SCIP_DECL_EXPRMONOTONICITY(monotonicityEntropy)
Definition: expr_entropy.c:609
static SCIP_DECL_EXPRINTEGRALITY(integralityEntropy)
Definition: expr_entropy.c:638
static SCIP_Real reversePropBinarySearch(SCIP *scip, SCIP_Real xmin, SCIP_Real xmax, SCIP_Bool increasing, SCIP_Real targetval)
Definition: expr_entropy.c:61
#define EXPRHDLR_DESC
Definition: expr_entropy.c:45
#define EXPRHDLR_PRECEDENCE
Definition: expr_entropy.c:46
static SCIP_DECL_EXPREVAL(evalEntropy)
Definition: expr_entropy.c:334
static SCIP_DECL_EXPRPARSE(parseEntropy)
Definition: expr_entropy.c:309
handler for -x*log(x) expressions
constant value expression handler
SCIP_Bool SCIPisExprEntropy(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_entropy.c:712
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)
Definition: expr_entropy.c:685
SCIP_RETCODE SCIPincludeExprhdlrEntropy(SCIP *scip)
Definition: expr_entropy.c:653
#define SCIPdebugMsg
Definition: scip_message.h:78
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:545
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:440
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:383
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:451
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:370
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:473
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:510
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
Definition: expr.c:407
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:532
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:429
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:488
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:418
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:823
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:868
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:499
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:974
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3908
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3860
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1442
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3893
SCIP_RETCODE SCIPparseExpr(SCIP *scip, SCIP_EXPR **expr, const char *exprstr, const char **finalpos, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1380
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:294
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3934
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3870
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:4016
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1409
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3883
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
void SCIPintervalEntropy(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_Real inf
Definition: intervalarith.h:55
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:143
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:195
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:54
@ SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:64
@ SCIP_MONOTONE_UNKNOWN
Definition: type_expr.h:71
@ SCIP_MONOTONE_INC
Definition: type_expr.h:72
@ SCIP_MONOTONE_DEC
Definition: type_expr.h:73
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63