×

A class of problems that can be solved using interval algorithms. (English) Zbl 1235.65043

Summary: The paper discusses several theoretical and implementational problems of interval branch-and-bound methods. A trial to define a class of problems that can be solved with such methods is done. Features and variants of the method are presented. Useful data structures and shared-memory parallelization issues are considered.

MSC:

65G40 General methods in interval analysis
65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

Intel TBB; INTOPT_90
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld G, Kreinovich V, Mayer G (1998) The shape of the solution set for systems of interval linear equations with dependent coefficients. Math Nachr 192: 23–36 · Zbl 0907.15003 · doi:10.1002/mana.19981920103
[2] Beelitz T, Lang B, Bischof CH (2006) Efficient task scheduling in the parallel result-verifying solution of nonlinear systems. Reliab Comput 12: 141–151 · Zbl 1083.65051 · doi:10.1007/s11155-006-4872-4
[3] Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms. MIT Press, Cambridge
[4] Fernandez J, Toth B (2007) Obtaining an outer approximation of the efficient set of nonlinear biobjective problems. J Glob Optim 38: 315–331 · Zbl 1172.90482 · doi:10.1007/s10898-006-9132-y
[5] Goualard F (2005) On considering an interval constraint solving algorithm as a free-steering nonlinear Gauss-Seidel procedure. In: SAC’05 proceedings of the 2005 ACM symposium on applied computing, ACM, New York
[6] Hansen E, Walster W (2004) Global optimization using interval analysis. Marcel Dekker, New York · Zbl 1103.90092
[7] Intel threading building blocks. http://www.threadingbuildingblocks.org
[8] Jaulin L, Kieffer M, Didrit O, Walter E (2001) Applied interval analysis. Springer, London · Zbl 1023.65037
[9] Kearfott RB (1996) Rigorous global search: continuous problems. Kluwer, Dordrecht · Zbl 0876.90082
[10] Kearfott RB, Nakao MT, Neumaier A, Rump SM, Shary SP, van Hentenryck P (2002) Standardized notation in interval analysis. http://www.mat.univie.ac.at/\(\sim\)neum/software/int/notation.ps.gz · Zbl 1196.65088
[11] Kreinovich V, Kubica BJ (2010) From computing sets of optima, Pareto sets and sets of Nash equilibria to general decision-related set computations. J Univers Comput Sci 16: 2657–2685 · Zbl 1219.91038
[12] Kubica BJ (2011) Interval methods for solving underdetermined nonlinear equations systems 2008. SCAN 2008 proceedings. Reliab Comput 15(3): 207–217
[13] Kubica BJ, Woźniak A (2008) Interval methods for computing the Pareto-front of a multicriterial problem. PPAM 2007 proceedings. LNCS 4967: 1382–1391
[14] Kubica BJ, Woźniak A (2012) A multi-threaded interval algorithm for the Pareto-front computation in a multi-core environment. Presented at PARA 2008 conference, accepted for publication in LNCS 6126
[15] Kubica BJ (2008) Can interval computations be applied over spaces of non-numbers?. Prace Naukowe Politechniki Warszawskiej. Elektronika 165: 103–112
[16] Kubica BJ (2009) Shared-memory parallelization of an interval equations systems solver–comparison of tools. Prace Naukowe Politechniki Warszawskiej. Elektronika 169: 121–128
[17] Kubica BJ (2009) Intel TBB as a tool for parallelization of an interval solver of nonlinear equations systems. ICCE internal report no 09-02
[18] Kubica BJ, Woźniak A (2010) Using the second-order information in Pareto-set computations of a multi-criteria problem. Presented at PARA 2010 conference, accepted for publication in LNCS
[19] Kubica BJ, Woźniak A (2010) An interval method for seeking the Nash equilibria of non-cooperative games. PPAM 2009 proceedings. LNCS 6068: 446–455
[20] Kubica BJ, Woźniak A (2010) Computing Pareto sets of multicriteria problems using interval methods. Presented at SCAN 2010 conference
[21] Moir M, Shavit N (2007) Concurrent data structures. http://www.cs.tau.ac.il/\(\sim\)shanir/concurrent-data-structures.pdf · Zbl 1390.68225
[22] Ratschan S (2002) Continuous first-order constraint satisfaction. LNCS 2385: 181–195 · Zbl 1072.68607
[23] Sharaya IA (2001) On maximal inner estimation of the solution sets of linear systems with interval parameters. Reliab Comput 7: 409–424 · Zbl 1012.65039 · doi:10.1023/A:1011428127620
[24] Shary SP (1996) Algebraic approach to the interval linear static identification, tolerance and control problems, or one more application of Kaucher arithmetic. Reliab Comput 2(1): 3–33 · Zbl 0853.65048 · doi:10.1007/BF02388185
[25] Shary SP (2001) A surprising approach in interval global optimization. Reliab Comput 7: 497–505 · Zbl 0993.65069 · doi:10.1023/A:1014754803382
[26] Shary SP (2002) A new technique in systems analysis under interval uncertainty and ambiguity. Reliab Comput 8: 321–418 · Zbl 1020.65029 · doi:10.1023/A:1020505620702
[27] Shary SP (2010) Konechnomiernyi Intiervalnyi Analiz. XYZ
[28] Toth BG, Kreinovich V (2009) Verified methods for computing Pareto-sets: general algorithmic analysis. Int J Appl Math Comput Sci 19(3): 369–380 · Zbl 1300.90041
[29] Villaverde K, Kreinovich V (1993) A linear-time algorithm that locates local extrema of a function of one variable from interval measurement results. Interval Comput 4: 176–194 · Zbl 0829.65085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.