{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T14:28:41Z","timestamp":1761920921181,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T00:00:00Z","timestamp":1625875200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T00:00:00Z","timestamp":1625875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Spanish Ministry","award":["RTI2018-095993-B-I00"],"award-info":[{"award-number":["RTI2018-095993-B-I00"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Branch and Bound (B&amp;B) algorithms in Global Optimization are used to perform an exhaustive search over the feasible area. One choice is to use simplicial partition sets. Obtaining sharp and cheap bounds of the objective function over a simplex is very important in the construction of efficient Global Optimization B&amp;B algorithms. Although enclosing a simplex in a box implies an overestimation, boxes are more natural when dealing with individual coordinate bounds, and bounding ranges with Interval Arithmetic (IA) is computationally cheap. This paper introduces several linear relaxations using gradient information and Affine Arithmetic and experimentally studies their efficiency compared to traditional lower bounds obtained by natural and centered IA forms and their adaption to simplices. A Global Optimization B&amp;B algorithm with monotonicity test over a simplex is used to compare their efficiency over a set of low dimensional test problems with instances that either have a box constrained search region or where the feasible set is a simplex. Numerical results show that it is possible to obtain tight lower bounds over simplicial subsets.<\/jats:p>","DOI":"10.1007\/s10898-021-01053-8","type":"journal-article","created":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T04:02:28Z","timestamp":1625889748000},"page":"779-804","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On new methods to construct lower bounds in simplicial branch and bound based on interval arithmetic"],"prefix":"10.1007","volume":"80","author":[{"given":"B.","family":"G.-T\u00f3th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. G.","family":"Casado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1572-1436","authenticated-orcid":false,"given":"E. M. T.","family":"Hendrix","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Messine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,10]]},"reference":[{"key":"1053_CR1","first-page":"263","volume":"146","author":"GM Adelson-Velsky","year":"1962","unstructured":"Adelson-Velsky, G.M., Landis, E.M.: An algorithm for the organization of information. Proceed. USSR Acad. Sci. (in Russian) 146, 263\u2013266 (1962)","journal-title":"Proceed. USSR Acad. Sci. (in Russian)"},{"key":"1053_CR2","unstructured":"Andrade, A., Comba, J., Stolfi, J.: Affine arithmetic. International Conf. on Interval and Computer-Algebraic Methods in Science and Engineering (INTERVAL\/94) (1994)"},{"issue":"1","key":"1053_CR3","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/BF01934696","volume":"28","author":"E Baumann","year":"1988","unstructured":"Baumann, E.: Optimal centered forms. BIT Num. Math. 28(1), 80\u201387 (1988). https:\/\/doi.org\/10.1007\/BF01934696","journal-title":"BIT Num. Math."},{"issue":"1\u20134","key":"1053_CR4","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1023\/B:NUMA.0000049462.70970.b6","volume":"37","author":"L de Figueiredo","year":"2004","unstructured":"de Figueiredo, L., Stolfi, J.: Affine arithmetic: concepts and applications. Num. Alg. 37(1\u20134), 147\u2013158 (2004). https:\/\/doi.org\/10.1023\/B:NUMA.0000049462.70970.b6","journal-title":"Num. Alg."},{"key":"1053_CR5","volume-title":"Global Optimization Using Interval Analysis, 2\u00e8me edn","author":"E Hansen","year":"2004","unstructured":"Hansen, E., Walster, W.: Global Optimization Using Interval Analysis, 2\u00e8me edn. Marcel Dekker Inc., New York (2004)"},{"key":"1053_CR6","doi-asserted-by":"publisher","DOI":"10.1063\/1.5089974","author":"EMT Hendrix","year":"2019","unstructured":"Hendrix, E.M.T., Salmer\u00f3n, J.M.G., Casado, L.G.: On function monotonicity in simplicial branch and bound. AIP Conf. Proceed. (2019). https:\/\/doi.org\/10.1063\/1.5089974","journal-title":"AIP Conf. Proceed."},{"key":"1053_CR7","unstructured":"Karhbet, S.D., Kearfott, R.B.: Range bounds of functions over simplices, for branch and bound algorithms. Reliable Computing 25, 53\u201373 (2017). https:\/\/interval.louisiana.edu\/reliable-computing-journal\/volume-25\/reliable-computing-25-pp-053-073.pdf"},{"key":"1053_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2495-0","volume-title":"Rigourous Global Search: Continuous Problems","author":"RB Kearfott","year":"1996","unstructured":"Kearfott, R.B.: Rigourous Global Search: Continuous Problems. Kluwer Academic Publishers, Newyork (1996)"},{"issue":"11","key":"1053_CR9","doi-asserted-by":"publisher","first-page":"992","DOI":"10.3217\/jucs-008-11-0992","volume":"8","author":"F Messine","year":"2002","unstructured":"Messine, F.: Extensions of affine arithmetic: application to unconstrained global optimization. J. Univ. Comput. Sci. 8(11), 992\u20131015 (2002). https:\/\/doi.org\/10.3217\/jucs-008-11-0992","journal-title":"J. Univ. Comput. Sci."},{"issue":"6","key":"1053_CR10","doi-asserted-by":"publisher","first-page":"589","DOI":"10.3217\/jucs-004-06-0589","volume":"4","author":"F Messine","year":"1998","unstructured":"Messine, F., Lagouanelle, J.L.: Enclosure methods for multivariate differentiable functions and application to global optimization. J. Univ. Comput. Sci. 4(6), 589\u2013603 (1998). https:\/\/doi.org\/10.3217\/jucs-004-06-0589","journal-title":"J. Univ. Comput. Sci."},{"issue":"3","key":"1053_CR11","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s11155-006-7217-4","volume":"12","author":"F Messine","year":"2006","unstructured":"Messine, F., Touhami, A.: A general reliable quadratic form: an extension of affine arithmetic. Reliab. Comput. 12(3), 171\u2013192 (2006). https:\/\/doi.org\/10.1007\/s11155-006-7217-4","journal-title":"Reliab. Comput."},{"key":"1053_CR12","doi-asserted-by":"publisher","first-page":"S2373","DOI":"10.1051\/ro\/2020088","volume":"55","author":"O Mohand","year":"2021","unstructured":"Mohand, O.: Tighter bound functions for nonconvex functions over simplexes. RAIRO Oper. Res. 55, S2373\u2013S2381 (2021). https:\/\/doi.org\/10.1051\/ro\/2020088","journal-title":"RAIRO Oper. Res."},{"key":"1053_CR13","volume-title":"Interval Analysis","author":"R Moore","year":"1966","unstructured":"Moore, R.: Interval Analysis. Prentice-Hall Inc., Englewood Cliffs (1966)"},{"issue":"3","key":"1053_CR14","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s10288-014-0269-0","volume":"13","author":"J Ninin","year":"2014","unstructured":"Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13(3), 247\u2013277 (2014). https:\/\/doi.org\/10.1007\/s10288-014-0269-0","journal-title":"4OR"},{"key":"1053_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-9093-7","volume-title":"Simplicial Global Optimization","author":"R Paulavi\u010dius","year":"2014","unstructured":"Paulavi\u010dius, R., \u017dilinskas, J.: Simplicial Global Optimization. Springer, New York (2014)"},{"key":"1053_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10861-0","volume-title":"Automatic differentiation: Techniques and applications","author":"LB Rall","year":"1981","unstructured":"Rall, L.B.: Automatic differentiation: Techniques and applications. Lecture Notes in Computer Science, vol. 120. Springer, Newyork (1981)"},{"key":"1053_CR17","volume-title":"Computer Methods for the Range of Functions","author":"H Ratschek","year":"1984","unstructured":"Ratschek, H., Rokne, J.: Computer Methods for the Range of Functions. Ellis Horwood Ltd, Chichester (1984)"},{"issue":"3","key":"1053_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1587\/nolta.6.341","volume":"6","author":"SM Rump","year":"2015","unstructured":"Rump, S.M., Kashiwagi, M.: Implementation and improvements of affine arithmetic. Nonlin. Theory Appl. 6(3), 341\u2013359 (2015). https:\/\/doi.org\/10.1587\/nolta.6.341","journal-title":"Nonlin. Theory Appl."},{"key":"1053_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9970-y","author":"JMG Salmer\u00f3n","year":"2015","unstructured":"Salmer\u00f3n, J.M.G., Aparicio, G., Casado, L.G., Garc\u00eda, I., Hendrix, E.M.T., Toth, B.G.: Generating a smallest binary tree by proper selection of the longest edges to bisect in a unit simplex refinement. J. Comb. Optim. (2015). https:\/\/doi.org\/10.1007\/s10878-015-9970-y","journal-title":"J. Comb. Optim."},{"key":"1053_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4388-3","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems","author":"H Sherali","year":"1999","unstructured":"Sherali, H., Adams, W.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academis Publishers, Dordrecht (1999)"},{"key":"1053_CR21","doi-asserted-by":"crossref","unstructured":"Sherali, H., Liberti, L.: Reformulation-Linearization Technique for Global Optimization. In: Encyclopedia of Optimization, Springer, New york (2009)","DOI":"10.1007\/978-0-387-74759-0_559"},{"key":"1053_CR22","unstructured":"Stolfi, J., de\u00a0Figueiredo, L.: Self-Validated Numerical Methods and Applications. Monograph for 21st Brazilian Mathematics Colloquium. IMPA\/CNPq (1997)"},{"key":"1053_CR23","unstructured":"Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: Test functions and datasets (2013). http:\/\/www.sfu.ca\/~ssurjano"},{"key":"1053_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-50327-6","volume-title":"The Computation of Fixed Points and Applications","author":"MJ Todd","year":"1976","unstructured":"Todd, M.J.: The Computation of Fixed Points and Applications. Springer, Heidelberg (1976)"},{"issue":"2","key":"1053_CR25","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10898-006-9072-6","volume":"38","author":"B T\u00f3th","year":"2007","unstructured":"T\u00f3th, B., Casado, L.G.: Multi-dimensional pruning from the Baumann point in an Interval Global Optimization Algorithm. J. Glob. Optim. 38(2), 215\u2013236 (2007). https:\/\/doi.org\/10.1007\/s10898-006-9072-6","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1053_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.3846\/1392-6292.2008.13.145-159","volume":"13","author":"J \u017dilinskas","year":"2008","unstructured":"\u017dilinskas, J.: Branch and bound with simplicial partitions for global optimization. Math. Modell. Anal. 13(1), 145\u2013159 (2008). https:\/\/doi.org\/10.3846\/1392-6292.2008.13.145-159","journal-title":"Math. Modell. Anal."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01053-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01053-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01053-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T15:59:21Z","timestamp":1672761561000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01053-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,10]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["1053"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01053-8","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2021,7,10]]},"assertion":[{"value":"1 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}