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