{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T02:36:08Z","timestamp":1763346968875,"version":"3.38.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T00:00:00Z","timestamp":1732665600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T00:00:00Z","timestamp":1732665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Fondecyt Project","award":["1200035"],"award-info":[{"award-number":["1200035"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In deterministic global optimization, techniques for linear relaxation of a non-convex program are used in the lower bound calculation phase. To achieve this phase, most deterministic global optimization codes use reformulation-linearization techniques. However, there exist also two interval-based polyhedral relaxation techniques which produce reliable bounds without adding new auxiliary variables, and which can take into account mathematical operations and most transcendental functions: (i) the affine relaxation technique, used in the IBBA code, based on affine forms and affine arithmetic, and (ii) the extremal Taylor technique, used in the Ibex-Opt code, which is based on a specific interval-based Taylor form. In this paper, we describe how these two interval-based linear relaxation techniques can be hybridized. These two approaches appear to be complementary, and such a hybrid method performs well on a representative sample of constrained global optimization instances.<\/jats:p>","DOI":"10.1007\/s10898-024-01449-2","type":"journal-article","created":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T01:52:02Z","timestamp":1732672322000},"page":"437-456","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hybridizing two linear relaxation techniques in interval-based solvers"],"prefix":"10.1007","volume":"91","author":[{"given":"Ignacio","family":"Araya","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6457-3321","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Messine","sequence":"additional","affiliation":[]},{"given":"Jordan","family":"Ninin","sequence":"additional","affiliation":[]},{"given":"Gilles","family":"Trombettoni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,27]]},"reference":[{"issue":"1","key":"1449_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: Solving Constraint Integer Programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"key":"1449_CR2","doi-asserted-by":"crossref","unstructured":"Araya, I., Reyes, V., C., O.: More Smear-Based Variable Selection Heuristics for NCSPs. In: Proc. ICTAI, pp. 1004\u20131011 (2013)","DOI":"10.1109\/ICTAI.2013.151"},{"key":"1449_CR3","doi-asserted-by":"crossref","unstructured":"Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval taylor. In: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 1\u201316. Springer (2012)","DOI":"10.1007\/978-3-642-29828-8_1"},{"issue":"2","key":"1449_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10898-014-0145-7","volume":"60","author":"I Araya","year":"2014","unstructured":"Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper Bounding in Inner Regions for Global Optimization under Inequality Constraints. J. Glob. Optim. 60(2), 145\u2013164 (2014)","journal-title":"J. Glob. Optim."},{"issue":"7","key":"1449_CR5","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1002\/aic.11777","volume":"55","author":"A Baharev","year":"2009","unstructured":"Baharev, A., Achterberg, T., R\u00e9v, E.: Computation of an Extractive Distillition Column with Affine Arithmetic. AIChE Journal 55(7), 1695\u20131704 (2009)","journal-title":"AIChE Journal"},{"issue":"4\u20135","key":"1449_CR6","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1080\/10556780903087124","volume":"24","author":"P Belotti","year":"2009","unstructured":"Belotti, P., Lee, J., Liberti, L., Margot, F., W\u00e4chter, A.: Branch and Bounds Tightening Techniques for Non-convex MINLP. Optim. Methods Softw. 24(4\u20135), 597\u2013634 (2009)","journal-title":"Optim. Methods Softw."},{"key":"1449_CR7","unstructured":"Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising Hull and Box Consistency. In: Proceedings of ICLP, pp. 230\u2013244 (1999)"},{"issue":"11","key":"1449_CR8","doi-asserted-by":"publisher","first-page":"1079","DOI":"10.1016\/j.artint.2009.03.002","volume":"173","author":"G Chabert","year":"2009","unstructured":"Chabert, G., Jaulin, L.: Contractor programming. Artif. Intell. 173(11), 1079\u20131100 (2009)","journal-title":"Artif. Intell."},{"key":"1449_CR9","unstructured":"Comba, J., Stolfi, J.: Affine Arithmetic and its Applications to Computer Graphics. In: Proceedings of SIBGRAPI\u201993 - VI Simp\u00f3sio Brasileiro de Computa\u00e7\u00e3o Gr\u00e1fica e Processamento de Imagens, pp. 9\u201318 (1993)"},{"issue":"3","key":"1449_CR10","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1137\/S0036142995281528","volume":"34","author":"T Csendes","year":"1997","unstructured":"Csendes, T., Ratz, D.: Subdivision direction selection in interval methods for global optimization. Siam J. Numer. Anal. 34(3), 922\u2013938 (1997)","journal-title":"Siam J. Numer. Anal."},{"key":"1449_CR11","unstructured":"Debruyne, R., Bessi\u00e8re, C.: Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In: Proc. IJCAI, pp. 412\u2013417 (1997)"},{"issue":"2","key":"1449_CR12","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"1449_CR13","unstructured":"de\u00a0Figueiredo, L.: Surface Intersection using Affine Arithmetic. In: Proceedings of Graphics Interface\u201996, pp. 168\u2013175 (1996)"},{"issue":"5","key":"1449_CR14","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1111\/1467-8659.1550287","volume":"15","author":"L de Figueiredo","year":"1996","unstructured":"de Figueiredo, L., Stolfi, J.: Adaptive Enumeration of Implicit Surfaces with Affine Arithmetic. Computer Gr. Forum 15(5), 287\u2013296 (1996)","journal-title":"Computer Gr. Forum"},{"issue":"1\u20134","key":"1449_CR15","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. Numerical Algorithms 37(1\u20134), 147\u2013158 (2004)","journal-title":"Numerical Algorithms"},{"key":"1449_CR16","doi-asserted-by":"crossref","unstructured":"G., C.L., Martinez, Garcia, E.M.T, H.: Branch-and-Bound interval global optimization on shared memory multiprocessors. Optimization Methods and Software 23(5), 689\u2013701 (2008)","DOI":"10.1080\/10556780802086300"},{"issue":"3","key":"1449_CR17","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1137\/S1052623402416839","volume":"14","author":"C Jansson","year":"2004","unstructured":"Jansson, C.: Rigorous lower and upper bounds in linear programming. SIAM J. Optim. 14(3), 914\u2013935 (2004)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1449_CR18","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/030602186","volume":"16","author":"R Kearfott","year":"2005","unstructured":"Kearfott, R., Hongthong, S.: Validated Linear Relaxations and Preprocessing: Some Experiments. Siam J. Optim. 16(2), 418\u2013433 (2005)","journal-title":"Siam J. Optim."},{"key":"1449_CR19","doi-asserted-by":"crossref","unstructured":"Kearfott, R.B.: Rigourous Global Search: Continuous Problems. Kluwer Academic Publishers (1996)","DOI":"10.1007\/978-1-4757-2495-0"},{"issue":"1\u20134","key":"1449_CR20","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/B:NUMA.0000049468.03595.4c","volume":"37","author":"LV Kolev","year":"2004","unstructured":"Kolev, L.V.: An Improved Interval Linearization for Solving Nonlinear Problems. Numerical Algorithms 37(1\u20134), 213\u2013224 (2004)","journal-title":"Numerical Algorithms"},{"key":"1449_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s10601-004-5307-7","volume":"10","author":"Y Lebbah","year":"2005","unstructured":"Lebbah, Y., Michel, C., Rueher, M.: A Rigorous Global Filtering Algorithm for Quadratic Constraints. Constraints 10, 47\u201365 (2005)","journal-title":"Constraints"},{"key":"1449_CR22","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/j.cam.2005.08.037","volume":"199","author":"Y Lebbah","year":"2007","unstructured":"Lebbah, Y., Michel, C., Rueher, M.: An Efficient and Safe Framework for Solving Optimization Problems. J. Comput. Appl. Math. 199, 372\u2013377 (2007)","journal-title":"J. Comput. Appl. Math."},{"issue":"5","key":"1449_CR23","doi-asserted-by":"publisher","first-page":"2076","DOI":"10.1137\/S0036142903436174","volume":"42","author":"Y Lebbah","year":"2005","unstructured":"Lebbah, Y., Michel, C., Rueher, M., Daney, D., Merlet, J.: Efficient and Safe Global Constraints for Handling Numerical Constraint Systems. SIAM J. Numerical Anal. 42(5), 2076\u20132097 (2005)","journal-title":"SIAM J. Numerical Anal."},{"key":"1449_CR24","unstructured":"Messine, F.: M\u00e9thodes d\u2019optimisation globale bas\u00e9es sur l\u2019analyse d\u2019intervalle pour la r\u00e9solution des probl\u00e8mes avec contraintes. Ph.D. thesis, LIMA-IRIT-ENSEEIHT-INPT, Toulouse (1997)"},{"issue":"11","key":"1449_CR25","first-page":"992","volume":"8","author":"F Messine","year":"2002","unstructured":"Messine, F.: Extensions of Affine Arithmetic: Application to Unconstrained Global Optimization. J. Univer. Computer Sci. 8(11), 992\u20131015 (2002)","journal-title":"J. Univer. Computer Sci."},{"key":"1449_CR26","doi-asserted-by":"crossref","unstructured":"Messine, F.: A Deterministic Global Optimization Algorithm for Design Problems. In: C.\u00a0Audet, P.\u00a0Hansen, G.\u00a0Savard (eds.) Essays and Surveys in Global Optimization, pp. 267\u2013294. Springer (2005)","DOI":"10.1007\/0-387-25570-2_10"},{"issue":"1","key":"1449_CR27","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1109\/20.650361","volume":"34","author":"F Messine","year":"1998","unstructured":"Messine, F., Nogar\u00e8de, B., Lagouanelle, J.L.: Optimal design of electromechanical actuators: A new method based on global optimization. IEEE Trans. Magn. 34(1), 299\u2013308 (1998)","journal-title":"IEEE Trans. Magn."},{"issue":"3","key":"1449_CR28","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. Reliable Comput. 12(3), 171\u2013192 (2006)","journal-title":"Reliable Comput."},{"issue":"2\u20133","key":"1449_CR29","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s10898-014-0166-2","volume":"59","author":"R Misener","year":"2014","unstructured":"Misener, R., Floudas, C.: ANTIGONE: Algorithms for coNTinuous \/ Integer Global Optimization of Nonlinear Equations. J. Global Optim. 59(2\u20133), 503\u2013526 (2014)","journal-title":"J. Global Optim."},{"key":"1449_CR30","volume-title":"Interval Anal.","author":"R Moore","year":"1966","unstructured":"Moore, R.: Interval Anal. Prentice-Hall Inc., Englewood Cliffs (1966)"},{"key":"1449_CR31","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10107-003-0433-3","volume":"99","author":"A Neumaier","year":"2004","unstructured":"Neumaier, A., Shcherbina, O.: Safe Bounds in Linear and Mixed-Integer Programming. Math. Program. 99, 283\u2013296 (2004)","journal-title":"Math. Program."},{"issue":"4","key":"1449_CR32","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/s10601-015-9180-3","volume":"20","author":"B Neveu","year":"2015","unstructured":"Neveu, B., Trombettoni, G., Araya, I.: Adaptive Constructive Interval Disjunction: Algorithms and Experiments. Constraints J. 20(4), 452\u2013467 (2015)","journal-title":"Constraints J."},{"key":"1449_CR33","doi-asserted-by":"crossref","unstructured":"Neveu, B., Trombettoni, G., et\u00a0al.: Adaptive constructive interval disjunction. In: 25th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 900\u2013906 (2013)","DOI":"10.1109\/ICTAI.2013.138"},{"key":"1449_CR34","unstructured":"Ninin, J.: Optimisation Globale bas\u00e9 sur l\u2019Analyse d\u2019Intervalles: Relaxation affine et limitation de la m\u00e9moire. Ph.D. thesis, Institut National Polytechnique de Toulouse (2010)"},{"key":"1449_CR35","doi-asserted-by":"crossref","unstructured":"Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13(3), 247\u2013277 (2014)","DOI":"10.1007\/s10288-014-0269-0"},{"issue":"4\u20135","key":"1449_CR36","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1080\/10556780902753395","volume":"24","author":"L P\u00e1l","year":"2009","unstructured":"P\u00e1l, L., Csendes, T.: INTLAB implementation of an interval global optimization algorithm. Optim. Methods Softw. 24(4\u20135), 749\u2013759 (2009)","journal-title":"Optim. Methods Softw."},{"key":"1449_CR37","unstructured":"Schrage, L.: Optimization Modeling With Lindo. Brooks\/Cole (1997)"},{"key":"1449_CR38","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-540-39901-8_16","volume-title":"Global Optim. Constr. Satisfaction","author":"O Shcherbina","year":"2003","unstructured":"Shcherbina, O., Neumaier, A., Sam-Haroud, D., Vu, X.H., Nguyen, T.V.: Benchmarking global optimization and constraint satisfaction codes. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optim. Constr. Satisfaction, pp. 211\u2013222. Springer, Berlin Heidelberg, Berlin, Heidelberg (2003)"},{"key":"1449_CR39","doi-asserted-by":"crossref","unstructured":"Sherali, H., Liberti, L.: Reformulation-Linearization Technique for Global Optimization. In: Encyclopedia of Optimization, vol.\u00a018, pp. 3263\u20133268. Springer-Verlag (2009)","DOI":"10.1007\/978-0-387-74759-0_559"},{"key":"1449_CR40","unstructured":"Stolfi, J., de\u00a0Figueiredo, L.: Self-Validated Numerical Methods and Applications. Monograph for 21st Brazilian Mathematics Colloquium. IMPA\/CNPq (1997)"},{"issue":"2","key":"1449_CR41","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-005-0581-8","volume":"103","author":"M Tawarmalani","year":"2005","unstructured":"Tawarmalani, M., Sahinidis, N.V.: A Polyhedral Branch-and-Cut Approach to Global Optimization. Math. Program. 103(2), 225\u2013249 (2005)","journal-title":"Math. Program."},{"key":"1449_CR42","doi-asserted-by":"crossref","unstructured":"Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner Regions and Interval Linearizations for Global Optimization. In: AAAI, pp. 99\u2013104 (2011)","DOI":"10.1609\/aaai.v25i1.7817"},{"key":"1449_CR43","doi-asserted-by":"crossref","unstructured":"Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Principles and Practice of Constraint Programming (CP), pp. 635\u2013650. Springer (2007)","DOI":"10.1007\/978-3-540-74970-7_45"},{"key":"1449_CR44","doi-asserted-by":"crossref","unstructured":"Van\u00a0Hentenryck, P., Michel, L., Deville, Y.: Numerica : A Modeling Language for Global Optimization. MIT Press (1997)","DOI":"10.7551\/mitpress\/5073.001.0001"},{"issue":"3","key":"1449_CR45","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10472-009-9129-6","volume":"55","author":"XH Vu","year":"2009","unstructured":"Vu, X.H., Sam-Haroud, D., Faltings, B.: Enhancing numerical constraint propagation using multiple inclusion representations. Annals Math. Artificial Intell. 55(3), 295\u2013354 (2009)","journal-title":"Annals Math. Artificial Intell."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01449-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01449-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01449-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,26]],"date-time":"2025-02-26T06:11:40Z","timestamp":1740550300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01449-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,27]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["1449"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01449-2","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,11,27]]},"assertion":[{"value":"28 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}