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_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   	 */
60   	static
61   	SCIP_Real reversePropBinarySearch(
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 */
111  	static
112  	SCIP_RETCODE reverseProp(
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))
133  	      || SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childinterval) )
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 */
144  	   if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, intersection) )
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  	   {
153  	      SCIPintervalSetBounds(interval, 0.0, SCIP_INTERVAL_INFINITY);
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);
168  	   SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &tmp, tmp);
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);
191  	      SCIPintervalEntropy(SCIP_INTERVAL_INFINITY, &tmp, tmp);
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 */
232  	static
233  	SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy)
234  	{  /*lint --e{715}*/
235  	   SCIP_CALL( SCIPincludeExprhdlrEntropy(scip) );
236  	
237  	   return SCIP_OKAY;
238  	}
239  	
240  	/** simplifies an entropy expression */
241  	static
242  	SCIP_DECL_EXPRSIMPLIFY(simplifyEntropy)
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 */
286  	static
287  	SCIP_DECL_EXPRCOPYDATA(copydataEntropy)
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 */
298  	static
299  	SCIP_DECL_EXPRFREEDATA(freedataEntropy)
300  	{  /*lint --e{715}*/
301  	   assert(expr != NULL);
302  	
303  	   SCIPexprSetData(expr, NULL);
304  	   return SCIP_OKAY;
305  	}
306  	
307  	/** expression parse callback */
308  	static
309  	SCIP_DECL_EXPRPARSE(parseEntropy)
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 */
333  	static
334  	SCIP_DECL_EXPREVAL(evalEntropy)
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 */
364  	static
365  	SCIP_DECL_EXPRBWDIFF(bwdiffEntropy)
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 */
391  	static
392  	SCIP_DECL_EXPRINTEVAL(intevalEntropy)
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 */
411  	static
412  	SCIP_DECL_EXPRESTIMATE(estimateEntropy)
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 */
485  	static
486  	SCIP_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 */
550  	static
551  	SCIP_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 */
571  	static
572  	SCIP_DECL_EXPRHASH(hashEntropy)
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 */
586  	static
587  	SCIP_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 */
608  	static
609  	SCIP_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  	
623  	   SCIP_CALL( SCIPevalExprActivity(scip, child) );
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 */
637  	static
638  	SCIP_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 */
653  	SCIP_RETCODE SCIPincludeExprhdlrEntropy(
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 */
664  	   SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, EXPRHDLR_NAME, EXPRHDLR_DESC, EXPRHDLR_PRECEDENCE,
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 */
685  	SCIP_RETCODE SCIPcreateExprEntropy(
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  	
699  	   exprhdlr = SCIPfindExprhdlr(scip, EXPRHDLR_NAME);
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}*/
712  	SCIP_Bool SCIPisExprEntropy(
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  	}
721