Scippy

SCIP

Solving Constraint Integer Programs

intervalarith.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright 2002-2022 Zuse Institute Berlin */
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 */
54 {
55  SCIP_Real inf; /**< infimum (lower bound) of interval */
56  SCIP_Real sup; /**< supremum (upper bound) of interval */
57 };
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
73  void
74  );
75 
76 /** sets rounding mode of floating point operations */
77 SCIP_EXPORT
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
91  void
92  );
93 
94 /** sets rounding mode of floating point operations to upwards rounding */
95 SCIP_EXPORT
97  void
98  );
99 
100 /** sets rounding mode of floating point operations to nearest rounding */
101 SCIP_EXPORT
103  void
104  );
105 
106 /** sets rounding mode of floating point operations to towards zero rounding */
107 SCIP_EXPORT
109  void
110  );
111 
112 /** negates a number in a way that the compiler does not optimize it away */
113 SCIP_EXPORT
115  SCIP_Real x /**< number to negate */
116  );
117 
118 /** returns infimum of interval */
119 SCIP_EXPORT
121  SCIP_INTERVAL interval /**< interval */
122  );
123 
124 /** returns supremum of interval */
125 SCIP_EXPORT
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
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
148  SCIP_INTERVAL* resultant /**< resultant interval of operation */
149  );
150 
151 /** indicates whether interval is empty, i.e., whether inf > sup */
152 SCIP_EXPORT
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
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 &le; -infinity and sup &ge; infinity */
166 SCIP_EXPORT
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
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
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
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
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
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
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)` &le; eps
249  * - `resultant = { operand1.inf }`, if `operand1.inf` > `operand2.sup` and `reldiff(operand1.inf,operand2.sup)` &le; eps
250  * - `resultant` = intersection of `operand1` and `operand2`, otherwise
251  */
252 SCIP_EXPORT
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
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
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
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
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
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
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
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
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
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
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
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
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
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 &ge; 0 or operand2 integer and needs to have operand2 &ge; 0 if operand1 = 0.
489  * @attention we assume a correctly rounded pow(double) function when rounding is to nearest
490  */
491 SCIP_EXPORT
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 &ge; 0 and need to have operand2 &ge; 0 if operand1 = 0.
502  */
503 SCIP_EXPORT
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 &ge; 0 and needs to have operand2 &ge; 0 if operand1 = 0.
513  */
514 SCIP_EXPORT
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 &ge; 0 and needs to have operand2 &ge; 0 if operand1 = 0.
524  */
525 SCIP_EXPORT
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
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 &ge; 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
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
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
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
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
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
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
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
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
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
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
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
void SCIPintervalSetEntire(SCIP_Real infinity, SCIP_INTERVAL *resultant)
void SCIPintervalReciprocal(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsSubsetEQ(SCIP_Real infinity, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalUnify(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
int SCIP_ROUNDMODE
Definition: intervalarith.h:64
void SCIPintervalCos(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsEntire(SCIP_Real infinity, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalPowerScalarIntegerSup(SCIP_Real operand1, int operand2)
#define infinity
Definition: gastrans.c:80
SCIP_Bool SCIPintervalIsPositiveInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalPowerScalarScalar(SCIP_INTERVAL *resultant, SCIP_Real operand1, SCIP_Real operand2)
void SCIPintervalMulSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetRoundingMode(SCIP_ROUNDMODE roundmode)
void SCIPintervalQuad(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL xrng)
SCIP_Bool SCIPintervalIsNegativeInfinity(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSub(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real SCIPintervalPowerScalarIntegerInf(SCIP_Real operand1, int operand2)
void SCIPintervalScalprodScalarsInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
void SCIPintervalAddScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSolveUnivariateQuadExpression(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real sqrcoeff, SCIP_Real lincoeff, SCIP_Real rhs, SCIP_INTERVAL xbnds)
void SCIPintervalPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalSet(SCIP_INTERVAL *resultant, SCIP_Real value)
void SCIPintervalAdd(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_ROUNDMODE SCIPintervalGetRoundingMode(void)
void SCIPintervalAddSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalMulInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_VAR ** x
Definition: circlepacking.c:63
real eps
void SCIPintervalScalprodScalars(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_Bool SCIPintervalAreDisjoint(SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalDiv(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Real inf
Definition: intervalarith.h:55
void SCIPintervalAbs(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSolveBivariateQuadExpressionAllScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds)
void SCIPintervalScalprod(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
void SCIPintervalScalprodScalarsSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_Real *operand2)
SCIP_Real SCIPintervalNegateReal(SCIP_Real x)
void SCIPintervalSquareRoot(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Real SCIPintervalQuadUpperBound(SCIP_Real infinity, SCIP_Real a, SCIP_INTERVAL b_, SCIP_INTERVAL x)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalMulScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalMulScalarSup(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
int SCIPintervalPropagateWeightedSum(SCIP_Real infinity, int noperands, SCIP_INTERVAL *operands, SCIP_Real *weights, SCIP_Real constant, SCIP_INTERVAL rhs, SCIP_INTERVAL *resultants, SCIP_Bool *infeasible)
SCIP_Real sup
Definition: intervalarith.h:56
void SCIPintervalEntropy(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalSolveUnivariateQuadExpressionPositive(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalSetRoundingModeDownwards(void)
void SCIPintervalSetRoundingModeToNearest(void)
#define SCIP_Bool
Definition: def.h:93
void SCIPintervalAddInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalPower(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalPowerScalarInverse(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL basedomain, SCIP_Real exponent, SCIP_INTERVAL image)
void SCIPintervalPowerScalarInteger(SCIP_INTERVAL *resultant, SCIP_Real operand1, int operand2)
SCIP_Bool SCIPintervalAreDisjointEps(SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSubScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalQuadBivar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_Real ax, SCIP_Real ay, SCIP_Real axy, SCIP_Real bx, SCIP_Real by, SCIP_INTERVAL xbnds, SCIP_INTERVAL ybnds)
void SCIPintervalSign(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalSetRoundingModeTowardsZero(void)
void SCIPintervalSignPowerScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalDivScalar(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalSquare(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalMulScalarInf(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_Real operand2)
void SCIPintervalMul(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSetRoundingModeUpwards(void)
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_Bool SCIPintervalHasRoundingControl(void)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
#define SCIP_Real
Definition: def.h:186
void SCIPintervalAddVectors(SCIP_Real infinity, SCIP_INTERVAL *resultant, int length, SCIP_INTERVAL *operand1, SCIP_INTERVAL *operand2)
common defines and data types used in all packages of SCIP
void SCIPintervalMax(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSolveUnivariateQuadExpressionNegative(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL sqrcoeff, SCIP_INTERVAL lincoeff, SCIP_INTERVAL rhs, SCIP_INTERVAL xbnds)
void SCIPintervalMin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalSin(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)