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-2014 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip/intervalarith.h
17  * @brief interval arithmetics for provable bounds
18  * @author Tobias Achterberg
19  * @author Stefan Vigerske
20  * @author Kati Wolter
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #ifndef __SCIP_INTERVALARITH_H__
26 #define __SCIP_INTERVALARITH_H__
27 
28 
29 #include "scip/def.h"
30 
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 
35 /** interval given by infimum and supremum */
36 struct SCIP_Interval
37 {
38  SCIP_Real inf; /**< infimum (lower bound) of interval */
39  SCIP_Real sup; /**< supremum (upper bound) of interval */
40 };
41 typedef struct SCIP_Interval SCIP_INTERVAL;
42 
43 /** rounding mode of floating point operations (upwards, downwards, nearest, ...)
44  * exact values depend on machine and compiler, so we define a corresponding enum in the header file */
45 typedef int SCIP_ROUNDMODE;
46 
47 /*
48  * Interval arithmetic operations
49  */
50 
51 /** returns whether rounding mode control is available */
52 extern
53 SCIP_Bool SCIPintervalHasRoundingControl(
54  void
55  );
56 
57 /** sets rounding mode of floating point operations */
58 extern
59 void SCIPintervalSetRoundingMode(
60  SCIP_ROUNDMODE roundmode /**< rounding mode to activate */
61  );
62 
63 /** gets current rounding mode of floating point operations */
64 extern
65 SCIP_ROUNDMODE SCIPintervalGetRoundingMode(
66  void
67  );
68 
69 /** sets rounding mode of floating point operations to downwards rounding */
70 extern
71 void SCIPintervalSetRoundingModeDownwards(
72  void
73  );
74 
75 /** sets rounding mode of floating point operations to upwards rounding */
76 extern
77 void SCIPintervalSetRoundingModeUpwards(
78  void
79  );
80 
81 /** sets rounding mode of floating point operations to nearest rounding */
82 extern
83 void SCIPintervalSetRoundingModeToNearest(
84  void
85  );
86 
87 /** sets rounding mode of floating point operations to towards zero rounding */
88 extern
89 void SCIPintervalSetRoundingModeTowardsZero(
90  void
91  );
92 
93 /** negates a number in a way that the compiler does not optimize it away */
94 extern
95 SCIP_Real SCIPintervalNegateReal(
96  SCIP_Real x /**< number to negate */
97  );
98 
99 /** returns infimum of interval */
100 extern
101 SCIP_Real SCIPintervalGetInf(
102  SCIP_INTERVAL interval /**< interval */
103  );
104 
105 /** returns supremum of interval */
106 extern
107 SCIP_Real SCIPintervalGetSup(
108  SCIP_INTERVAL interval /**< interval */
109  );
110 
111 /** stores given value as interval */
112 extern
113 void SCIPintervalSet(
114  SCIP_INTERVAL* resultant, /**< interval to store value into */
115  SCIP_Real value /**< value to store */
116  );
117 
118 /** stores given infimum and supremum as interval */
119 extern
120 void SCIPintervalSetBounds(
121  SCIP_INTERVAL* resultant, /**< interval to store value into */
122  SCIP_Real inf, /**< value to store as infimum */
123  SCIP_Real sup /**< value to store as supremum */
124  );
125 
126 /** sets interval to empty interval, which will be [1.0, -1.0] */
127 extern
128 void SCIPintervalSetEmpty(
129  SCIP_INTERVAL* resultant /**< resultant interval of operation */
130  );
131 
132 /** indicates whether interval is empty, i.e., whether inf > sup */
133 extern
134 SCIP_Bool SCIPintervalIsEmpty(
135  SCIP_INTERVAL operand /**< operand of operation */
136  );
137 
138 /** sets interval to entire [-infinity, +infinity] */
139 extern
140 void SCIPintervalSetEntire(
141  SCIP_Real infinity, /**< value for infinity */
142  SCIP_INTERVAL* resultant /**< resultant interval of operation */
143  );
144 
145 /** indicates whether interval is entire, i.e., whether inf <= -infinity and sup >= infinity */
146 extern
147 SCIP_Bool SCIPintervalIsEntire(
148  SCIP_Real infinity, /**< value for infinity */
149  SCIP_INTERVAL operand /**< operand of operation */
150  );
151 
152 /** indicates whether interval is positive infinity, i.e., [infinity, infinity] */
153 extern
154 SCIP_Bool SCIPintervalIsPositiveInfinity(
155  SCIP_Real infinity, /**< value for infinity */
156  SCIP_INTERVAL operand /**< operand of operation */
157  );
158 
159 /** indicates whether interval is negative infinity, i.e., [-infinity, -infinity] */
160 extern
161 SCIP_Bool SCIPintervalIsNegativeInfinity(
162  SCIP_Real infinity, /**< value for infinity */
163  SCIP_INTERVAL operand /**< operand of operation */
164  );
165 
166 #ifdef NDEBUG
167 
168 /* In optimized mode, some function calls are overwritten by defines to reduce the number of function calls and
169  * speed up the algorithms.
170  * With SCIPintervalSetBounds we need to be a bit careful, since i and s could use resultant->inf and resultant->sup,
171  * e.g., SCIPintervalSetBounds(&resultant, -resultant->sup, -resultant->inf).
172  * So we need to make sure that we first evaluate both terms before setting resultant.
173  */
174 
175 #define SCIPintervalGetInf(interval) (interval).inf
176 #define SCIPintervalGetSup(interval) (interval).sup
177 #define SCIPintervalSet(resultant, value) do { (resultant)->inf = (value); (resultant)->sup = (resultant)->inf; } while( FALSE )
178 #define SCIPintervalSetBounds(resultant, i, s) do { SCIP_Real scipintervaltemp; scipintervaltemp = (s); (resultant)->inf = (i); (resultant)->sup = scipintervaltemp; } while( FALSE )
179 #define SCIPintervalSetEmpty(resultant) do { (resultant)->inf = 1.0; (resultant)->sup = -1.0; } while( FALSE )
180 #define SCIPintervalSetEntire(infinity, resultant) do { (resultant)->inf = -(infinity); (resultant)->sup = (infinity); } while( FALSE )
181 #define SCIPintervalIsEmpty(operand) ( (operand).sup < (operand).inf )
182 #define SCIPintervalIsEntire(infinity, operand) ( (operand).inf <= -(infinity) && (operand).sup >= (infinity) )
183 #define SCIPintervalIsPositiveInfinity(infinity, operand) ( (operand).inf >= (infinity) && (operand).sup >= (operand).inf )
184 #define SCIPintervalIsNegativeInfinity(infinity, operand) ( (operand).sup <= -(infinity) && (operand).sup >= (operand).inf )
185 
186 #endif
187 
188 /** indicates whether operand1 is contained in operand2 */
189 extern
190 SCIP_Bool SCIPintervalIsSubsetEQ(
191  SCIP_Real infinity, /**< value for infinity */
192  SCIP_INTERVAL operand1, /**< first operand of operation */
193  SCIP_INTERVAL operand2 /**< second operand of operation */
194  );
195 
196 /** indicates whether operand1 and operand2 are disjoint */
197 extern
198 SCIP_Bool SCIPintervalAreDisjoint(
199  SCIP_INTERVAL operand1, /**< first operand of operation */
200  SCIP_INTERVAL operand2 /**< second operand of operation */
201  );
202 
203 /** intersection of two intervals */
204 extern
205 void SCIPintervalIntersect(
206  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
207  SCIP_INTERVAL operand1, /**< first operand of operation */
208  SCIP_INTERVAL operand2 /**< second operand of operation */
209  );
210 
211 /** interval enclosure of the union of two intervals */
212 extern
213 void SCIPintervalUnify(
214  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
215  SCIP_INTERVAL operand1, /**< first operand of operation */
216  SCIP_INTERVAL operand2 /**< second operand of operation */
217  );
218 
219 /** adds operand1 and operand2 and stores infimum of result in infimum of resultant */
220 extern
221 void SCIPintervalAddInf(
222  SCIP_Real infinity, /**< value for infinity */
223  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
224  SCIP_INTERVAL operand1, /**< first operand of operation */
225  SCIP_INTERVAL operand2 /**< second operand of operation */
226  );
227 
228 /** adds operand1 and operand2 and stores supremum of result in supremum of resultant */
229 extern
230 void SCIPintervalAddSup(
231  SCIP_Real infinity, /**< value for infinity */
232  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
233  SCIP_INTERVAL operand1, /**< first operand of operation */
234  SCIP_INTERVAL operand2 /**< second operand of operation */
235  );
236 
237 /** adds operand1 and operand2 and stores result in resultant */
238 extern
239 void SCIPintervalAdd(
240  SCIP_Real infinity, /**< value for infinity */
241  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
242  SCIP_INTERVAL operand1, /**< first operand of operation */
243  SCIP_INTERVAL operand2 /**< second operand of operation */
244  );
245 
246 /** adds operand1 and scalar operand2 and stores result in resultant */
247 extern
248 void SCIPintervalAddScalar(
249  SCIP_Real infinity, /**< value for infinity */
250  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
251  SCIP_INTERVAL operand1, /**< first operand of operation */
252  SCIP_Real operand2 /**< second operand of operation */
253  );
254 
255 /** adds vector operand1 and vector operand2 and stores result in vector resultant */
256 extern
257 void SCIPintervalAddVectors(
258  SCIP_Real infinity, /**< value for infinity */
259  SCIP_INTERVAL* resultant, /**< array of resultant intervals of operation */
260  int length, /**< length of arrays */
261  SCIP_INTERVAL* operand1, /**< array of first operands of operation */
262  SCIP_INTERVAL* operand2 /**< array of second operands of operation */
263  );
264 
265 /** subtracts operand2 from operand1 and stores result in resultant */
266 extern
267 void SCIPintervalSub(
268  SCIP_Real infinity, /**< value for infinity */
269  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
270  SCIP_INTERVAL operand1, /**< first operand of operation */
271  SCIP_INTERVAL operand2 /**< second operand of operation */
272  );
273 
274 /** subtracts scalar operand2 from operand1 and stores result in resultant */
275 extern
276 void SCIPintervalSubScalar(
277  SCIP_Real infinity, /**< value for infinity */
278  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
279  SCIP_INTERVAL operand1, /**< first operand of operation */
280  SCIP_Real operand2 /**< second operand of operation */
281  );
282 
283 /** multiplies operand1 with operand2 and stores infimum of result in infimum of resultant */
284 extern
285 void SCIPintervalMulInf(
286  SCIP_Real infinity, /**< value for infinity */
287  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
288  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
289  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
290  );
291 
292 /** multiplies operand1 with operand2 and stores supremum of result in supremum of resultant */
293 extern
294 void SCIPintervalMulSup(
295  SCIP_Real infinity, /**< value for infinity */
296  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
297  SCIP_INTERVAL operand1, /**< first operand of operation; can be +/-inf */
298  SCIP_INTERVAL operand2 /**< second operand of operation; can be +/-inf */
299  );
300 
301 /** multiplies operand1 with operand2 and stores result in resultant */
302 extern
303 void SCIPintervalMul(
304  SCIP_Real infinity, /**< value for infinity */
305  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
306  SCIP_INTERVAL operand1, /**< first operand of operation */
307  SCIP_INTERVAL operand2 /**< second operand of operation */
308  );
309 
310 /** multiplies operand1 with scalar operand2 and stores infimum of result in infimum of resultant */
311 extern
312 void SCIPintervalMulScalarInf(
313  SCIP_Real infinity, /**< value for infinity */
314  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
315  SCIP_INTERVAL operand1, /**< first operand of operation */
316  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
317  );
318 
319 /** multiplies operand1 with scalar operand2 and stores supremum of result in supremum of resultant */
320 extern
321 void SCIPintervalMulScalarSup(
322  SCIP_Real infinity, /**< value for infinity */
323  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
324  SCIP_INTERVAL operand1, /**< first operand of operation */
325  SCIP_Real operand2 /**< second operand of operation; can be +/- inf */
326  );
327 
328 /** multiplies operand1 with scalar operand2 and stores result in resultant */
329 extern
330 void SCIPintervalMulScalar(
331  SCIP_Real infinity, /**< value for infinity */
332  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
333  SCIP_INTERVAL operand1, /**< first operand of operation */
334  SCIP_Real operand2 /**< second operand of operation */
335  );
336 
337 /** divides operand1 by operand2 and stores result in resultant */
338 extern
339 void SCIPintervalDiv(
340  SCIP_Real infinity, /**< value for infinity */
341  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
342  SCIP_INTERVAL operand1, /**< first operand of operation */
343  SCIP_INTERVAL operand2 /**< second operand of operation */
344  );
345 
346 /** divides operand1 by scalar operand2 and stores result in resultant */
347 extern
348 void SCIPintervalDivScalar(
349  SCIP_Real infinity, /**< value for infinity */
350  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
351  SCIP_INTERVAL operand1, /**< first operand of operation */
352  SCIP_Real operand2 /**< second operand of operation */
353  );
354 
355 /** computes the scalar product of two vectors of intervals and stores result in resultant */
356 extern
357 void SCIPintervalScalprod(
358  SCIP_Real infinity, /**< value for infinity */
359  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
360  int length, /**< length of vectors */
361  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
362  SCIP_INTERVAL* operand2 /**< second vector as array of intervals */
363  );
364 
365 /** computes the scalar product of a vector of intervals and a vector of scalars and stores infimum of result in infimum
366  * of resultant
367  */
368 extern
369 void SCIPintervalScalprodScalarsInf(
370  SCIP_Real infinity, /**< value for infinity */
371  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
372  int length, /**< length of vectors */
373  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
374  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
375  );
376 
377 /** computes the scalar product of a vector of intervals and a vector of scalars and stores supremum of result in supremum
378  * of resultant
379  */
380 extern
381 void SCIPintervalScalprodScalarsSup(
382  SCIP_Real infinity, /**< value for infinity */
383  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
384  int length, /**< length of vectors */
385  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
386  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
387  );
388 
389 /** computes the scalar product of a vector of intervals and a vector of scalars and stores result in resultant */
390 extern
391 void SCIPintervalScalprodScalars(
392  SCIP_Real infinity, /**< value for infinity */
393  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
394  int length, /**< length of vectors */
395  SCIP_INTERVAL* operand1, /**< first vector as array of intervals */
396  SCIP_Real* operand2 /**< second vector as array of scalars; can have +/-inf entries */
397  );
398 
399 /** squares operand and stores result in resultant */
400 extern
401 void SCIPintervalSquare(
402  SCIP_Real infinity, /**< value for infinity */
403  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
404  SCIP_INTERVAL operand /**< operand of operation */
405  );
406 
407 /** stores (positive part of) square root of operand in resultant
408  * @attention we assume a correctly rounded sqrt(double) function when rounding is to nearest
409  */
410 extern
411 void SCIPintervalSquareRoot(
412  SCIP_Real infinity, /**< value for infinity */
413  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
414  SCIP_INTERVAL operand /**< operand of operation */
415  );
416 
417 /** stores operand1 to the power of operand2 in resultant
418  *
419  * uses SCIPintervalPowerScalar if operand2 is a scalar, otherwise computes exp(op2*log(op1))
420  */
421 extern
422 void SCIPintervalPower(
423  SCIP_Real infinity, /**< value for infinity */
424  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
425  SCIP_INTERVAL operand1, /**< first operand of operation */
426  SCIP_INTERVAL operand2 /**< second operand of operation */
427  );
428 
429 /** stores operand1 to the power of the scalar operand2 in resultant */
430 extern
431 void SCIPintervalPowerScalar(
432  SCIP_Real infinity, /**< value for infinity */
433  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
434  SCIP_INTERVAL operand1, /**< first operand of operation */
435  SCIP_Real operand2 /**< second operand of operation */
436  );
437 
438 /** stores bounds on the power of a scalar operand1 to a scalar operand2 in resultant
439  * both operands need to be finite numbers
440  * need to have operand1 >= 0 or operand2 integer and need to have operand2 >= 0 if operand1 == 0
441  * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
442  */
443 extern
444 void SCIPintervalPowerScalarScalar(
445  SCIP_INTERVAL* resultant, /**< resultant of operation */
446  SCIP_Real operand1, /**< first operand of operation */
447  SCIP_Real operand2 /**< second operand of operation */
448  );
449 
450 /** computes lower bound on power of a scalar operand1 to an integer operand2
451  * both operands need to be finite numbers
452  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
453  */
454 extern
455 SCIP_Real SCIPintervalPowerScalarIntegerInf(
456  SCIP_Real operand1, /**< first operand of operation */
457  int operand2 /**< second operand of operation */
458  );
459 
460 /** computes upper bound on power of a scalar operand1 to an integer operand2
461  * both operands need to be finite numbers
462  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
463  */
464 extern
465 SCIP_Real SCIPintervalPowerScalarIntegerSup(
466  SCIP_Real operand1, /**< first operand of operation */
467  int operand2 /**< second operand of operation */
468  );
469 
470 /** computes bounds on power of a scalar operand1 to an integer operand2
471  * both operands need to be finite numbers
472  * need to have operand1 >= 0 and need to have operand2 >= 0 if operand1 == 0
473  */
474 extern
475 void SCIPintervalPowerScalarInteger(
476  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
477  SCIP_Real operand1, /**< first operand of operation */
478  int operand2 /**< second operand of operation */
479  );
480 
481 /** given an interval for the image of a power operation, computes an interval for the origin
482  * that is, for y = x^p with p = exponent a given scalar and y = image a given interval,
483  * 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
484  */
485 extern
486 void SCIPintervalPowerScalarInverse(
487  SCIP_Real infinity, /**< value for infinity */
488  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
489  SCIP_INTERVAL basedomain, /**< domain of base */
490  SCIP_Real exponent, /**< exponent */
491  SCIP_INTERVAL image /**< interval image of power */
492  );
493 
494 /** stores operand1 to the signed power of the scalar positive operand2 in resultant
495  *
496  * the signed power of x w.r.t. an exponent n >= 0 is given as sign(x) * abs(x)^n
497  *
498  * @attention we assume correctly rounded sqrt(double) and pow(double) functions when rounding is to nearest
499  */
500 extern
501 void SCIPintervalSignPowerScalar(
502  SCIP_Real infinity, /**< value for infinity */
503  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
504  SCIP_INTERVAL operand1, /**< first operand of operation */
505  SCIP_Real operand2 /**< second operand of operation */
506  );
507 
508 /** computes the reciprocal of an interval
509  */
510 extern
511 void SCIPintervalReciprocal(
512  SCIP_Real infinity, /**< value for infinity */
513  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
514  SCIP_INTERVAL operand /**< operand of operation */
515  );
516 
517 /** stores exponential of operand in resultant
518  * @attention we assume a correctly rounded exp(double) function when rounding is to nearest
519  */
520 extern
521 void SCIPintervalExp(
522  SCIP_Real infinity, /**< value for infinity */
523  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
524  SCIP_INTERVAL operand /**< operand of operation */
525  );
526 
527 /** stores natural logarithm of operand in resultant
528  * @attention we assume a correctly rounded log(double) function when rounding is to nearest
529  */
530 extern
531 void SCIPintervalLog(
532  SCIP_Real infinity, /**< value for infinity */
533  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
534  SCIP_INTERVAL operand /**< operand of operation */
535  );
536 
537 /** stores minimum of operands in resultant */
538 extern
539 void SCIPintervalMin(
540  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
541  SCIP_INTERVAL operand1, /**< first operand of operation */
542  SCIP_INTERVAL operand2 /**< second operand of operation */
543  );
544 
545 /** stores maximum of operands in resultant */
546 extern
547 void SCIPintervalMax(
548  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
549  SCIP_INTERVAL operand1, /**< first operand of operation */
550  SCIP_INTERVAL operand2 /**< second operand of operation */
551  );
552 
553 /** stores absolute value of operand in resultant */
554 extern
555 void SCIPintervalAbs(
556  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
557  SCIP_INTERVAL operand /**< operand of operation */
558  );
559 
560 /** stores sign of operand in resultant */
561 extern
562 void SCIPintervalSign(
563  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
564  SCIP_INTERVAL operand /**< operand of operation */
565  );
566 
567 /** computes exact upper bound on \f$ a x^2 + b x \f$ for x in [xlb, xub], b an interval, and a scalar
568  *
569  * Uses Algorithm 2.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008) */
570 extern
571 SCIP_Real SCIPintervalQuadUpperBound(
572  SCIP_Real infinity, /**< value for infinity */
573  SCIP_Real a, /**< coefficient of x^2 */
574  SCIP_INTERVAL b, /**< coefficient of x */
575  SCIP_INTERVAL xrng /**< range of x */
576  );
577 
578 /** stores range of quadratic term in resultant
579  *
580  * given scalar a and intervals b and x, computes interval for \f$ a x^2 + b x \f$ */
581 extern
582 void SCIPintervalQuad(
583  SCIP_Real infinity, /**< value for infinity */
584  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
585  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
586  SCIP_INTERVAL lincoeff, /**< coefficient of x */
587  SCIP_INTERVAL xrng /**< range of x */
588  );
589 
590 
591 /** computes interval with positive solutions of a quadratic equation with interval coefficients
592  *
593  * 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$.
594  */
595 extern
596 void SCIPintervalSolveUnivariateQuadExpressionPositive(
597  SCIP_Real infinity, /**< value for infinity */
598  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
599  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
600  SCIP_INTERVAL lincoeff, /**< coefficient of x */
601  SCIP_INTERVAL rhs /**< right hand side of equation */
602  );
603 
604 /** computes positive solutions of a quadratic equation with scalar coefficients
605  *
606  * 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$.
607  * Implements Algorithm 3.2 from Domes and Neumaier: Constraint propagation on quadratic constraints (2008).
608  */
609 extern
610 void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(
611  SCIP_Real infinity, /**< value for infinity */
612  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
613  SCIP_Real sqrcoeff, /**< coefficient of x^2 */
614  SCIP_Real lincoeff, /**< coefficient of x */
615  SCIP_Real rhs /**< right hand side of equation */
616  );
617 
618 /** solves a quadratic equation with interval coefficients
619  *
620  * 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$
621  */
622 extern
623 void SCIPintervalSolveUnivariateQuadExpression(
624  SCIP_Real infinity, /**< value for infinity */
625  SCIP_INTERVAL* resultant, /**< resultant interval of operation */
626  SCIP_INTERVAL sqrcoeff, /**< coefficient of x^2 */
627  SCIP_INTERVAL lincoeff, /**< coefficient of x */
628  SCIP_INTERVAL rhs /**< right hand side of equation */
629  );
630 
631 /** stores range of bivariate quadratic term in resultant
632  * 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$
633  * NOTE: the operations are not applied rounding-safe here
634  */
635 extern
636 void SCIPintervalQuadBivar(
637  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
638  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
639  SCIP_Real ax, /**< square coefficient of x */
640  SCIP_Real ay, /**< square coefficient of y */
641  SCIP_Real axy, /**< bilinear coefficients */
642  SCIP_Real bx, /**< linear coefficient of x */
643  SCIP_Real by, /**< linear coefficient of y */
644  SCIP_INTERVAL xbnds, /**< bounds on x */
645  SCIP_INTERVAL ybnds /**< bounds on y */
646  );
647 
648 /** solves a bivariate quadratic equation for the first variable
649  * given scalars ax, ay, axy, bx and by, and intervals for x, y, and rhs,
650  * 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$
651  * NOTE: the operations are not applied rounding-safe here
652  */
653 extern
654 void SCIPintervalSolveBivariateQuadExpressionAllScalar(
655  SCIP_Real infinity, /**< value for infinity in interval arithmetics */
656  SCIP_INTERVAL* resultant, /**< buffer where to store result of operation */
657  SCIP_Real ax, /**< square coefficient of x */
658  SCIP_Real ay, /**< square coefficient of y */
659  SCIP_Real axy, /**< bilinear coefficients */
660  SCIP_Real bx, /**< linear coefficient of x */
661  SCIP_Real by, /**< linear coefficient of y */
662  SCIP_INTERVAL rhs, /**< right-hand-side of equation */
663  SCIP_INTERVAL xbnds, /**< bounds on x */
664  SCIP_INTERVAL ybnds /**< bounds on y */
665  );
666 
667 #ifdef __cplusplus
668 }
669 #endif
670 
671 #endif
672