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