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 2002-2022 Zuse Institute Berlin */
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
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
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  {
154  SCIPintervalIntersect(interval, *interval, childinterval);
155  return SCIP_OKAY;
156  }
157 
158  childinf = MAX(0.0, SCIPintervalGetInf(childinterval)); /*lint !e666*/
159  childsup = SCIPintervalGetSup(childinterval);
160  extremum = exp(-1.0);
161  boundinf = SCIP_INVALID;
162  boundsup = SCIP_INVALID;
163 
164  /*
165  * check whether lower bound of child can be improved
166  */
167  SCIPintervalSet(&tmp, childinf);
169 
170  /* entropy(childinf) < intersection.inf -> consider [childinf, MIN(childsup, extremum)] */
171  if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) )
172  {
173  boundinf = reversePropBinarySearch(scip, childinf, MIN(extremum, childsup), TRUE,
174  SCIPintervalGetInf(intersection));
175  }
176  /* entropy(childinf) > intersection.sup -> consider [MAX(childinf,extremum), childsup] */
177  else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) )
178  {
179  boundinf = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE,
180  SCIPintervalGetSup(intersection));
181  }
182  /* using a strict greater-than here because we expect a tightening because we saw an at-least-epsilon-potential above */
183  assert(boundinf == SCIP_INVALID || boundinf > childinf); /*lint !e777*/
184 
185  /*
186  * check whether upper bound of child can be improved
187  */
188  if( childsup < SCIP_INTERVAL_INFINITY )
189  {
190  SCIPintervalSet(&tmp, childsup);
192  }
193  else
194  SCIPintervalSetBounds(&tmp, -SCIP_INTERVAL_INFINITY, -SCIP_INTERVAL_INFINITY); /* entropy(inf) = -inf */
195 
196  /* entropy(childsup) < intersection.inf -> consider [MAX(childinf,extremum), childsup] */
197  if( SCIPintervalGetInf(intersection) > -SCIP_INTERVAL_INFINITY && SCIPintervalGetSup(tmp) - SCIPintervalGetInf(intersection) < -SCIPepsilon(scip) )
198  {
199  boundsup = reversePropBinarySearch(scip, MAX(childinf, extremum), childsup, FALSE,
200  SCIPintervalGetInf(intersection));
201  }
202  /* entropy(childsup) > intersection.sup -> consider [childinf, MIN(childsup,extremum)] */
203  else if( SCIPintervalGetSup(intersection) < SCIP_INTERVAL_INFINITY && SCIPintervalGetInf(tmp) - SCIPintervalGetSup(intersection) > SCIPepsilon(scip) )
204  {
205  boundsup = reversePropBinarySearch(scip, childinf, MIN(childsup, extremum), TRUE,
206  SCIPintervalGetSup(intersection));
207  }
208  /* using a strict smaller-than here because we expect a tightening because we saw an at-least-epsilon-potential above */
209  assert(boundsup == SCIP_INVALID || boundsup < childsup); /*lint !e777*/
210 
211  if( boundinf != SCIP_INVALID ) /*lint !e777*/
212  {
213  childinf = MAX(childinf, boundinf);
214  }
215  if( boundsup != SCIP_INVALID ) /*lint !e777*/
216  {
217  childsup = boundsup;
218  }
219  assert(childinf <= childsup); /* infeasible case has been handled already */
220 
221  /* set the resulting bounds */
222  SCIPintervalSetBounds(interval, childinf, childsup);
223 
224  return SCIP_OKAY;
225 }
226 
227 /*
228  * Callback methods of expression handler
229  */
230 
231 /** expression handler copy callback */
232 static
233 SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy)
234 { /*lint --e{715}*/
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 
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 */
654  SCIP* scip /**< SCIP data structure */
655  )
656 {
657  SCIP_EXPRHDLRDATA* exprhdlrdata;
658  SCIP_EXPRHDLR* exprhdlr;
659 
660  /* create expression handler data */
661  exprhdlrdata = NULL;
662 
663  /* include expression handler */
665  evalEntropy, exprhdlrdata) );
666  assert(exprhdlr != NULL);
667 
668  SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrEntropy, NULL);
669  SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataEntropy, freedataEntropy);
670  SCIPexprhdlrSetSimplify(exprhdlr, simplifyEntropy);
671  SCIPexprhdlrSetParse(exprhdlr, parseEntropy);
672  SCIPexprhdlrSetIntEval(exprhdlr, intevalEntropy);
673  SCIPexprhdlrSetEstimate(exprhdlr, initestimatesEntropy, estimateEntropy);
674  SCIPexprhdlrSetReverseProp(exprhdlr, reversepropEntropy);
675  SCIPexprhdlrSetHash(exprhdlr, hashEntropy);
676  SCIPexprhdlrSetDiff(exprhdlr, bwdiffEntropy, NULL ,NULL);
677  SCIPexprhdlrSetCurvature(exprhdlr, curvatureEntropy);
678  SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityEntropy);
679  SCIPexprhdlrSetIntegrality(exprhdlr, integralityEntropy);
680 
681  return SCIP_OKAY;
682 }
683 
684 /** creates an entropy expression */
686  SCIP* scip, /**< SCIP data structure */
687  SCIP_EXPR** expr, /**< pointer where to store expression */
688  SCIP_EXPR* child, /**< child expression */
689  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
690  void* ownercreatedata /**< data to pass to ownercreate */
691  )
692 {
693  SCIP_EXPRHDLR* exprhdlr;
694  SCIP_EXPRDATA* exprdata;
695 
696  assert(expr != NULL);
697  assert(child != NULL);
698 
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}*/
713  SCIP* scip, /**< SCIP data structure */
714  SCIP_EXPR* expr /**< expression */
715  )
716 { /*lint --e{715}*/
717  assert(expr != NULL);
718 
719  return strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0;
720 }
SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
static SCIP_DECL_EXPRMONOTONICITY(monotonicityEntropy)
Definition: expr_entropy.c:609
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
static SCIP_DECL_EXPRFREEDATA(freedataEntropy)
Definition: expr_entropy.c:299
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
static SCIP_DECL_EXPREVAL(evalEntropy)
Definition: expr_entropy.c:334
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:473
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:534
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:112
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_EXPRCURVATURE(curvatureEntropy)
Definition: expr_entropy.c:587
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPARSE((*parse)))
Definition: expr.c:407
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:96
handler for -x*log(x) expressions
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:53
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_DECL_EXPRSIMPLIFY(simplifyEntropy)
Definition: expr_entropy.c:242
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:451
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:3964
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:440
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1408
static SCIP_DECL_EXPRREVERSEPROP(reversepropEntropy)
Definition: expr_entropy.c:551
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:868
SCIP_VAR ** x
Definition: circlepacking.c:63
SCIP_Real SCIPepsilon(SCIP *scip)
static SCIP_DECL_EXPRINTEVAL(intevalEntropy)
Definition: expr_entropy.c:392
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3841
static SCIP_DECL_EXPRHASH(hashEntropy)
Definition: expr_entropy.c:572
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3818
SCIP_Real inf
Definition: intervalarith.h:55
static SCIP_Real reversePropBinarySearch(SCIP *scip, SCIP_Real xmin, SCIP_Real xmax, SCIP_Bool increasing, SCIP_Real targetval)
Definition: expr_entropy.c:61
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3882
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:973
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:638
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1441
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
#define REALABS(x)
Definition: def.h:210
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
static SCIP_DECL_EXPRBWDIFF(bwdiffEntropy)
Definition: expr_entropy.c:365
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_RETCODE SCIPcreateExprValue(SCIP *scip, SCIP_EXPR **expr, SCIP_Real value, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_value.c:270
SCIP_Bool SCIPisExprEntropy(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_entropy.c:712
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:368
SCIP_RETCODE SCIPcreateExprEntropy(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_entropy.c:685
#define SCIP_INTERVAL_INFINITY
Definition: def.h:208
#define SCIP_Bool
Definition: def.h:93
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:140
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:429
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1416
#define EXPRHDLR_PRECEDENCE
Definition: expr_entropy.c:46
#define MAX(x, y)
Definition: tclique_def.h:92
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRREVERSEPROP((*reverseprop)))
Definition: expr.c:510
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:1379
static SCIP_DECL_EXPRPARSE(parseEntropy)
Definition: expr_entropy.c:309
static SCIP_DECL_EXPRCOPYHDLR(copyhdlrEntropy)
Definition: expr_entropy.c:233
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:192
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3831
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:381
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:418
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3856
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
#define SCIP_Real
Definition: def.h:186
static SCIP_DECL_EXPRESTIMATE(estimateEntropy)
Definition: expr_entropy.c:412
static SCIP_DECL_EXPRCOPYDATA(copydataEntropy)
Definition: expr_entropy.c:287
#define SCIP_INVALID
Definition: def.h:206
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition: expr_value.c:294
#define EXPRHDLR_HASHKEY
Definition: expr_entropy.c:47
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)), SCIP_DECL_EXPRESTIMATE((*estimate)))
Definition: expr.c:521
static SCIP_DECL_EXPRINITESTIMATES(initestimatesEntropy)
Definition: expr_entropy.c:486
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:44
SCIP_RETCODE SCIPincludeExprhdlrEntropy(SCIP *scip)
Definition: expr_entropy.c:653
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:823
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:499
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:488
#define EXPRHDLR_DESC
Definition: expr_entropy.c:45