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-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
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
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  {
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);
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);
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}*/
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 
493  if( SCIPisEQ(scip, lb, ub) )
494  return SCIP_OKAY;
495 
496  if( overestimate )
497  {
498  /* adjust lb */
499  lb = MAX(lb, SCIPepsilon(scip)); /*lint !e666*/
500 
501  refpointsover[0] = lb;
502  refpointsover[1] = SCIPisInfinity(scip, ub) ? lb + 2.0 : (lb + ub) / 2;
503  refpointsover[2] = SCIPisInfinity(scip, ub) ? lb + 20.0 : ub;
504  }
505 
506  *nreturned = 0;
507 
508  for( i = 0; i < 4; ++i )
509  {
510  if( (overest[i] && !overestimate) || (!overest[i] && (overestimate || SCIPisInfinity(scip, ub))) )
511  continue;
512 
513  assert(!overest[i] || (SCIPisLE(scip, refpointsover[i], ub) && SCIPisGE(scip, refpointsover[i], lb))); /*lint !e661*/
514 
515  if( overest[i] )
516  { /*lint !e661*/
517  /* -x*(1+log(x*)) + x* <= -x*log(x) */
518  assert(i < 3);
519  coefs[*nreturned][0] = -(1.0 + log(refpointsover[i]));
520  constant[*nreturned] = refpointsover[i];
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));
530  }
531 
532  ++(*nreturned);
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 
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 */
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 */
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 */
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}*/
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 }
SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
static SCIP_DECL_EXPRMONOTONICITY(monotonicityEntropy)
Definition: expr_entropy.c:598
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
static SCIP_DECL_EXPRFREEDATA(freedataEntropy)
Definition: expr_entropy.c:290
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3798
static SCIP_DECL_EXPREVAL(evalEntropy)
Definition: expr_entropy.c:325
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:464
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:525
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
static SCIP_RETCODE reverseProp(SCIP *scip, SCIP_INTERVAL exprinterval, SCIP_INTERVAL childinterval, SCIP_INTERVAL *interval)
Definition: expr_entropy.c:103
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_EXPRCURVATURE(curvatureEntropy)
Definition: expr_entropy.c:576
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
Definition: expr.c:398
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:87
handler for -x*log(x) expressions
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:44
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_EXPRSIMPLIFY(simplifyEntropy)
Definition: expr_entropy.c:233
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:442
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:3954
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:431
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1399
static SCIP_DECL_EXPRREVERSEPROP(reversepropEntropy)
Definition: expr_entropy.c:540
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:859
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_Real SCIPepsilon(SCIP *scip)
static SCIP_DECL_EXPRINTEVAL(intevalEntropy)
Definition: expr_entropy.c:383
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3831
static SCIP_DECL_EXPRHASH(hashEntropy)
Definition: expr_entropy.c:561
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
SCIP_Real inf
Definition: intervalarith.h:46
static SCIP_Real reversePropBinarySearch(SCIP *scip, SCIP_Real xmin, SCIP_Real xmax, SCIP_Bool increasing, SCIP_Real targetval)
Definition: expr_entropy.c:52
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3872
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:964
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
static SCIP_DECL_EXPRINTEGRALITY(integralityEntropy)
Definition: expr_entropy.c:627
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1432
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
#define REALABS(x)
Definition: def.h:201
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
static SCIP_DECL_EXPRBWDIFF(bwdiffEntropy)
Definition: expr_entropy.c:356
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Real sup
Definition: intervalarith.h:47
SCIP_RETCODE SCIPcreateExprValue(SCIP *scip, SCIP_EXPR **expr, SCIP_Real value, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_value.c:261
SCIP_Bool SCIPisExprEntropy(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_entropy.c:701
void SCIPintervalEntropy(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:359
SCIP_RETCODE SCIPcreateExprEntropy(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_entropy.c:674
#define SCIP_INTERVAL_INFINITY
Definition: def.h:199
#define SCIP_Bool
Definition: def.h:84
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:131
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:420
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
#define EXPRHDLR_PRECEDENCE
Definition: expr_entropy.c:37
#define MAX(x, y)
Definition: tclique_def.h:83
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:501
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:1370
static SCIP_DECL_EXPRPARSE(parseEntropy)
Definition: expr_entropy.c:300
static SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy)
Definition: expr_entropy.c:224
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:183
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3821
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:372
constant value expression handler
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:409
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3846
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
#define SCIP_Real
Definition: def.h:177
static SCIP_DECL_EXPRESTIMATE(estimateEntropy)
Definition: expr_entropy.c:403
static SCIP_DECL_EXPRCOPYDATA(copydataEntropy)
Definition: expr_entropy.c:278
#define SCIP_INVALID
Definition: def.h:197
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:285
#define EXPRHDLR_HASHKEY
Definition: expr_entropy.c:38
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:512
static SCIP_DECL_EXPRINITESTIMATES(initestimatesEntropy)
Definition: expr_entropy.c:477
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define EXPRHDLR_NAME
Definition: expr_entropy.c:35
SCIP_RETCODE SCIPincludeExprhdlrEntropy(SCIP *scip)
Definition: expr_entropy.c:642
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:814
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:490
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:479
#define EXPRHDLR_DESC
Definition: expr_entropy.c:36