Scippy

SCIP

Solving Constraint Integer Programs

intervalarith.h
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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file intervalarith.h
17  * @ingroup PUBLICCOREAPI
18  * @brief interval arithmetics for provable bounds
19  * @author Tobias Achterberg
20  * @author Stefan Vigerske
21  * @author Kati Wolter
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #ifndef __SCIP_INTERVALARITH_H__
27 #define __SCIP_INTERVALARITH_H__
28 
29 
30 #include "scip/def.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 /**@defgroup PublicIntervalArithMethods Interval Arithmetics
37  * @ingroup MiscellaneousMethods
38  * @brief methods for interval arithmetics
39  *
40  * @{
41  */
42 
43 /** interval given by infimum and supremum */
45 {
46  SCIP_Real inf; /**< infimum (lower bound) of interval */
47  SCIP_Real sup; /**< supremum (upper bound) of interval */
48 };
50 
51 /** rounding mode of floating point operations (upwards, downwards, nearest, ...)
52  *
53  * exact values depend on machine and compiler
54  */
55 typedef int SCIP_ROUNDMODE;
56 
57 /*
58  * Interval arithmetic operations
59  */
60 
61 /** returns whether rounding mode control is available */
62 SCIP_EXPORT
64  void
65  );
66 
67 /** sets rounding mode of floating point operations */
68 SCIP_EXPORT
70  SCIP_ROUNDMODE roundmode /**< rounding mode to activate */
71  );
72 
73 /** gets current rounding mode of floating point operations */
74 SCIP_EXPORT
75 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(
76  void
77  );
78 
79 /** sets rounding mode of floating point operations to downwards rounding */
80 SCIP_EXPORT
82  void
83  );
84 
85 /** sets rounding mode of floating point operations to upwards rounding */
86 SCIP_EXPORT
88  void
89  );
90 
91 /** sets rounding mode of floating point operations to nearest rounding */
92 SCIP_EXPORT
94  void
95  );
96 
97 /** sets rounding mode of floating point operations to towards zero rounding */
98 SCIP_EXPORT
100  void
101  );
102 
103 /** negates a number in a way that the compiler does not optimize it away */
104 SCIP_EXPORT
106  SCIP_Real x /**< number to negate */
107  );
108 
109 /** returns infimum of interval */
110 SCIP_EXPORT
112  SCIP_INTERVAL interval /**< interval */
113  );
114 
115 /** returns supremum of interval */
116 SCIP_EXPORT
118  SCIP_INTERVAL interval /**< interval */
119  );
120 
121 /** stores given value as interval */
122 SCIP_EXPORT
123 void SCIPintervalSet(
124  SCIP_INTERVAL* resultant, /**< interval to store value into */
125  SCIP_Real value /**< value to store */
126  );
127 
128 /** stores given infimum and supremum as interval */
129 SCIP_EXPORT
131  SCIP_INTERVAL* resultant, /**< interval to store value into */
132  SCIP_Real inf, /**< value to store as infimum */
133  SCIP_Real sup /**< value to store as supremum */
134  );
135 
136 /** sets interval to empty interval, which will be [1.0, -1.0] */
137 SCIP_EXPORT
139  SCIP_INTERVAL* resultant /**< resultant interval of operation */
140  );
141 
142 /** indicates whether interval is empty, i.e., whether inf > sup */
143 SCIP_EXPORT
145  SCIP_Real infinity, /**< value for infinity */
146  SCIP_INTERVAL operand /**< operand of operation */
147  );
148 
149 /** sets interval to entire [-infinity, +infinity] */
150 SCIP_EXPORT
152  SCIP_Real infinity, /**< value for infinity */
153  SCIP_INTERVAL* resultant /**< resultant interval of operation */
154  );
155 
156 /** indicates whether interval is entire, i.e., whether inf &le; -infinity and sup &ge; infinity */
157 SCIP_EXPORT
159  SCIP_Real infinity, /**< value for infinity */
160  SCIP_INTERVAL operand /**< operand of operation */
161  );
162 
163 /** indicates whether interval is positive infinity, i.e., [infinity, infinity] */
164 SCIP_EXPORT
166  SCIP_Real infinity, /**< value for infinity */
167  SCIP_INTERVAL operand /**< operand of operation */
168  );
169 
170 /** indicates whether interval is negative infinity, i.e., [-infinity, -infinity] */
171 SCIP_EXPORT
173  SCIP_Real infinity, /**< value for infinity */
174  SCIP_INTERVAL operand /**< operand of operation */
175  );
176 
177 #ifdef NDEBUG
178 
179 /* In optimized mode, some function calls are overwritten by defines to reduce the number of function calls and
180  * speed up the algorithms.
181  * With SCIPintervalSetBounds we need to be a bit careful, since i and s could use resultant->inf and resultant->sup,
182  * e.g., SCIPintervalSetBounds(&resultant, -resultant->sup, -resultant->inf).
183  * So we need to make sure that we first evaluate both terms before setting resultant.
184  */
185 
186 #define SCIPintervalGetInf(interval) (interval).inf
187 #define SCIPintervalGetSup(interval) (interval).sup
188 #define SCIPintervalSet(resultant, value) do { (resultant)->inf = (value); (resultant)->sup = (resultant)->inf; } while( FALSE )
189 #define SCIPintervalSetBounds(resultant, i, s) do { SCIP_Real scipintervaltemp; scipintervaltemp = (s); (resultant)->inf = (i); (resultant)->sup = scipintervaltemp; } while( FALSE )
190 #define SCIPintervalSetEmpty(resultant) do { (resultant)->inf = 1.0; (resultant)->sup = -1.0; } while( FALSE )
191 #define SCIPintervalSetEntire(infinity, resultant) do { (resultant)->inf = -(infinity); (resultant)->sup = (infinity); } while( FALSE )
192 #define SCIPintervalIsEmpty(infinity, operand) ( (operand).inf > -(infinity) && (operand).sup < (infinity) && (operand).sup < (operand).inf )
193 #define SCIPintervalIsEntire(infinity, operand) ( (operand).inf <= -(infinity) && (operand).sup >= (infinity) )
194 #define SCIPintervalIsPositiveInfinity(infinity, operand) ( (operand).inf >= (infinity) && (operand).sup >= (operand).inf )
195 #define SCIPintervalIsNegativeInfinity(infinity, operand) ( (operand).sup <= -(infinity) && (operand).sup >= (operand).inf )
196 
197 #endif
198 
199 /** indicates whether operand1 is contained in operand2 */
200 SCIP_EXPORT
202  SCIP_Real infinity, /**< value for infinity */
203  SCIP_INTERVAL operand1, /**< first operand of operation */
204  SCIP_INTERVAL operand2 /**< second operand of operation */
205  );
206 
207 /** indicates whether operand1 and operand2 are disjoint */
208 SCIP_EXPORT
210  SCIP_INTERVAL operand1, /**< first operand of operation */
211  SCIP_INTERVAL operand2 /**< second operand of operation */
212  );
213 
214 /** indicates whether operand1 and operand2 are disjoint with epsilon tolerance
215  *
216  * Returns whether minimal (relative) distance of intervals is larger than epsilon.
217  * Same as `SCIPintervalIsEmpty(SCIPintervalIntersectEps(operand1, operand2))`.
218  */
219 SCIP_EXPORT
221  SCIP_Real eps, /**< epsilon */
222  SCIP_INTERVAL operand1, /**< first operand of operation */
223  SCIP_INTERVAL operand2 /**< second operand of operation */
224  );
225 
226 /** intersection of two intervals */
227 SCIP_EXPORT
229  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
230  SCIP_INTERVAL operand1, /**< first operand of operation */
231  SCIP_INTERVAL operand2 /**< second operand of operation */
232  );
233 
234 /** intersection of two intervals with epsilon tolerance
235  *
236  * If intersection of operand1 and operand2 is empty, but minimal (relative) distance of intervals
237  * is at most epsilon, then set resultant to singleton containing the point in operand1
238  * that is closest to operand2, i.e.,
239  * - `resultant = { operand1.sup }`, if `operand1.sup` < `operand2.inf` and `reldiff(operand2.inf,operand1.sup)` &le; eps
240  * - `resultant = { operand1.inf }`, if `operand1.inf` > `operand2.sup` and `reldiff(operand1.inf,operand2.sup)` &le; eps
241  * - `resultant` = intersection of `operand1` and `operand2`, otherwise
242  */
243 SCIP_EXPORT
245  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
246  SCIP_Real eps, /**< epsilon */
247  SCIP_INTERVAL operand1, /**< first operand of operation */
248  SCIP_INTERVAL operand2 /**< second operand of operation */
249  );
250 
251 /** interval enclosure of the union of two intervals */
252 SCIP_EXPORT
253 void SCIPintervalUnify(
254  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
255  SCIP_INTERVAL operand1, /**< first operand of operation */
256  SCIP_INTERVAL operand2 /**< second operand of operation */
257  );
258 
259 /** adds operand1 and operand2 and stores infimum of result in infimum of resultant */
260 SCIP_EXPORT
261 void SCIPintervalAddInf(
262  SCIP_Real infinity, /**< value for infinity */
263  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
264  SCIP_INTERVAL operand1, /**< first operand of operation */
265  SCIP_INTERVAL operand2 /**< second operand of operation */
266  );
267 
268 /** adds operand1 and operand2 and stores supremum of result in supremum of resultant */
269 SCIP_EXPORT
270 void SCIPintervalAddSup(
271  SCIP_Real infinity, /**< value for infinity */
272  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
273  SCIP_INTERVAL operand1, /**< first operand of operation */
274  SCIP_INTERVAL operand2 /**< second operand of operation */
275  );
276 
277 /** adds operand1 and operand2 and stores result in resultant */
278 SCIP_EXPORT
279 void SCIPintervalAdd(
280  SCIP_Real infinity, /**< value for infinity */
281  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
282  SCIP_INTERVAL operand1, /**< first operand of operation */
283  SCIP_INTERVAL operand2 /**< second operand of operation */
284  );
285 
286 /** adds operand1 and scalar operand2 and stores result in resultant */
287 SCIP_EXPORT
289  SCIP_Real infinity, /**< value for infinity */
290  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
291  SCIP_INTERVAL operand1, /**< first operand of operation */
292  SCIP_Real operand2 /**< second operand of operation */
293  );
294 
295 /** adds vector operand1 and vector operand2 and stores result in vector resultant */
296 SCIP_EXPORT
298  SCIP_Real infinity, /**< value for infinity */
299  SCIP_INTERVAL* resultant, /**< array of resultant intervals of operation */
300  int length, /**< length of arrays */
301  SCIP_INTERVAL* operand1, /**< array of first operands of operation */
302  SCIP_INTERVAL* operand2 /**< array of second operands of operation */
303  );
304 
305 /** subtracts operand2 from operand1 and stores result in resultant */
306 SCIP_EXPORT
307 void SCIPintervalSub(
308  SCIP_Real infinity, /**< value for infinity */
309  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
310  SCIP_INTERVAL operand1, /**< first operand of operation */
311  SCIP_INTERVAL operand2 /**< second operand of operation */
312  );
313 
314 /** subtracts scalar operand2 from operand1 and stores result in resultant */
315 SCIP_EXPORT
317  SCIP_Real infinity, /**< value for infinity */
318  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
319  SCIP_INTERVAL operand1, /**< first operand of operation */
320  SCIP_Real operand2 /**< second operand of operation */
321  );
322 
323 /** multiplies operand1 with operand2 and stores infimum of result in infimum of resultant */
324 SCIP_EXPORT
325 void SCIPintervalMulInf(
326  SCIP_Real infinity, /**< value for infinity */
327  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
328  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
329  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
330  );
331 
332 /** multiplies operand1 with operand2 and stores supremum of result in supremum of resultant */
333 SCIP_EXPORT
334 void SCIPintervalMulSup(
335  SCIP_Real infinity, /**< value for infinity */
336  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
337  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
338  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
339  );
340 
341 /** multiplies operand1 with operand2 and stores result in resultant */
342 SCIP_EXPORT
343 void SCIPintervalMul(
344  SCIP_Real infinity, /**< value for infinity */
345  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
346  SCIP_INTERVAL operand1, /**< first operand of operation */
347  SCIP_INTERVAL operand2 /**< second operand of operation */
348  );
349 
350 /** multiplies operand1 with scalar operand2 and stores infimum of result in infimum of resultant */
351 SCIP_EXPORT
353  SCIP_Real infinity, /**< value for infinity */
354  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
355  SCIP_INTERVAL operand1, /**< first operand of operation */
356  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
357  );
358 
359 /** multiplies operand1 with scalar operand2 and stores supremum of result in supremum of resultant */
360 SCIP_EXPORT
362  SCIP_Real infinity, /**< value for infinity */
363  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
364  SCIP_INTERVAL operand1, /**< first operand of operation */
365  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
366  );
367 
368 /** multiplies operand1 with scalar operand2 and stores result in resultant */
369 SCIP_EXPORT
371  SCIP_Real infinity, /**< value for infinity */
372  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
373  SCIP_INTERVAL operand1, /**< first operand of operation */
374  SCIP_Real operand2 /**< second operand of operation */
375  );
376 
377 /** divides operand1 by operand2 and stores result in resultant */
378 SCIP_EXPORT
379 void SCIPintervalDiv(
380  SCIP_Real infinity, /**< value for infinity */
381  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
382  SCIP_INTERVAL operand1, /**< first operand of operation */
383  SCIP_INTERVAL operand2 /**< second operand of operation */
384  );
385 
386 /** divides operand1 by scalar operand2 and stores result in resultant */
387 SCIP_EXPORT
389  SCIP_Real infinity, /**< value for infinity */
390  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
391  SCIP_INTERVAL operand1, /**< first operand of operation */
392  SCIP_Real operand2 /**< second operand of operation */
393  );
394 
395 /** computes the scalar product of two vectors of intervals and stores result in resultant */
396 SCIP_EXPORT
398  SCIP_Real infinity, /**< value for infinity */
399  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
400  int length, /**< length of vectors */
401  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
402  SCIP_INTERVAL* operand2 /**< second vector as array of intervals */
403  );
404 
405 /** computes the scalar product of a vector of intervals and a vector of scalars and stores infimum of result in infimum of resultant */
406 SCIP_EXPORT
408  SCIP_Real infinity, /**< value for infinity */
409  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
410  int length, /**< length of vectors */
411  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
412  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
413  );
414 
415 /** computes the scalar product of a vector of intervals and a vector of scalars and stores supremum of result in supremum of resultant */
416 SCIP_EXPORT
418  SCIP_Real infinity, /**< value for infinity */
419  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
420  int length, /**< length of vectors */
421  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
422  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
423  );
424 
425 /** computes the scalar product of a vector of intervals and a vector of scalars and stores result in resultant */
426 SCIP_EXPORT
428  SCIP_Real infinity, /**< value for infinity */
429  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
430  int length, /**< length of vectors */
431  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
432  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
433  );
434 
435 /** squares operand and stores result in resultant */
436 SCIP_EXPORT
437 void SCIPintervalSquare(
438  SCIP_Real infinity, /**< value for infinity */
439  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
440  SCIP_INTERVAL operand /**< operand of operation */
441  );
442 
443 /** stores (positive part of) square root of operand in resultant
444  * @attention we assume a correctly rounded sqrt(double) function when rounding is to nearest
445  */
446 SCIP_EXPORT
448  SCIP_Real infinity, /**< value for infinity */
449  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
450  SCIP_INTERVAL operand /**< operand of operation */
451  );
452 
453 /** stores operand1 to the power of operand2 in resultant
454  *
455  * uses SCIPintervalPowerScalar if operand2 is a scalar, otherwise computes exp(op2*log(op1))
456  */
457 SCIP_EXPORT
458 void SCIPintervalPower(
459  SCIP_Real infinity, /**< value for infinity */
460  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
461  SCIP_INTERVAL operand1, /**< first operand of operation */
462  SCIP_INTERVAL operand2 /**< second operand of operation */
463  );
464 
465 /** stores operand1 to the power of the scalar operand2 in resultant
466  * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
467  */
468 SCIP_EXPORT
470  SCIP_Real infinity, /**< value for infinity */
471  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
472  SCIP_INTERVAL operand1, /**< first operand of operation */
473  SCIP_Real operand2 /**< second operand of operation */
474  );
475 
476 /** stores bounds on the power of a scalar operand1 to a scalar operand2 in resultant
477  *
478  * Both operands need to be finite numbers.
479  * Needs to have operand1 &ge; 0 or operand2 integer and needs to have operand2 &ge; 0 if operand1 = 0.
480  * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
481  */
482 SCIP_EXPORT
484  SCIP_INTERVAL* resultant, /**< resultant of operation */
485  SCIP_Real operand1, /**< first operand of operation */
486  SCIP_Real operand2 /**< second operand of operation */
487  );
488 
489 /** computes lower bound on power of a scalar operand1 to an integer operand2
490  *
491  * Both operands need to be finite numbers.
492  * Needs to have operand1 &ge; 0 and need to have operand2 &ge; 0 if operand1 = 0.
493  */
494 SCIP_EXPORT
496  SCIP_Real operand1, /**< first operand of operation */
497  int operand2 /**< second operand of operation */
498  );
499 
500 /** computes upper bound on power of a scalar operand1 to an integer operand2
501  *
502  * Both operands need to be finite numbers.
503  * Needs to have operand1 &ge; 0 and needs to have operand2 &ge; 0 if operand1 = 0.
504  */
505 SCIP_EXPORT
507  SCIP_Real operand1, /**< first operand of operation */
508  int operand2 /**< second operand of operation */
509  );
510 
511 /** computes bounds on power of a scalar operand1 to an integer operand2
512  *
513  * Both operands need to be finite numbers.
514  * Needs to have operand1 &ge; 0 and needs to have operand2 &ge; 0 if operand1 = 0.
515  */
516 SCIP_EXPORT
518  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
519  SCIP_Real operand1, /**< first operand of operation */
520  int operand2 /**< second operand of operation */
521  );
522 
523 /** given an interval for the image of a power operation, computes an interval for the origin
524  *
525  * That is, for \f$y = x^p\f$ with the exponent \f$p\f$ a given scalar and \f$y\f$ = `image` a given interval,
526  * computes \f$x \subseteq \text{basedomain}\f$ such that \f$y \in x^p\f$ and such that for all \f$z \in \text{basedomain} \setminus x: z^p \not \in y\f$.
527  */
528 SCIP_EXPORT
530  SCIP_Real infinity, /**< value for infinity */
531  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
532  SCIP_INTERVAL basedomain, /**< domain of base */
533  SCIP_Real exponent, /**< exponent */
534  SCIP_INTERVAL image /**< interval image of power */
535  );
536 
537 /** stores operand1 to the signed power of the scalar positive operand2 in resultant
538  *
539  * The signed power of x w.r.t. an exponent n &ge; 0 is given as \f$\mathrm{sign}(x) |x|^n\f$.
540  *
541  * @attention we assume correctly rounded sqrt(double) and pow(double) functions when rounding is to nearest
542  */
543 SCIP_EXPORT
545  SCIP_Real infinity, /**< value for infinity */
546  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
547  SCIP_INTERVAL operand1, /**< first operand of operation */
548  SCIP_Real operand2 /**< second operand of operation */
549  );
550 
551 /** computes the reciprocal of an interval
552  */
553 SCIP_EXPORT
555  SCIP_Real infinity, /**< value for infinity */
556  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
557  SCIP_INTERVAL operand /**< operand of operation */
558  );
559 
560 /** stores exponential of operand in resultant
561  * @attention we assume a correctly rounded exp(double) function when rounding is to nearest
562  */
563 SCIP_EXPORT
564 void SCIPintervalExp(
565  SCIP_Real infinity, /**< value for infinity */
566  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
567  SCIP_INTERVAL operand /**< operand of operation */
568  );
569 
570 /** stores natural logarithm of operand in resultant
571  * @attention we assume a correctly rounded log(double) function when rounding is to nearest
572  */
573 SCIP_EXPORT
574 void SCIPintervalLog(
575  SCIP_Real infinity, /**< value for infinity */
576  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
577  SCIP_INTERVAL operand /**< operand of operation */
578  );
579 
580 /** stores minimum of operands in resultant */
581 SCIP_EXPORT
582 void SCIPintervalMin(
583  SCIP_Real infinity, /**< value for infinity */
584  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
585  SCIP_INTERVAL operand1, /**< first operand of operation */
586  SCIP_INTERVAL operand2 /**< second operand of operation */
587  );
588 
589 /** stores maximum of operands in resultant */
590 SCIP_EXPORT
591 void SCIPintervalMax(
592  SCIP_Real infinity, /**< value for infinity */
593  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
594  SCIP_INTERVAL operand1, /**< first operand of operation */
595  SCIP_INTERVAL operand2 /**< second operand of operation */
596  );
597 
598 /** stores absolute value of operand in resultant */
599 SCIP_EXPORT
600 void SCIPintervalAbs(
601  SCIP_Real infinity, /**< value for infinity */
602  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
603  SCIP_INTERVAL operand /**< operand of operation */
604  );
605 
606 /** stores sine value of operand in resultant */
607 SCIP_EXPORT
608 void SCIPintervalSin(
609  SCIP_Real infinity, /**< value for infinity */
610  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
611  SCIP_INTERVAL operand /**< operand of operation */
612  );
613 
614 /** stores cosine value of operand in resultant */
615 SCIP_EXPORT
616 void SCIPintervalCos(
617  SCIP_Real infinity, /**< value for infinity */
618  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
619  SCIP_INTERVAL operand /**< operand of operation */
620  );
621 
622 /** stores sign of operand in resultant */
623 SCIP_EXPORT
624 void SCIPintervalSign(
625  SCIP_Real infinity, /**< value for infinity */
626  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
627  SCIP_INTERVAL operand /**< operand of operation */
628  );
629 
630 /** stores entropy of operand in resultant */
631 SCIP_EXPORT
633  SCIP_Real infinity, /**< value for infinity */
634  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
635  SCIP_INTERVAL operand /**< operand of operation */
636  );
637 
638 /** computes exact upper bound on \f$ a x^2 + b x \f$ for x in [xlb, xub], b an interval, and a scalar
639  *
640  * Uses Algorithm 2.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008).
641  */
642 SCIP_EXPORT
644  SCIP_Real infinity, /**< value for infinity */
645  SCIP_Real a, /**< coefficient of x^2 */
646  SCIP_INTERVAL b_, /**< coefficient of x */
647  SCIP_INTERVAL x /**< range of x */
648  );
649 
650 /** stores range of quadratic term in resultant
651  *
652  * given scalar a and intervals b and x, computes interval for \f$ a x^2 + b x \f$ */
653 SCIP_EXPORT
654 void SCIPintervalQuad(
655  SCIP_Real infinity, /**< value for infinity */
656  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
657  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
658  SCIP_INTERVAL lincoeff, /**< coefficient of x */
659  SCIP_INTERVAL xrng /**< range of x */
660  );
661 
662 
663 /** computes interval with positive solutions of a quadratic equation with interval coefficients
664  *
665  * Given intervals a, b, and c, this function computes an interval that contains all positive solutions of \f$ a x^2 + b x \in c\f$ within xbnds.
666  */
667 SCIP_EXPORT
669  SCIP_Real infinity, /**< value for infinity */
670  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
671  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
672  SCIP_INTERVAL lincoeff, /**< coefficient of x */
673  SCIP_INTERVAL rhs, /**< right hand side of equation */
674  SCIP_INTERVAL xbnds /**< bounds on x */
675  );
676 
677 /** computes interval with negative solutions of a quadratic equation with interval coefficients
678  *
679  * Given intervals a, b, and c, this function computes an interval that contains all negative solutions of \f$ a x^2 + b x \in c\f$ within xbnds.
680  */
681 SCIP_EXPORT
683  SCIP_Real infinity, /**< value for infinity */
684  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
685  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
686  SCIP_INTERVAL lincoeff, /**< coefficient of x */
687  SCIP_INTERVAL rhs, /**< right hand side of equation */
688  SCIP_INTERVAL xbnds /**< bounds on x */
689  );
690 
691 /** computes positive solutions of a quadratic equation with scalar coefficients
692  *
693  * Givens scalar a, b, and c, this function computes an interval that contains all positive solutions of \f$ a x^2 + b x \geq c\f$ within xbnds.
694  * Implements Algorithm 3.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008).
695  */
696 SCIP_EXPORT
698  SCIP_Real infinity, /**< value for infinity */
699  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
700  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
701  SCIP_Real lincoeff, /**< coefficient of x */
702  SCIP_Real rhs, /**< right hand side of equation */
703  SCIP_INTERVAL xbnds /**< bounds on x */
704  );
705 
706 /** solves a quadratic equation with interval coefficients
707  *
708  * Given intervals a, b and c, this function computes an interval that contains all solutions of \f$ a x^2 + b x \in c\f$ within xbnds.
709  */
710 SCIP_EXPORT
712  SCIP_Real infinity, /**< value for infinity */
713  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
714  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
715  SCIP_INTERVAL lincoeff, /**< coefficient of x */
716  SCIP_INTERVAL rhs, /**< right hand side of equation */
717  SCIP_INTERVAL xbnds /**< bounds on x */
718  );
719 
720 /** stores range of bivariate quadratic term in resultant
721  *
722  * Given scalars \f$a_x\f$, \f$a_y\f$, \f$a_{xy}\f$, \f$b_x\f$, and \f$b_y\f$ and intervals for \f$x\f$ and \f$y\f$,
723  * computes interval for \f$ a_x x^2 + a_y y^2 + a_{xy} x y + b_x x + b_y y \f$.
724  *
725  * \attention The operations are not applied rounding-safe here!
726  */
727 SCIP_EXPORT
729  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
730  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
731  SCIP_Real ax, /**< square coefficient of x */
732  SCIP_Real ay, /**< square coefficient of y */
733  SCIP_Real axy, /**< bilinear coefficients */
734  SCIP_Real bx, /**< linear coefficient of x */
735  SCIP_Real by, /**< linear coefficient of y */
736  SCIP_INTERVAL xbnds, /**< bounds on x */
737  SCIP_INTERVAL ybnds /**< bounds on y */
738  );
739 
740 /** solves a bivariate quadratic equation for the first variable
741  *
742  * Given scalars \f$a_x\f$, \f$a_y\f$, \f$a_{xy}\f$, \f$b_x\f$ and \f$b_y\f$, and intervals for \f$x\f$, \f$y\f$, and rhs,
743  * computes \f$ \{ x \in \mathbf{x} : \exists y \in \mathbf{y} : a_x x^2 + a_y y^2 + a_{xy} x y + b_x x + b_y y \in \mathbf{\mbox{rhs}} \} \f$.
744  *
745  * \attention the operations are not applied rounding-safe here
746  */
747 SCIP_EXPORT
749  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
750  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
751  SCIP_Real ax, /**< square coefficient of x */
752  SCIP_Real ay, /**< square coefficient of y */
753  SCIP_Real axy, /**< bilinear coefficients */
754  SCIP_Real bx, /**< linear coefficient of x */
755  SCIP_Real by, /**< linear coefficient of y */
756  SCIP_INTERVAL rhs, /**< right-hand-side of equation */
757  SCIP_INTERVAL xbnds, /**< bounds on x */
758  SCIP_INTERVAL ybnds /**< bounds on y */
759  );
760 
761 /** propagates a weighted sum of intervals in a given interval
762  *
763  * Given \f$\text{constant} + \sum_i \text{weights}_i \text{operands}_i \in \text{rhs}\f$,
764  * computes possibly tighter interval for each term.
765  *
766  * @attention Valid values are returned in resultants only if any tightening has been found and no empty interval, that is, function returns with non-zero and `*infeasible` = FALSE.
767  *
768  * @return Number of terms for which resulting interval is smaller than operand interval.
769  */
770 SCIP_EXPORT
772  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
773  int noperands, /**< number of operands (intervals) to propagate */
774  SCIP_INTERVAL* operands, /**< intervals to propagate */
775  SCIP_Real* weights, /**< weights of intervals in sum */
776  SCIP_Real constant, /**< constant in sum */
777  SCIP_INTERVAL rhs, /**< right-hand-side interval */
778  SCIP_INTERVAL* resultants, /**< array to store propagated intervals, if any reduction is found at all (check return code and *infeasible) */
779  SCIP_Bool* infeasible /**< buffer to store if propagation produced empty interval */
780  );
781 
782 /** @} */
783 
784 #ifdef __cplusplus
785 }
786 #endif
787 
788 #endif
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
void SCIPintervalReciprocal(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
int SCIP_ROUNDMODE
Definition: intervalarith.h:55
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalPowerScalarIntegerSup(SCIP_Real operand1, int operand2)
#define infinity
Definition: gastrans.c:71
SCIP_Bool SCIPintervalIsPositiveInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalPowerScalarScalar(SCIP_INTERVAL *resultant, SCIP_Real operand1, SCIP_Real operand2)
void SCIPintervalMulSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng)
SCIP_Bool SCIPintervalIsNegativeInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real SCIPintervalPowerScalarIntegerInf(SCIP_Real operand1, int operand2)
void SCIPintervalScalprodScalarsInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_Real lincoeff, SCIP_Real rhs, SCIP_INTERVAL xbnds)
void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
void SCIPintervalAddSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalMulInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_VAR ** x
Definition: circlepacking.c:54
real eps
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_Bool SCIPintervalAreDisjoint(SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real inf
Definition: intervalarith.h:46
void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSolveBivariateQuadExpressionAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds)
void SCIPintervalScalprod(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
void SCIPintervalScalprodScalarsSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_Real SCIPintervalNegateReal(SCIP_Real x)
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalMulScalarSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
int SCIPintervalPropagateWeightedSum(SCIP_Real infinity, int noperands, SCIP_INTERVAL *operands, SCIP_Real *weights, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_INTERVAL *resultants, SCIP_Bool *infeasible)
SCIP_Real sup
Definition: intervalarith.h:47
void SCIPintervalEntropy(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalSolveUnivariateQuadExpressionPositive(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalSetRoundingModeDownwards(void)
void SCIPintervalSetRoundingModeToNearest(void)
#define SCIP_Bool
Definition: def.h:84
void SCIPintervalAddInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalPower(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
void SCIPintervalPowerScalarInteger(SCIP_INTERVAL *resultant, SCIP_Real operand1, int operand2)
SCIP_Bool SCIPintervalAreDisjointEps(SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalQuadBivar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds)
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalSetRoundingModeTowardsZero(void)
void SCIPintervalSignPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalMulScalarInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetRoundingModeUpwards(void)
SCIP_VAR * a
Definition: circlepacking.c:57
SCIP_Bool SCIPintervalHasRoundingControl(void)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
#define SCIP_Real
Definition: def.h:177
void SCIPintervalAddVectors(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
common defines and data types used in all packages of SCIP
void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSolveUnivariateQuadExpressionNegative(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)