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