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