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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip/intervalarith.h
17  * @ingroup INTERNALAPI
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 /** interval given by infimum and supremum */
38 {
39  SCIP_Real inf; /**< infimum (lower bound) of interval */
40  SCIP_Real sup; /**< supremum (upper bound) of interval */
41 };
43 
44 /** rounding mode of floating point operations (upwards, downwards, nearest, ...)
45  * exact values depend on machine and compiler, so we define a corresponding enum in the header file */
46 typedef int SCIP_ROUNDMODE;
47 
48 /*
49  * Interval arithmetic operations
50  */
51 
52 /** returns whether rounding mode control is available */
55  void
56  );
57 
58 /** sets rounding mode of floating point operations */
61  SCIP_ROUNDMODE roundmode /**< rounding mode to activate */
62  );
63 
64 /** gets current rounding mode of floating point operations */
66 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(
67  void
68  );
69 
70 /** sets rounding mode of floating point operations to downwards rounding */
73  void
74  );
75 
76 /** sets rounding mode of floating point operations to upwards rounding */
79  void
80  );
81 
82 /** sets rounding mode of floating point operations to nearest rounding */
85  void
86  );
87 
88 /** sets rounding mode of floating point operations to towards zero rounding */
91  void
92  );
93 
94 /** negates a number in a way that the compiler does not optimize it away */
97  SCIP_Real x /**< number to negate */
98  );
99 
100 /** returns infimum of interval */
103  SCIP_INTERVAL interval /**< interval */
104  );
105 
106 /** returns supremum of interval */
109  SCIP_INTERVAL interval /**< interval */
110  );
111 
112 /** stores given value as interval */
114 void SCIPintervalSet(
115  SCIP_INTERVAL* resultant, /**< interval to store value into */
116  SCIP_Real value /**< value to store */
117  );
118 
119 /** stores given infimum and supremum as interval */
122  SCIP_INTERVAL* resultant, /**< interval to store value into */
123  SCIP_Real inf, /**< value to store as infimum */
124  SCIP_Real sup /**< value to store as supremum */
125  );
126 
127 /** sets interval to empty interval, which will be [1.0, -1.0] */
130  SCIP_INTERVAL* resultant /**< resultant interval of operation */
131  );
132 
133 /** indicates whether interval is empty, i.e., whether inf > sup */
136  SCIP_Real infinity, /**< value for infinity */
137  SCIP_INTERVAL operand /**< operand of operation */
138  );
139 
140 /** sets interval to entire [-infinity, +infinity] */
143  SCIP_Real infinity, /**< value for infinity */
144  SCIP_INTERVAL* resultant /**< resultant interval of operation */
145  );
146 
147 /** indicates whether interval is entire, i.e., whether inf <= -infinity and sup >= infinity */
150  SCIP_Real infinity, /**< value for infinity */
151  SCIP_INTERVAL operand /**< operand of operation */
152  );
153 
154 /** indicates whether interval is positive infinity, i.e., [infinity, infinity] */
157  SCIP_Real infinity, /**< value for infinity */
158  SCIP_INTERVAL operand /**< operand of operation */
159  );
160 
161 /** indicates whether interval is negative infinity, i.e., [-infinity, -infinity] */
164  SCIP_Real infinity, /**< value for infinity */
165  SCIP_INTERVAL operand /**< operand of operation */
166  );
167 
168 #ifdef NDEBUG
169 
170 /* In optimized mode, some function calls are overwritten by defines to reduce the number of function calls and
171  * speed up the algorithms.
172  * With SCIPintervalSetBounds we need to be a bit careful, since i and s could use resultant->inf and resultant->sup,
173  * e.g., SCIPintervalSetBounds(&resultant, -resultant->sup, -resultant->inf).
174  * So we need to make sure that we first evaluate both terms before setting resultant.
175  */
176 
177 #define SCIPintervalGetInf(interval) (interval).inf
178 #define SCIPintervalGetSup(interval) (interval).sup
179 #define SCIPintervalSet(resultant, value) do { (resultant)->inf = (value); (resultant)->sup = (resultant)->inf; } while( FALSE )
180 #define SCIPintervalSetBounds(resultant, i, s) do { SCIP_Real scipintervaltemp; scipintervaltemp = (s); (resultant)->inf = (i); (resultant)->sup = scipintervaltemp; } while( FALSE )
181 #define SCIPintervalSetEmpty(resultant) do { (resultant)->inf = 1.0; (resultant)->sup = -1.0; } while( FALSE )
182 #define SCIPintervalSetEntire(infinity, resultant) do { (resultant)->inf = -(infinity); (resultant)->sup = (infinity); } while( FALSE )
183 #define SCIPintervalIsEmpty(infinity, operand) ( (operand).inf > -(infinity) && (operand).sup < (infinity) && (operand).sup < (operand).inf )
184 #define SCIPintervalIsEntire(infinity, operand) ( (operand).inf <= -(infinity) && (operand).sup >= (infinity) )
185 #define SCIPintervalIsPositiveInfinity(infinity, operand) ( (operand).inf >= (infinity) && (operand).sup >= (operand).inf )
186 #define SCIPintervalIsNegativeInfinity(infinity, operand) ( (operand).sup <= -(infinity) && (operand).sup >= (operand).inf )
187 
188 #endif
189 
190 /** indicates whether operand1 is contained in operand2 */
193  SCIP_Real infinity, /**< value for infinity */
194  SCIP_INTERVAL operand1, /**< first operand of operation */
195  SCIP_INTERVAL operand2 /**< second operand of operation */
196  );
197 
198 /** indicates whether operand1 and operand2 are disjoint */
201  SCIP_INTERVAL operand1, /**< first operand of operation */
202  SCIP_INTERVAL operand2 /**< second operand of operation */
203  );
204 
205 /** intersection of two intervals */
208  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
209  SCIP_INTERVAL operand1, /**< first operand of operation */
210  SCIP_INTERVAL operand2 /**< second operand of operation */
211  );
212 
213 /** interval enclosure of the union of two intervals */
215 void SCIPintervalUnify(
216  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
217  SCIP_INTERVAL operand1, /**< first operand of operation */
218  SCIP_INTERVAL operand2 /**< second operand of operation */
219  );
220 
221 /** adds operand1 and operand2 and stores infimum of result in infimum of resultant */
223 void SCIPintervalAddInf(
224  SCIP_Real infinity, /**< value for infinity */
225  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
226  SCIP_INTERVAL operand1, /**< first operand of operation */
227  SCIP_INTERVAL operand2 /**< second operand of operation */
228  );
229 
230 /** adds operand1 and operand2 and stores supremum of result in supremum of resultant */
232 void SCIPintervalAddSup(
233  SCIP_Real infinity, /**< value for infinity */
234  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
235  SCIP_INTERVAL operand1, /**< first operand of operation */
236  SCIP_INTERVAL operand2 /**< second operand of operation */
237  );
238 
239 /** adds operand1 and operand2 and stores result in resultant */
241 void SCIPintervalAdd(
242  SCIP_Real infinity, /**< value for infinity */
243  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
244  SCIP_INTERVAL operand1, /**< first operand of operation */
245  SCIP_INTERVAL operand2 /**< second operand of operation */
246  );
247 
248 /** adds operand1 and scalar operand2 and stores result in resultant */
251  SCIP_Real infinity, /**< value for infinity */
252  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
253  SCIP_INTERVAL operand1, /**< first operand of operation */
254  SCIP_Real operand2 /**< second operand of operation */
255  );
256 
257 /** adds vector operand1 and vector operand2 and stores result in vector resultant */
260  SCIP_Real infinity, /**< value for infinity */
261  SCIP_INTERVAL* resultant, /**< array of resultant intervals of operation */
262  int length, /**< length of arrays */
263  SCIP_INTERVAL* operand1, /**< array of first operands of operation */
264  SCIP_INTERVAL* operand2 /**< array of second operands of operation */
265  );
266 
267 /** subtracts operand2 from operand1 and stores result in resultant */
269 void SCIPintervalSub(
270  SCIP_Real infinity, /**< value for infinity */
271  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
272  SCIP_INTERVAL operand1, /**< first operand of operation */
273  SCIP_INTERVAL operand2 /**< second operand of operation */
274  );
275 
276 /** subtracts scalar operand2 from operand1 and stores result in resultant */
279  SCIP_Real infinity, /**< value for infinity */
280  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
281  SCIP_INTERVAL operand1, /**< first operand of operation */
282  SCIP_Real operand2 /**< second operand of operation */
283  );
284 
285 /** multiplies operand1 with operand2 and stores infimum of result in infimum of resultant */
287 void SCIPintervalMulInf(
288  SCIP_Real infinity, /**< value for infinity */
289  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
290  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
291  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
292  );
293 
294 /** multiplies operand1 with operand2 and stores supremum of result in supremum of resultant */
296 void SCIPintervalMulSup(
297  SCIP_Real infinity, /**< value for infinity */
298  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
299  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
300  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
301  );
302 
303 /** multiplies operand1 with operand2 and stores result in resultant */
305 void SCIPintervalMul(
306  SCIP_Real infinity, /**< value for infinity */
307  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
308  SCIP_INTERVAL operand1, /**< first operand of operation */
309  SCIP_INTERVAL operand2 /**< second operand of operation */
310  );
311 
312 /** multiplies operand1 with scalar operand2 and stores infimum of result in infimum of resultant */
315  SCIP_Real infinity, /**< value for infinity */
316  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
317  SCIP_INTERVAL operand1, /**< first operand of operation */
318  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
319  );
320 
321 /** multiplies operand1 with scalar operand2 and stores supremum of result in supremum of resultant */
324  SCIP_Real infinity, /**< value for infinity */
325  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
326  SCIP_INTERVAL operand1, /**< first operand of operation */
327  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
328  );
329 
330 /** multiplies operand1 with scalar operand2 and stores result in resultant */
333  SCIP_Real infinity, /**< value for infinity */
334  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
335  SCIP_INTERVAL operand1, /**< first operand of operation */
336  SCIP_Real operand2 /**< second operand of operation */
337  );
338 
339 /** divides operand1 by operand2 and stores result in resultant */
341 void SCIPintervalDiv(
342  SCIP_Real infinity, /**< value for infinity */
343  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
344  SCIP_INTERVAL operand1, /**< first operand of operation */
345  SCIP_INTERVAL operand2 /**< second operand of operation */
346  );
347 
348 /** divides operand1 by scalar operand2 and stores result in resultant */
351  SCIP_Real infinity, /**< value for infinity */
352  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
353  SCIP_INTERVAL operand1, /**< first operand of operation */
354  SCIP_Real operand2 /**< second operand of operation */
355  );
356 
357 /** computes the scalar product of two vectors of intervals and stores result in resultant */
360  SCIP_Real infinity, /**< value for infinity */
361  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
362  int length, /**< length of vectors */
363  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
364  SCIP_INTERVAL* operand2 /**< second vector as array of intervals */
365  );
366 
367 /** computes the scalar product of a vector of intervals and a vector of scalars and stores infimum of result in infimum
368  * of resultant
369  */
372  SCIP_Real infinity, /**< value for infinity */
373  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
374  int length, /**< length of vectors */
375  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
376  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
377  );
378 
379 /** computes the scalar product of a vector of intervals and a vector of scalars and stores supremum of result in supremum
380  * of resultant
381  */
384  SCIP_Real infinity, /**< value for infinity */
385  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
386  int length, /**< length of vectors */
387  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
388  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
389  );
390 
391 /** computes the scalar product of a vector of intervals and a vector of scalars and stores result in resultant */
394  SCIP_Real infinity, /**< value for infinity */
395  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
396  int length, /**< length of vectors */
397  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
398  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
399  );
400 
401 /** squares operand and stores result in resultant */
403 void SCIPintervalSquare(
404  SCIP_Real infinity, /**< value for infinity */
405  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
406  SCIP_INTERVAL operand /**< operand of operation */
407  );
408 
409 /** stores (positive part of) square root of operand in resultant
410  * @attention we assume a correctly rounded sqrt(double) function when rounding is to nearest
411  */
414  SCIP_Real infinity, /**< value for infinity */
415  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
416  SCIP_INTERVAL operand /**< operand of operation */
417  );
418 
419 /** stores operand1 to the power of operand2 in resultant
420  *
421  * uses SCIPintervalPowerScalar if operand2 is a scalar, otherwise computes exp(op2*log(op1))
422  */
424 void SCIPintervalPower(
425  SCIP_Real infinity, /**< value for infinity */
426  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
427  SCIP_INTERVAL operand1, /**< first operand of operation */
428  SCIP_INTERVAL operand2 /**< second operand of operation */
429  );
430 
431 /** stores operand1 to the power of the scalar operand2 in resultant */
434  SCIP_Real infinity, /**< value for infinity */
435  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
436  SCIP_INTERVAL operand1, /**< first operand of operation */
437  SCIP_Real operand2 /**< second operand of operation */
438  );
439 
440 /** stores bounds on the power of a scalar operand1 to a scalar operand2 in resultant
441  * both operands need to be finite numbers
442  * need to have operand1 >= 0 or operand2 integer and need to have operand2 >= 0 if operand1 == 0
443  * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
444  */
447  SCIP_INTERVAL* resultant, /**< resultant of operation */
448  SCIP_Real operand1, /**< first operand of operation */
449  SCIP_Real operand2 /**< second operand of operation */
450  );
451 
452 /** computes lower bound on power of a scalar operand1 to an integer operand2
453  * both operands need to be finite numbers
454  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
455  */
458  SCIP_Real operand1, /**< first operand of operation */
459  int operand2 /**< second operand of operation */
460  );
461 
462 /** computes upper bound on power of a scalar operand1 to an integer operand2
463  * both operands need to be finite numbers
464  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
465  */
468  SCIP_Real operand1, /**< first operand of operation */
469  int operand2 /**< second operand of operation */
470  );
471 
472 /** computes bounds on power of a scalar operand1 to an integer operand2
473  * both operands need to be finite numbers
474  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
475  */
478  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
479  SCIP_Real operand1, /**< first operand of operation */
480  int operand2 /**< second operand of operation */
481  );
482 
483 /** given an interval for the image of a power operation, computes an interval for the origin
484  * that is, for y = x^p with p = exponent a given scalar and y = image a given interval,
485  * computes a subinterval x of basedomain such that y in x^p and such that for all z in basedomain less x, z^p not in y
486  */
489  SCIP_Real infinity, /**< value for infinity */
490  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
491  SCIP_INTERVAL basedomain, /**< domain of base */
492  SCIP_Real exponent, /**< exponent */
493  SCIP_INTERVAL image /**< interval image of power */
494  );
495 
496 /** stores operand1 to the signed power of the scalar positive operand2 in resultant
497  *
498  * the signed power of x w.r.t. an exponent n >= 0 is given as sign(x) * abs(x)^n
499  *
500  * @attention we assume correctly rounded sqrt(double) and pow(double) functions when rounding is to nearest
501  */
504  SCIP_Real infinity, /**< value for infinity */
505  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
506  SCIP_INTERVAL operand1, /**< first operand of operation */
507  SCIP_Real operand2 /**< second operand of operation */
508  );
509 
510 /** computes the reciprocal of an interval
511  */
514  SCIP_Real infinity, /**< value for infinity */
515  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
516  SCIP_INTERVAL operand /**< operand of operation */
517  );
518 
519 /** stores exponential of operand in resultant
520  * @attention we assume a correctly rounded exp(double) function when rounding is to nearest
521  */
523 void SCIPintervalExp(
524  SCIP_Real infinity, /**< value for infinity */
525  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
526  SCIP_INTERVAL operand /**< operand of operation */
527  );
528 
529 /** stores natural logarithm of operand in resultant
530  * @attention we assume a correctly rounded log(double) function when rounding is to nearest
531  */
533 void SCIPintervalLog(
534  SCIP_Real infinity, /**< value for infinity */
535  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
536  SCIP_INTERVAL operand /**< operand of operation */
537  );
538 
539 /** stores minimum of operands in resultant */
541 void SCIPintervalMin(
542  SCIP_Real infinity, /**< value for infinity */
543  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
544  SCIP_INTERVAL operand1, /**< first operand of operation */
545  SCIP_INTERVAL operand2 /**< second operand of operation */
546  );
547 
548 /** stores maximum of operands in resultant */
550 void SCIPintervalMax(
551  SCIP_Real infinity, /**< value for infinity */
552  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
553  SCIP_INTERVAL operand1, /**< first operand of operation */
554  SCIP_INTERVAL operand2 /**< second operand of operation */
555  );
556 
557 /** stores absolute value of operand in resultant */
559 void SCIPintervalAbs(
560  SCIP_Real infinity, /**< value for infinity */
561  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
562  SCIP_INTERVAL operand /**< operand of operation */
563  );
564 
565 /** stores sine value of operand in resultant
566  * NOTE: the operations are not applied rounding-safe here
567  */
569 void SCIPintervalSin(
570  SCIP_Real infinity, /**< value for infinity */
571  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
572  SCIP_INTERVAL operand /**< operand of operation */
573  );
574 
575 /** stores cosine value of operand in resultant
576  * NOTE: the operations are not applied rounding-safe here
577  */
579 void SCIPintervalCos(
580  SCIP_Real infinity, /**< value for infinity */
581  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
582  SCIP_INTERVAL operand /**< operand of operation */
583  );
584 
585 /** stores sign of operand in resultant */
587 void SCIPintervalSign(
588  SCIP_Real infinity, /**< value for infinity */
589  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
590  SCIP_INTERVAL operand /**< operand of operation */
591  );
592 
593 /** computes exact upper bound on \f$ a x^2 + b x \f$ for x in [xlb, xub], b an interval, and a scalar
594  *
595  * Uses Algorithm 2.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008) */
598  SCIP_Real infinity, /**< value for infinity */
599  SCIP_Real a, /**< coefficient of x^2 */
600  SCIP_INTERVAL b_, /**< coefficient of x */
601  SCIP_INTERVAL x /**< range of x */
602  );
603 
604 /** stores range of quadratic term in resultant
605  *
606  * given scalar a and intervals b and x, computes interval for \f$ a x^2 + b x \f$ */
608 void SCIPintervalQuad(
609  SCIP_Real infinity, /**< value for infinity */
610  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
611  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
612  SCIP_INTERVAL lincoeff, /**< coefficient of x */
613  SCIP_INTERVAL xrng /**< range of x */
614  );
615 
616 
617 /** computes interval with positive solutions of a quadratic equation with interval coefficients
618  *
619  * 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.
620  */
623  SCIP_Real infinity, /**< value for infinity */
624  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
625  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
626  SCIP_INTERVAL lincoeff, /**< coefficient of x */
627  SCIP_INTERVAL rhs, /**< right hand side of equation */
628  SCIP_INTERVAL xbnds /**< bounds on x */
629  );
630 
631 /** computes interval with negative solutions of a quadratic equation with interval coefficients
632  *
633  * 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.
634  */
637  SCIP_Real infinity, /**< value for infinity */
638  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
639  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
640  SCIP_INTERVAL lincoeff, /**< coefficient of x */
641  SCIP_INTERVAL rhs, /**< right hand side of equation */
642  SCIP_INTERVAL xbnds /**< bounds on x */
643  );
644 
645 /** computes positive solutions of a quadratic equation with scalar coefficients
646  *
647  * Given 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.
648  * Implements Algorithm 3.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008).
649  */
652  SCIP_Real infinity, /**< value for infinity */
653  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
654  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
655  SCIP_Real lincoeff, /**< coefficient of x */
656  SCIP_Real rhs, /**< right hand side of equation */
657  SCIP_INTERVAL xbnds /**< bounds on x */
658  );
659 
660 /** solves a quadratic equation with interval coefficients
661  *
662  * 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
663  */
666  SCIP_Real infinity, /**< value for infinity */
667  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
668  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
669  SCIP_INTERVAL lincoeff, /**< coefficient of x */
670  SCIP_INTERVAL rhs, /**< right hand side of equation */
671  SCIP_INTERVAL xbnds /**< bounds on x */
672  );
673 
674 /** stores range of bivariate quadratic term in resultant
675  * given scalars ax, ay, axy, bx, and by and intervals for x and y, computes interval for \f$ ax x^2 + ay y^2 + axy x y + bx x + by y \f$
676  * NOTE: the operations are not applied rounding-safe here
677  */
680  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
681  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
682  SCIP_Real ax, /**< square coefficient of x */
683  SCIP_Real ay, /**< square coefficient of y */
684  SCIP_Real axy, /**< bilinear coefficients */
685  SCIP_Real bx, /**< linear coefficient of x */
686  SCIP_Real by, /**< linear coefficient of y */
687  SCIP_INTERVAL xbnds, /**< bounds on x */
688  SCIP_INTERVAL ybnds /**< bounds on y */
689  );
690 
691 /** solves a bivariate quadratic equation for the first variable
692  * given scalars ax, ay, axy, bx and by, and intervals for x, y, and rhs,
693  * 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$
694  * NOTE: the operations are not applied rounding-safe here
695  */
698  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
699  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
700  SCIP_Real ax, /**< square coefficient of x */
701  SCIP_Real ay, /**< square coefficient of y */
702  SCIP_Real axy, /**< bilinear coefficients */
703  SCIP_Real bx, /**< linear coefficient of x */
704  SCIP_Real by, /**< linear coefficient of y */
705  SCIP_INTERVAL rhs, /**< right-hand-side of equation */
706  SCIP_INTERVAL xbnds, /**< bounds on x */
707  SCIP_INTERVAL ybnds /**< bounds on y */
708  );
709 
710 #ifdef __cplusplus
711 }
712 #endif
713 
714 #endif
SCIP_EXPORT SCIP_Real SCIPintervalPowerScalarIntegerSup(SCIP_Real operand1, int operand2)
SCIP_EXPORT void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT SCIP_Bool SCIPintervalIsNegativeInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSetRoundingModeDownwards(void)
SCIP_EXPORT void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
SCIP_EXPORT void SCIPintervalScalprod(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
SCIP_EXPORT void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
#define infinity
Definition: gastrans.c:71
SCIP_EXPORT SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
#define SCIP_EXPORT
Definition: def.h:100
SCIP_EXPORT void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng)
SCIP_EXPORT void SCIPintervalMulSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalMulInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT SCIP_Real SCIPintervalPowerScalarIntegerInf(SCIP_Real operand1, int operand2)
SCIP_EXPORT SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_VAR ** x
Definition: circlepacking.c:54
SCIP_EXPORT void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
SCIP_EXPORT void SCIPintervalPowerScalarScalar(SCIP_INTERVAL *resultant, SCIP_Real operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalMulScalarInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT SCIP_Bool SCIPintervalIsPositiveInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_Real inf
Definition: intervalarith.h:39
SCIP_EXPORT SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_EXPORT void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalScalprodScalarsSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_EXPORT void SCIPintervalAddVectors(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
SCIP_EXPORT void SCIPintervalSetRoundingModeTowardsZero(void)
SCIP_EXPORT void SCIPintervalSetRoundingModeUpwards(void)
SCIP_EXPORT void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
SCIP_EXPORT SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_Real sup
Definition: intervalarith.h:40
SCIP_EXPORT 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)
SCIP_EXPORT SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
SCIP_EXPORT void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
SCIP_EXPORT void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalSolveUnivariateQuadExpressionNegative(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
SCIP_EXPORT void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT void SCIPintervalMulScalarSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSetRoundingModeToNearest(void)
SCIP_EXPORT void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_Real lincoeff, SCIP_Real rhs, SCIP_INTERVAL xbnds)
SCIP_EXPORT 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)
SCIP_EXPORT void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT SCIP_Bool SCIPintervalHasRoundingControl(void)
SCIP_EXPORT void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x)
SCIP_EXPORT void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalReciprocal(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT SCIP_Real SCIPintervalNegateReal(SCIP_Real x)
SCIP_EXPORT void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
SCIP_EXPORT SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
SCIP_EXPORT void SCIPintervalScalprodScalarsInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_EXPORT void SCIPintervalPowerScalarInteger(SCIP_INTERVAL *resultant, SCIP_Real operand1, int operand2)
SCIP_EXPORT void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
SCIP_VAR * a
Definition: circlepacking.c:57
#define SCIP_Real
Definition: def.h:163
int SCIP_ROUNDMODE
Definition: intervalarith.h:46
SCIP_EXPORT void SCIPintervalSignPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_EXPORT SCIP_Bool SCIPintervalAreDisjoint(SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
common defines and data types used in all packages of SCIP
SCIP_EXPORT void SCIPintervalAddSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_EXPORT void SCIPintervalSolveUnivariateQuadExpressionPositive(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
SCIP_EXPORT void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
SCIP_EXPORT void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_EXPORT void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalPower(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_EXPORT void SCIPintervalAddInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)