Ir al contenido

Documat

Impact of domain reduction techniques in polynomial optimization: a computational study

  • Ignacio Gómez-Casares [1] ; Brais González-Rodríguez [1] ; Julio González-Díaz [1] Árbol académico ; Pablo Rodríguez-Fernández [1]
    1. [1] Universidade de Santiago de Compostela

      Universidade de Santiago de Compostela

      Santiago de Compostela, España

  • Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 34, Nº. 1, 2026, págs. 76-101
  • Idioma: inglés
  • DOI: 10.1007/s11750-025-00703-4
  • Enlaces
  • Resumen

    • Domain reduction techniques are at the core of any global optimization solver for NLP or MINLP problems. In this paper, we delve into several of these techniques and assess the impact they may have in the performance of an RLT-based algorithm for polynomial optimization problems. These techniques include (i) the use of (nonlinear) conic relaxations for optimality-based bound tightening, (ii) the use of Lagrangian dual information to enhance feasibility-based bound tightening, and (iii) different strategies for branching point selection. One of this paper’s main contributions is providing insights into the relative impact of these techniques with respect to each other, which we hope will guide the efforts to develop and implement this type of enhancements in other solvers. We also explore how a solver equipped with these domain reduction enhancements can further improve its performance by using machine learning to better choose the best domain reduction approach to use on a given instance.

  • Referencias bibliográficas
    • Achterberg T, Koch T, Martin A (2005) Branching rules revisited. Oper Res Lett 33(1):42–54
    • Baltean-Lugojan R, Bonami P, Misener R, Tramontani A (2019) Scoring positive semidefinite cutting planes for quadratic optimization via trained...
    • Belotti P (2013) Bound reduction using pairs of linear inequalities. J Glob Optim 56(3):787–819
    • Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw...
    • Belotti P, Cafieri S, Lee J, Liberti L (2012) On feasibility based bounds tightening. https://enac.hal.science/ hal-00935464
    • Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290(2):405–421
    • Bonami P, Lodi A, Schweiger J, Tramontani A (2019) Solving quadratic programming by cutting planes. SIAM J Optim 29(2):1076–1105
    • Buchheim C, Wiegele A (2012) Semidefinite relaxations for non-convex quadratic mixed-integer programming. Math Progr 141(1–2):435–452
    • Burer S, Vandenbussche D (2006) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math...
    • Burer S, Ye Y (2020) Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math Progr 181(1):1–17
    • Bussieck MR, Drud AS, Meeraus A (2003) MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J Comput 15:114–119
    • Chen C, Atamturk A, Oren SS (2016) Bound tightening for the alternating current optimal power flow problem. IEEE Trans Power Syst 31(5):3729–3736
    • Coffrin C, Hijazi HL, Van Hentenryck P (2015) Strengthening convex relaxations with bound tightening for power network optimization. In: International...
    • Dalkiran E, Sherali HD (2013) Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global...
    • Dalkiran E, Sherali HD (2016) RLT-POS: Reformulation-linearization technique-based optimization software for solving polynomial programming...
    • Elloumi S, Lambert A (2019) Global solution of non-convex quadratically constrained quadratic programs. Optim Method Softw 34(1):98–114
    • FICO (2023) FICO Xpress optimization. Available at: https://community.fico.com/s/optimization
    • Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, Lodi A, Misener R, Mittelmann H, Sahinidis N, Vigerske S, Wiegele...
    • Ghaddar B, Gómez-Casares I, González-Díaz J, González-Rodríguez B, Pateiro-López B, RodríguezBallesteros S (2023) Learning for spatial branching:...
    • Gleixner AM, Berthold T, Müller B, Weltge S (2017) Three enhancements for optimization-based bound tightening. J Glob Optim 67(4):731–757
    • González-Rodríguez B, Ossorio-Castillo J, González-Díaz J, González-Rueda ÁM, Penas DR, RodríguezMartínez D (2023) Computational advances...
    • González-Rodríguez B, Alvite-Pazó R, Alvite-Pazó S, Ghaddar B, González-Díaz J (2025a) Polynomial optimization: tightening RLT-based branch-and-bound...
    • González-Rodríguez B, Gómez-Casares I, Ghaddar B, González-Díaz J, Pateiro-López B (2025b) Learning in RLT-based spatial branching: limitations...
    • Gupta P, Gasse M, Khalil E, Mudigonda P, Lodi A, Bengio Y (2020) Hybrid models for learning to branch. Adv Neural Inf Process Syst 33:18087–18097
    • Gurobi Optimization (2023) Gurobi optimizer reference manual. Available at: http://www.gurobi.com Jeyakumar V, Li G (2017) Exact conic programming...
    • Kannan R, Nagarajan H, Deka D (2024) Strong partitioning and a machine learning approximation for accelerating the global optimization of...
    • Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796–817
    • Linderoth JT, Savelsbergh MWP (1999) A computational study of search strategies for mixed integer programming. INFORMS J Comput 11(2):173–187
    • Lodi A, Zarpellon G (2017) On learning and branching: a survey. TOP 25(2):207–236
    • Meinshausen N (2006) Quantile regression forests. J Mach Learn Res 7:983–999
    • MOSEK ApS (2022) Introducing the MOSEK Optimization Suite 9.3.20
    • Nie J (2023) Moment and polynomial optimization. SIAM Puranik Y, Sahinidis NV (2017) Domain reduction techniques for global NLP and MINLP...
    • R Core Team (2023) R: a language and environment for statistical computing. R Foundation for Statistical Computing, Vienna
    • Ryoo HS, Sahinidis NV (1996) A branch-and-reduce approach to global optimization. J Glob Optim 8(2):107–138
    • Sahinidis NV (2024) BARON 24.1.30: global optimization of mixed-integer nonlinear programs, user’s manual. https://www.minlp.com/downloads/docs/baron%20manual.pdf
    • Shchetinin D, Rubira TTD, Hug G (2019) Efficient bound tightening techniques for convex relaxations of AC optimal power flow. IEEE Trans Power...
    • Sherali HD, Tuncbilek CH (1992) A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique....
    • Sherali HD, Dalkiran E, Desai J (2011) Enhancing RLT-based relaxations for polynomial programming problems via a new class of v-semidefinite...
    • Sundar K, Nagarajan H, Misra S, Lu M, Coffrin C, Bent R (2018) Optimization-based bound tightening using a strengthened QC-relaxation of the...
    • Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Progr...
    • Wright MN, Ziegler A (2017) ranger: a fast implementation of random forests for high dimensional data in C++ and R. J Stat Softw 77(1):1–17
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno