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 */
44 struct SCIP_Interval
45 {
46 SCIP_Real inf; /**< infimum (lower bound) of interval */
47 SCIP_Real sup; /**< supremum (upper bound) of interval */
48 };
49 typedef struct SCIP_Interval SCIP_INTERVAL;
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
63 SCIP_Bool SCIPintervalHasRoundingControl(
64 void
65 );
66
67 /** sets rounding mode of floating point operations */
68 SCIP_EXPORT
69 void SCIPintervalSetRoundingMode(
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
81 void SCIPintervalSetRoundingModeDownwards(
82 void
83 );
84
85 /** sets rounding mode of floating point operations to upwards rounding */
86 SCIP_EXPORT
87 void SCIPintervalSetRoundingModeUpwards(
88 void
89 );
90
91 /** sets rounding mode of floating point operations to nearest rounding */
92 SCIP_EXPORT
93 void SCIPintervalSetRoundingModeToNearest(
94 void
95 );
96
97 /** sets rounding mode of floating point operations to towards zero rounding */
98 SCIP_EXPORT
99 void SCIPintervalSetRoundingModeTowardsZero(
100 void
101 );
102
103 /** negates a number in a way that the compiler does not optimize it away */
104 SCIP_EXPORT
105 SCIP_Real SCIPintervalNegateReal(
106 SCIP_Real x /**< number to negate */
107 );
108
109 /** returns infimum of interval */
110 SCIP_EXPORT
111 SCIP_Real SCIPintervalGetInf(
112 SCIP_INTERVAL interval /**< interval */
113 );
114
115 /** returns supremum of interval */
116 SCIP_EXPORT
117 SCIP_Real SCIPintervalGetSup(
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
130 void SCIPintervalSetBounds(
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
138 void SCIPintervalSetEmpty(
139 SCIP_INTERVAL* resultant /**< resultant interval of operation */
140 );
141
142 /** indicates whether interval is empty, i.e., whether inf > sup */
143 SCIP_EXPORT
144 SCIP_Bool SCIPintervalIsEmpty(
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
151 void SCIPintervalSetEntire(
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 ≤ -infinity and sup ≥ infinity */
157 SCIP_EXPORT
158 SCIP_Bool SCIPintervalIsEntire(
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
165 SCIP_Bool SCIPintervalIsPositiveInfinity(
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
172 SCIP_Bool SCIPintervalIsNegativeInfinity(
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
201 SCIP_Bool SCIPintervalIsSubsetEQ(
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
209 SCIP_Bool SCIPintervalAreDisjoint(
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
220 SCIP_Bool SCIPintervalAreDisjointEps(
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
228 void SCIPintervalIntersect(
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)` ≤ eps
240 * - `resultant = { operand1.inf }`, if `operand1.inf` > `operand2.sup` and `reldiff(operand1.inf,operand2.sup)` ≤ eps
241 * - `resultant` = intersection of `operand1` and `operand2`, otherwise
242 */
243 SCIP_EXPORT
244 void SCIPintervalIntersectEps(
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
288 void SCIPintervalAddScalar(
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
297 void SCIPintervalAddVectors(
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
316 void SCIPintervalSubScalar(
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
352 void SCIPintervalMulScalarInf(
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
361 void SCIPintervalMulScalarSup(
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
370 void SCIPintervalMulScalar(
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
388 void SCIPintervalDivScalar(
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
397 void SCIPintervalScalprod(
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
407 void SCIPintervalScalprodScalarsInf(
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
417 void SCIPintervalScalprodScalarsSup(
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
427 void SCIPintervalScalprodScalars(
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
447 void SCIPintervalSquareRoot(
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
469 void SCIPintervalPowerScalar(
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 ≥ 0 or operand2 integer and needs to have operand2 ≥ 0 if operand1 = 0.
480 * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
481 */
482 SCIP_EXPORT
483 void SCIPintervalPowerScalarScalar(
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 ≥ 0 and need to have operand2 ≥ 0 if operand1 = 0.
493 */
494 SCIP_EXPORT
495 SCIP_Real SCIPintervalPowerScalarIntegerInf(
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 ≥ 0 and needs to have operand2 ≥ 0 if operand1 = 0.
504 */
505 SCIP_EXPORT
506 SCIP_Real SCIPintervalPowerScalarIntegerSup(
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 ≥ 0 and needs to have operand2 ≥ 0 if operand1 = 0.
515 */
516 SCIP_EXPORT
517 void SCIPintervalPowerScalarInteger(
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
529 void SCIPintervalPowerScalarInverse(
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 ≥ 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
544 void SCIPintervalSignPowerScalar(
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
554 void SCIPintervalReciprocal(
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
632 void SCIPintervalEntropy(
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
643 SCIP_Real SCIPintervalQuadUpperBound(
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
668 void SCIPintervalSolveUnivariateQuadExpressionPositive(
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
682 void SCIPintervalSolveUnivariateQuadExpressionNegative(
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
697 void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(
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
711 void SCIPintervalSolveUnivariateQuadExpression(
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
728 void SCIPintervalQuadBivar(
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
748 void SCIPintervalSolveBivariateQuadExpressionAllScalar(
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
771 int SCIPintervalPropagateWeightedSum(
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
789