Reducciones de dominio en optimización matemática mediante ajustes de cotas

Traballo Fin de Grao Reducciones de dominio en optimización matemática mediante ajustes de cotas SERGIO RODRÍGUEZ DELGADO 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Reducciones de dominio en optimización matemática mediante ajustes de cotas SERGIO RODRÍGUEZ DELGADO Julio, 2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estatística e Investigación Operativa Título: Reducciones de dominio en optimización matemática mediante ajustes de cotas Breve descrición do contido A la hora de buscar óptimos globales en problemas de optimización matemática no convexos, la mayoría de los algoritmos suelen basarse en técnicas de ramicación y acotación. De manera directa o indirecta, estas técnicas buscan subdividir la región factible del problema original en subregiones, de tal manera que al nal se pueda explorar toda la región factible del problema original mediante la resolución de subproblemas más sencillos. El rendimiento de estas técnicas depende fuertemente del tamaño del dominio original y, por tanto, es habitual complementarlas con técnicas de reducción de dominio. Una de las formas más habituales de llevar esto acabo es realizando ajustes de cotas, conocidas como bound tightening por su nombre en inglés, que buscan anar las cotas disponibles para cada variable estudiando las implicaciones que el resto de restricciones y cotas tienen sobre las mismas. iii Índice general Resumen vii Introducción ix 1. Preliminares 1 1.1. Introducción a la Optimización Matemática .................. 1 1.2. Dualidad en Programación Lineal ........................ 2 2. FBBT. Feasibility-Based Bound Tightening 5 2.1. FBBT en Restricciones Lineales ......................... 5 2.1.1. Ajustes en las Cotas de Variables .................... 6 2.1.2. Ajuste de Lados Derechos ........................ 7 2.2. FBBT con Pares de Restricciones Lineales ................... 9 2.3. FBBT mediante Aritmética de Intervalos .................... 14 2.3.1. Aritmética de Intervalos. Introducción y Propiedades. Operaciones con Aritmética de Intervalos. Funciones de Intervalos ......... 15 2.3.2. FBBT. Propagación de las Cotas .................... 19 3. OBBT. Optimization-Based Bound Tightening 29 3.1. OBBT Clásico .................................. 29 3.2. OBBT en Problemas Lineales. Relajación One-Row .............. 30 3.2.1. Cotas de Variables Duales ........................ 30 3.2.2. OBBT vía FBBT ............................. 34 4. Implementación y Resultados Numéricos 37 4.1. Marco de la Programación ............................ 37 4.2. Rendimiento Estático ............................... 38 4.3. Performance Proles ............................... 42 4.4. Rendimiento Dinámico .............................. 44 Referencias 51 v Resumen El objetivo de este trabajo es realizar una recopilación de métodos de reducción de dominio en problemas de optimización mediante ajustes de cotas y, posteriormente, realizar un análisis numérico del rendimiento que estos métodos tienen sobre problemas de optimización concretos. Se presentan también algunas mejoras o alternativas que pueden resultar ecaces en dichos métodos, en función de los tipos de restricciones que presente el problema. Abstract The aim of this project is to conduct a review of some domain reduction techniques in optimization problems by bound tightening and, subsequently, to carry out a numerical analysis of the performance that these methods have over particular optimization problems. Furthermore, some improvements and alternatives to these techniques are presented. They may be eective depending on the kind of constraints that the problem presents. vii 4 CAPÍTULO 1. PRELIMINARES Corolario 1.3. Dado un par de problemas duales entre sí (P) y (D), y x y π soluciones factibles del primal y dual respectivamente tales que cTx=πTb , entonces x y π son soluciones óptimas de primal y dual respectivamente. Corolario 1.4. Dado un par de problemas duales entre sí (P) y (D), si la función objetivo de uno de ellos es no acotada, entonces el otro no tiene soluciones factibles. Teorema 1.5 (Dualidad fuerte) . Dado un par de problemas duales entre sí (P) y (D), si uno de ellos tiene una solución óptima, entonces el otro tiene también solución óptima y los valores óptimos de la función objetivo coinciden. En particular, si x y π son soluciones óptimas de (P) y (D) respectivamente, se tiene que cTx=πTb. Demostración. La demostración de este resultado puede encontrarse en González-Díaz (2018). Teorema 1.6 (Teorema de las holguras complementarias) . Dado un par de problemas duales (P) y (D) y un par de soluciones factibles x y π . Entonces x y π forman un par de soluciones óptimas si y solo si: πk(Ax −b)k= 0,∀k= 1, . . . , p ; (c−πTA)jxj= 0,∀j= 1,...,n. Demostración. La demostración de este resultado puede encontrarse en González-Díaz (2018). Este resultado implica que, dado un par de óptimos x y π de un par de problemas de programación lineal duales entre sí, si una restricción del dual no se satura, entonces la correspondiente variable del primal será 0. Análogamente, si una variable no negativa es estrictamente positiva, entonces la desigualdad correspondiente en el dual estará saturada. Capítulo 2 FBBT. Feasibility-Based Bound Tightening El Feasibility-Based Bound Tightening , o Ajuste de Cotas Basados en Factibilidad, (en adelante FBBT) es un procedimiento de ajuste de cotas en problemas de optimización basado en las restricciones del problema. Trata de estudiar si es posible mejorar las cotas de las variables de dicho problema basándose en su factibilidad, esto es, en que se cumplan las restricciones del mismo. En Puranik y Sahinidis (2017), Belotti (2013), Belotti y otros (2012) y Messine (2004) se tratan las cuestiones que se desarrollarán a lo largo de este capítulo. Sea el problema de optimización:              minimizar g0(x) sujeto a gi(x)≥bi, i = 1, . . . , m x≡(x1, . . . , xn)∈Rn xL k≤xk≤xU k, k = 1, . . . , n (2.1) En adelante serán estudiadas varias técnicas de FBBT en función del tipo de restricciones que presente el problema. 2.1. FBBT en Restricciones Lineales En el caso de restricciones lineales se pueden obtener expresiones directas de las cotas de las variables o de los lados derechos de las restricciones, simplemente mediante operaciones en la restricción. 5 6 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING 2.1.1. Ajustes en las Cotas de Variables En este caso, es posible obtener una expresión directa de las cotas de las variables operando con dichas restricciones. Sea una variable xj en una restricción de un problema de optimización. Si la restricción es de tipo  ≥  y la variable tiene coeciente positivo, es posible obtener una candidata a nueva cota inferior; en cambio, si la variable tiene coeciente negativo, es posible obtener una candidata a nueva cota superior. De manera general, sea una restricción lineal del problema (2.1) de la forma n X j=1 ajxj≥b, xL j≤xj≤xU j, j = 1, . . . , n, y sea N:= {1, . . . , n}. Se tienen, para j∈N , las siguientes desigualdades: aj>0, xj≥1 aj b− n X k=1,k6=j m´ax{akxU k, akxL k} , (2.2) aj<0, xj≤1 aj b− n X k=1,k6=j m´ax{akxU k, akxL k} . (2.3) Deniendo P+:= {j∈N:aj>0}y P−:= {j∈N:aj<0}, es posible reescribir las desigualdades (2.2) y (2.3) como sigue: ∀j∈P+, xj≥1 aj b−X k∈P+\{j} akxU k−X k∈P−\{j} akxL k , (2.4) ∀j∈P−, xj≤1 aj b−X k∈P+\{j} akxU k−X k∈P−\{j} akxL k . (2.5) Ejemplo 2.1. Dada la restricción 2x1−2x2−3x3≥ −6, 2.1. FBBT EN RESTRICCIONES LINEALES 7 con x1∈[xL 1, xU 1] = [−12,4] , x2∈[xL 2, xU 2] = [−2,10] y x3∈[xL 3, xU 3] = [0,12] , veamos si es posible ajustar las cotas de las variables. Para este ejemplo se tienen: P+={1}y P−={2,3}. Para x1 , aplicando la fórmula (2.4), se tiene: x1≥1 2·(−6−(−2·(−2) −3·0)) = −10 2=−5>−12 = xL 1 Por tanto, empleando la restricción, podemos ajustar la cota inferior de la variable x1 a ¯xL 1=−5 . Para x2 , aplicando la fórmula (2.5), se tiene: x2≤ −1 2·(−6−(2 ·4−3·0)) = −−1 2·(−14) = 7 <10 = xU 2, por lo que podemos ajustar su cota superior a ¯xU 2= 7 . Para x3 procedemos de manera análoga: x3≤ −1 3·(−6−(2 ·4−2·(−2))) = −1 3·(−18) = 6 <12 = xU 3, por lo que podemos ajustar de nuevo su cota superior a ¯xU 3= 6 . 2.1.2. Ajuste de Lados Derechos Sea una restricción lineal del problema (2.1) de la forma n X j=1 ajxj≥b, xL j≤xj≤xU j, j = 1, . . . , n. La restricción n X j=1 ajxj≥b0, con b0:= m´ax nm´ın Pn j=1 ajxj, bo, es igualmente válida y podrá ser, en general, más restrictiva. El cálculo de m´ın Pn j=1 ajxj se hará de la siguiente manera: 8 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING m´ın n X j=1 ajxj=X j∈P+ ajxL j+X j∈P− ajxU j, siempre que las cotas implicadas sean nitas. Si la restricción es de la forma: n X j=1 ajxj≤b, entonces, de manera análoga, se tiene que la restricción n X j=1 ajxj≤b0, con b0:= m´ın nm´ax Pn j=1 ajxj, bo, es igualmente válida y podrá ser, en general, más restrictiva. El cálculo de m´ax Pn j=1 ajxj se hará de la siguiente manera: m´ax n X j=1 ajxj=X j∈P+ ajxU j+X j∈P− ajxL j, siempre que las cotas implicadas sean nitas. Ejemplo 2.2. Dada la restricción x1−2x2+x3≤8, con x1∈[xL 1, xU 1]=[−1,2] , x2∈[xL 2, xU 2] = [0,1] y x3∈[xL 3, xU 3]=[−1,4] , veamos si es posible ajustar más el lado derecho. Aplicando lo anterior, el máximo se obtiene de la siguiente manera: xU 1−2xL 2+xU 3= 2 −2·0 + 4 = 6 <8, por lo que es posible ajustar más el lado derecho, obteniéndose la nueva restricción x1−2x2+x3≤6, que es más restrictiva. 2.2. FBBT CON PARES DE RESTRICCIONES LINEALES 9 2.2. FBBT con Pares de Restricciones Lineales Dado un par de restricciones lineales de un problema de optimización, una combinación convexa de ellas será una restricción que también se deberá vericar. De esto tratará esta sección, dadas dos restricciones lineales, considerar una combinación convexa entre ellas y estudiar cómo deberá ser dicha combinación para que ajuste las cotas de las variables implicadas lo máximo posible. Sean dos restricciones lineales del problema (2.1) de la forma: n X j=1 ajxj≥b, n X j=1 eajxj≥e b, (2.6) y sea N:= {1, . . . , n} . La combinación convexa de las restricciones anteriores, denida para un parámetro λ∈[0,1] , es: λ n X j=1 ajxj+ (1 −λ) n X j=1 eajxj≥λb + (1 −λ)e b, y operando se tiene: n X j=1 (λaj+ (1 −λ)eaj)xj≥λb + (1 −λ)e b, una nueva restricción para cada λ∈[0,1] , que igualmente el problema deberá satisfacer. Sean: ¯aj(λ) :=λaj+ (1 −λ)eaj, ¯ b(λ) :=λb + (1 −λ)e b. Con esta notación la restricción se escribe: n X i=1 ¯aj(λ)xj≥¯ b(λ). Sean ahora los conjuntos: P+(λ) := {j∈N: ¯aj(λ)>0}y P−(λ) := {j∈N: ¯aj(λ)<0}. En base a lo realizado en el apartado anterior, sean: Lj(λ) := ¯ b(λ)−X k∈P+(λ)\{j} ¯ak(λ)xU k−X k∈P−(λ)\{j} ¯ak(λ)xL k, Uj(λ) := ¯ b(λ)−X k∈P+(λ)\{j} ¯ak(λ)xU k−X k∈P−(λ)\{j} ¯ak(λ)xL k. 10 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING Por tanto, para cada λ∈[0,1] se tienen las siguientes cotas: ∀j∈P+(λ), xj≥Lj(λ) ¯aj(λ), ∀j∈P−(λ), xj≤Uj(λ) ¯aj(λ), en analogía con las desigualdades (2.4) y (2.5). Ejemplo 2.3. Sean las dos restricciones lineales siguientes: x1+x2+x3≥3, x1−x2+x3≥2, con (x1, x2, x3)∈[−1,3] ×[−1,1] ×[0,1] . De las desigualdades obtenidas en el (2.4) y (2.5) se tienen las cotas: x1+x2+x3≥3 =⇒x1≥3−xU 2−xU 3= 3 −1−1=1, x1−x2+x3≥2 =⇒x1≥3 + xL 2−xU 3= 3 −1−1=0, de donde se puede deducir que xL 1= 1 . Sea ahora una combinación convexa para ambas restricciones, con λ∈[0,1] : λ(x1+x2+x3) + (1 −λ)(x1−x2+x3)≥3λ+ 2(1 −λ) =⇒x1+ (2λ−1)x2+x3≥λ+ 2, y veamos si se puede encontrar una cota inferior mayor para la variable x1 . λ=3 4 : x1+1 2x2+x3≥11 4=⇒x1≥11 4−1 2xU 2−xU 3=11 4−1 2·1−1 = 5 4>1. λ=1 2 : x1+x3≥5 2=⇒x1≥5 2−xU 3=5 2−1 = 3 2>5 4>1. De este ejemplo se deduce que es posible encontrar mejores cotas inferiores para x1 combinando ambas restricciones que con cada restricción por separado, pero la optimalidad de dicha cota dependerá del valor de λ escogido. 2.2. FBBT CON PARES DE RESTRICCIONES LINEALES 11 Proposición 2.4. Las funciones Lj(λ) y Uj(λ) son continuas para λ∈R . Demostración. Es suciente probarlo para Lj(λ) , ya que será análogo para Uj(λ) . l´ım →0Lj(λ+)−Lj(λ) = l´ım →0 ¯ b(λ+)−¯ b(λ) −X k∈N\{j}:¯ak(λ+ε)>0,¯ak(λ)>0 (¯ak(λ+ε)−¯ak(λ))xU k −X k∈N\{j}:¯ak(λ+ε)<0,¯ak(λ)<0 (¯ak(λ+ε)−¯ak(λ))xL k −X k∈N\{j}:¯ak(λ+ε)>0,¯ak(λ)<0 (¯ak(λ+ε)xU k−¯ak(λ)xL k) −X k∈N\{j}:¯ak(λ+ε)<0,¯ak(λ)>0 (¯ak(λ+ε)xL k−¯ak(λ)xU k) = l´ım →0ε(b−e b) (2.7) −X k∈N\{j}:¯ak(λ+ε)>0,¯ak(λ)>0 (ε(ak−eak))xU k (2.8) −X k∈N\{j}:¯ak(λ+ε)<0,¯ak(λ)<0 (ε(ak−eak))xL k (2.9) −X k∈N\{j}:¯ak(λ+ε)>0,¯ak(λ)<0 (¯ak(λ+ε)xU k−¯ak(λ)xL k) (2.10) −X k∈N\{j}:¯ak(λ+ε)<0,¯ak(λ)>0 (¯ak(λ+ε)xL k−¯ak(λ)xU k). (2.11) Mientras que (2.7), (2.8) y (2.9) tienen a 0 a la vez que ε , los términos (2.10) y (2.11) se anulan entre ellos a medida que ε→0 ya que ¯ak(λ+ε) y ¯ak(λ) tienen signo opuesto en dichas expresiones. En conclusión, el límite es nulo para cualquier λ y por tanto Lj(λ) es continua. Analógamente se tiene la demostración para Uj(λ) . Observación 2.5 . Las funciones Lj(λ) y Uj(λ) no son diferenciables en general para λ∈[0,1] . Para encontrar, por tanto, posibles cotas más ajustadas de xj combinando pares de restricciones lineales, es posible resolver los problemas de optimización con función objetivo 12 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING racional y a trozos siguiente: ¯xL j= m´ax Lj(λ) ¯aj(λ):λ∈(0,1),¯aj(λ)>0, (2.12) ¯xU j= m´ın Uj(λ) ¯aj(λ):λ∈(0,1),¯aj(λ)<0. (2.13) Las nuevas cotas de la variable xj serán [xL j, xU j]∩[¯xL j,¯xU j] . Estos dos problemas pueden ser complicados de resolver. No obstante, para resolverlos más fácilmente, es posible restringir los valores de λ∈(0,1) a un subconjunto nito de valores (como arma el siguiente resultado). Proposición 2.6. Todas las soluciones óptimas de los problemas (2.12) y (2.13) están en el conjunto Λ := {λ∈(0,1) : (∃j∈ {1,2, . . . , n}| ¯aj(λ) = 0)}. Demostración. Se probará exclusivamente la igualdad (2.12), ya que para la igualdad (2.13) se hace de manera análoga. Reescribiendo ¯aj(λ) := λaj+ (1 −λ)eaj como rλ +s , se tiene r=aj−eaj y s=eaj . Sea r < 0 sin pérdida de generalidad. Por la condición ¯aj(λ) = rλ +s > 0 con r < 0 se tiene λ < −s r por lo que Lj(λ) ¯aj(λ) es una cota inferior válida para xj si λ∈[0,¯ λ] con ¯ λ:= m´ın{1,−s r} . El conjunto Λ = {λ∈(0,1) : (∃j∈ {1,2, . . . , n}| ¯aj(λ) = 0)} contiene todos los puntos de corte de la función a trozos Lj(λ) ¯aj(λ) , es decir, valores de λ para los que algún ¯ak(λ)=0 . Así es posible reescribir Λ = {λ1, λ2, . . . , λp} con 0 = λ0< λ1≤λ2≤ ··· ≤ λp≤1 . Restringiendo λ≤¯ λ para que se verique la condición de signo de ¯aj(λ) , es posible denir la función a trozos Lj(λ) ¯aj(λ) en Λ∩[0,¯ λ] = {λ1, λ2, . . . , λk} con k≤p como sigue: Lj(λ) ¯aj(λ)=              α0λ+β0 rλ+s, si λ∈(0, λ1] α1λ+β1 rλ+s, si λ∈(λ1, λ2] . . . αkλ+βk rλ+s, si λ∈(λk,¯ λ] 2.2. FBBT CON PARES DE RESTRICCIONES LINEALES 13 siendo αh=b−e b−Pk∈P+(λh)\{j}(ak−eak)xU k−Pk∈P−(λh)\{j}(ak−eak)xL k y βh=e b−Pk∈P+(λh)\{j}eakxU k−Pk∈P−(λh)\{j}eakxL k , para h= 0,1,2, . . . , k . Dado que αhλ+βh rλ+s es cociente de dos funciones anes, no admite máximo local en los intervalos (λh, λh+1) para h= 0,1,2, . . . , k , siendo λk+1 =¯ λ (ya que la derivada del cociente de dos funciones anes tiene signo constante y, por tanto, no admite extremos en el interior del intervalo de denición), por lo que el máximo se alcanza en Λ . De manera similar se demuestra el caso r > 0 , donde Λ es un subconjunto nito del intervalo [¯ λ, 1] , con ¯ λ= m´ax{0,−s r} . La demostración para (2.13) es análoga. Corolario 2.7. El par de inecuaciones (2.6) ajusta la cota de una variable solamente si existe, al menos, una variable xj cuyos coecientes aj y eaj en las restricciones sean no nulos y tengan signo opuesto, esto es: ∃j∈N:ajeaj<0. Demostración. Supongamos que los coecientes aj y eaj tienen el mismo signo ∀j∈N . En ese caso se tiene, para λ∈[0,1] : aj,eaj>0, λaj+ (1 −λ)eaj>0, aj,eaj<0, λaj+ (1 −λ)eaj<0. Por tanto, el conjunto Λ denido anteriormente es vacío, y por la Proposición 2.6 no hay ajuste de cotas. En el siguiente ejemplo se pone de maniesto la Proposición 2.6. Ejemplo 2.8 (Basado en un ejemplo de Belotti (2013)) . Considérense las restricciones: 15x1+ 2x2+x3−2x4≥4 y −x1−2x2−6x3+x4≥5, 20 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING 3. Procedimiento Root to Leaf , de la raíz a las hojas. Consiste en descender por el árbol, desde la raíz a las hojas, propagando ahora la cota actualizada de la restricción a las variables. En cada nodo se realizan los cálculos intermedios para deducir las cotas de la expresión de cada nodo, intersecándose con las cotas calculadas en el apartado 2 (proceso Leaf to Root ), para así nalmente obtener las cotas óptimas de las variables. Para deducir las cotas de un nodo se deberá realizar la operación inversa a la que aparezca en el nodo superior al jado, operando el intervalo que se está propagando con el resto de nodos que estén al mismo nivel que el jado y que dependan del mismo nodo superior. 4. Actualizar las cotas de las variables, y proceder con la siguiente restricción. Una vez se hayan realizado los cálculos con todas las restricciones, calcular también el número de variables a la que se le ha modicado su cota (más de una tolerancia jada) y, en caso de ser no nulo, aplicar nuevamente el algoritmo al problema. En los siguientes ejemplos se pone de maniesto el ajuste de cotas dado por el Algoritmo 2.19 de FBBT. Ejemplo 2.20 (Basado en un ejemplo de Messine (2004)) . Ajuste de cotas en las variables x1∈[1,3] , x2∈[1,3] y x3∈[1,3] vericando la restricción x1+ 2x2·x3= 3 empleando el Algoritmo 2.19 de FBBT. Primeramente se presenta el árbol de la restricción y se realiza el proceso Leaf to Root . Se tiene: 2.3. FBBT MEDIANTE ARITMÉTICA DE INTERVALOS 21 + x1· 2x2·x3 x2x3 [1,3] x1+ 2x2·x3∈[3,3] [1,3] [1,3] Imagen 2.2: Árbol de la restricción asociada (con cotas de variables y restricciones). + x1· 2x2·x3 x2x3 [1,3] x1+ 2x2·x3∈[3,3] [1,3] [1,3] [1,3] ·[1,3] = [1,9] 2·[1,9] = [2,18][1,3] [1,3] + [2,18] = [3,21] Imagen 2.3: Leaf to Root . Una vez realizado el proceso Leaf to Root se procede a realizar el Root to Leaf , para propagar las cotas a las variables. + x1· 2x2·x3 x2x3 [1,1] x1+ 2x2·x3 [1,1] [1,1] [3,21]∩[3,3] = [3,3] ([3,3] −[2,18]) ∩[1,3] [−15,1] ∩[1,3] = [1,1] ([3,3] −[1,3]) ∩[2,18] = [0,2] ∩[2,18] = [2,2] [2,2] 2∩[1,9] = [1,1] ∩[1,9] = [1,1] [1,1] [1,3] ∩[1,3] = [ 1 3,1] ∩[1,3] = [1,1] [1,1] [1,3] ∩[1,3] = [ 1 3,1] ∩[1,3] = [1,1] Imagen 2.4: Root to Leaf . Una vez realizado el ajuste de cotas se observa que el único valor factible para que se verique la restricción es, para las tres variables, x1=x2=x3= 1 . Nuevas aplicaciones del algoritmo no mejorarán más las cotas. 22 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING Sea Z⊆X el nuevo subconjunto de Rn de cotas de las variables x1, . . . , xn , resultante de la propagación de una restricción g(x) sobre X mediante el Algoritmo 2.19 y sea G la función inclusión y extensión en intervalos de g(x) denida mediante análisis de intervalos. Proposición 2.21. Si u∈Z entonces g(u)∈G(Z) y recíprocamente, si u∈X y g(u)∈ G(Z) , entonces u∈Z . Demostración. La demostración puede encontrarse en Messine (2004). Proposición 2.22. G(Z)⊆G(X) y G(X)∩[g(x)L, g(x)U]⊆G(Z) . Demostración. La demostración puede encontrarse en Messine (2004). Teorema 2.23 (Validación del Algoritmo 2.19) . No existe u∈X que verique una restricción considerada g(x) tal que u /∈Z (siendo Z el resultado de la propagación de la restricción g(x) sobre las cotas originales X empleando el Algoritmo 2.19 ). Demostración. Supongamos que ∃u∈X, u /∈Z . Entonces por la Proposición 2.21 se tiene que g(u)/∈G(Z) . De esta manera, por la Proposición 2.22, como G(X)∩[g(x)L, g(x)U]⊆G(Z), entonces g(u)/∈G(X)∩[g(x)L, g(x)U] =⇒g(u)/∈G(X) o g(u)/∈[g(x)L, g(x)U]. Dado que además se tiene por denición que g(u)∈G(X) entonces g(u)/∈[g(x)L, g(x)U] y así u no verica la restricción g(x) . Observación 2.24 . El Teorema anterior demuestra que el Algoritmo 2.19 permite encontrar cotas de manera correcta, ya que no es posible encontrar u∈X tal que u verique g(x) (esto es, g(u)∈[g(x)L, g(x)U] ), pero u /∈Z . Ejemplo 2.25 (Aplicación del Algoritmo 2.19) . Ajuste de cotas de las variables x1∈[1,10] , x2∈[1,8] y x3∈[1,12] en la restricción x1·x2+ 4x1+x3≤10 mediante el Algoritmo 2.19 de FBBT. 2.3. FBBT MEDIANTE ARITMÉTICA DE INTERVALOS 23 Primeramente se presenta el árbol de la restricción con cotas en variables y restricción. + · x1x2 · 4x1 x3 [1,10] [1,8] [1,10] [1,12] x1·x2+ 4x1+x3∈[−∞,10] Imagen 2.5: Árbol de la restricción asociada (con cotas de variables y restricciones). Realizando el proceso Leaf to Root se obtiene: + · x1x2 · 4x1 x3 [1,10] [1,8] [1,10] [1,12] x1·x2+ 4x1+x3∈[−∞,10] [1,10] ·[1,8] = [1,80] [1,12] 4·[1,10] = [4,40] [1,80] + [4,40] + [1,12] = [6,132] Imagen 2.6: Leaf to Root . Tras este proceso se puede observar que es posible denir una cota inferior para la restricción, ya que: x1·x2+ 4x1+x3∈[−∞,10] ∩[6,132] = [6,10], por lo que es posible ahora armar que 6≤x1·x2+ 4x1+x3≤10. Esta nueva restricción ayudará al ajuste de cotas de las variables. Realizando el proceso Root to Leaf , para propagar las cotas a las variables, se tiene: 24 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING + · x1x2 · 4x1 x3 [1,5] [1,5] [1,2] [1,5] x1·x2+ 4x1+x3 [6,132]∩[−∞,10] = [6,10] ([6,10] −[4,40] −[1,12]) ∩[1,80] = [1,5] ([6,10] −[1,80] −[1,12]) ∩[4,40] = [4,8] ([6,10] −[1,80] −[4,40]) ∩[1,12] = [1,5] [1,5] [1,10] ∩[1,10] = [1,5] [1,5] [1,10] ∩[1,10] = [1,5] [4,8] 4∩[1,10] = [1,2] Imagen 2.7: Root to Leaf . Tras los cálculos se tiene: x1∈[1,5] ∩[1,2] = [1,2], x2∈[1,5], x3∈[1,5], por lo que se ve claramente que las cotas de las variables han sido reducidas. Reaplicaciones del algoritmo no ajustarán más las cotas de las variables. Observación 2.26 . Es posible que la aplicación del Algoritmo 2.19 repetidas veces produzca mejoras sucesivas en las cotas, como ocurrirá en los siguientes ejemplos. Ejemplo 2.27 (Aplicación del algoritmo FBBT) . Ajuste de cotas en las variables x1∈[0,3] , x2∈[1,5] vericando la restricción x2 1·x2≥10 mediante el Algoritmo 2.19 de FBBT. Se presenta el árbol de la restricción y se realiza el proceso Leaf to Root : 2.3. FBBT MEDIANTE ARITMÉTICA DE INTERVALOS 25 · x2 1 x1 x2 [0,3] [1,5] x2 1·x2∈[10,∞] Imagen 2.8: Árbol de la restricción asociada (con cotas de variables y restricciones). · x2 1 x1 x2 [0,3] [1,5] x2 1·x2∈[10,∞] [0,3]2= [0,9] [1,5] [0,9] ·[1,5] = [0,45] Imagen 2.9: Leaf to Root . Una vez realizado el porceso Leaf to Root es posible denir una cota superior para la restricción ya que x2 1·x2∈[10,∞]∩[0,45] = [10,45], por lo que es posible ahora armar que 10 ≤x2 1·x2≤45. Esta nueva restricción ayudará al ajuste de cotas de las variables. Se realiza ahora el proceso Root to Leaf : · x2 1 x1 x2 [√2,3] [1,5] x2 1·x2 [10,∞]∩[0,45] = [10,45] [10,45] [1,5] ∩[0,9] = [2,45] ∩[0,9] = [2,9] [√2,√9] ∩[0,3] = [√2,3] [10,45] [0,9] NO! Imagen 2.10: Root to Leaf . Se obtienen las cotas siguientes: x1∈[√2,3], x2∈[1,5]. 26 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING No obstante, reaplicando el algoritmo, es posible ajustar las cotas nuevamente. Así se tiene: · x2 1 x1 x2 [√2,3] [1,5] x2 1·x2∈[10,45] [√2,3]2= [2,9] [1,5] [2,9] ·[1,5] = [2,45] Imagen 2.11: Leaf to Root . · x2 1 x1 x2 [√2,3] [10 9,5] x2 1·x2 [10,45] ∩[2,45] = [10,45] [10,45] [1,5] ∩[2,9] = [2,45] ∩[2,9] = [2,9] [√2,√9] ∩[√2,3] = [√2,3] [10,45] [2,9] ∩[1,5] = [ 10 9,45 2]∩[1,5] = [ 10 9,5] Imagen 2.12: Root to Leaf . Se obtienen las cotas siguientes: x1∈h√2,3i, x2∈10 9,5, que claramente han sido mejoradas. Otra aplicación del algoritmo ya no mejorará las cotas. Existen conjuntos de restricciones para los que sucesivas reaplicaciones del Algortimo 2.19 pueden producir mejoras continuadas en las cotas de las variables. No obstante, es posible que las mejoras no compensen el coste de estas reaplicaciones, o que se produzcan cambios en las cotas constantemente en cada iteración. Es por esto que este algoritmo se ejecuta con un criterio de parada de iteraciones en base al número de variables que se vean afectadas por el cambio de cotas y a la cantidad de cambio (absoluto o relativo) en las variables, determinado por una tolerancia. Es habitual también un número máximo de iteraciones. En este ejemplo se muestra un caso en el que el que se produce constantemente una mejora en las cotas de las varibles en las reaplicaciones sucesivas del algoritmo de FBBT. Ejemplo 2.28 (Basado en un ejemplo de Belotti y otros (2012)) . Ajuste de cotas en las variables x1∈[0,1] y x2∈[0,1] vericando las restricciones ax1−x2= 0 y x1−ax2= 0 , 2.3. FBBT MEDIANTE ARITMÉTICA DE INTERVALOS 27 con a > 1 . Se tienen los árboles de las restricciones: − · ax1 x2 [0,1] [0,1] ax1−x2∈[0,0] Imagen 2.13: Árbol de la primera restricción (con cotas de variables y restricciones). − x1· ax2 [0,1] [0,1] x1−ax2∈[0,0] Imagen 2.14: Árbol de la segunda restricción (con cotas de variables y restricciones). Aplicando el algoritmo a la primera restricción se obtiene: − · ax1 x2 [0,1] [0,1] [0, a] [0,1] [0, a]−[0,1] = [−1, a] ax1−x2∈[0,0] Imagen 2.15: Leaf to Root. − · ax1 x2 [0,1 a] [0,1] ax1−x2 ([0,0] + [0,1]) ∩[0, a] = [0,1] (−[0,0] + [0, a]) ∩[0,1] = [0,1] [−1, a]∩[0,0] = [0,0] 1 a[0,1] ∩[0,1] = [0,1 a] Imagen 2.16: Root to Leaf . Se tiene así que las cotas de la variable x1 se redujeron a 0,1 a , y las de la variable x2 no mejoraron. Aplicando el algoritmo a la segunda restricción con las cotas de las variables obtenidas de aplicar el algoritmo a la primera restricción se tiene: 28 CAPÍTULO 2. FBBT. FEASIBILITY-BASED BOUND TIGHTENING − x1· ax2 [0,1] [0,1 a] x1−ax2∈[0,0] [0,1 a] [0, a] [0,1 a]−[0, a]=[−a, 1 a] Imagen 2.17: Leaf to Root. − x1· ax2 [0,1 a2] [0,1 a] ax1−x2 ([0,0] + [0, a]) ∩[0,1 a] = [0,1 a] (−[0,0] + [0,1 a]) ∩[0, a] = [0,1 a] [−a, 1 a]∩[0,0] = [0,0] 1 a[0,1 a]∩[0,1] = [0,1 a2] Imagen 2.18: Root to Leaf . Se tiene, tras la aplicación del algoritmo a ambas restricciones, las siguientes cotas: x1∈0,1 a, x2∈0,1 a2. Si se realizan nuevas aplicaciones sucesivas del algoritmo a ambas restricciones, es fácil comprobar que, en la aplicación k -ésima, se tendrá: x1∈0,1 a2k−1, x2∈0,1 a2k. Es evidente que el límite de la sucesión de intervalos que se genera aplicando el algoritmo es: x1∈[0,0] , x2∈[0,0] . Sin embargo, dicho límite no sería alcanzado en un número nito de iteraciones, por lo que es importante establecer una toleracia de cambio en las cotas de las variables para detener así el algoritmo. Capítulo 3 OBBT. Optimization-Based Bound Tightening El Optimization-Based Bound Tightening (en adelante OBBT) es otro procedimiento de ajuste de cotas basado en la resolución de problemas de optimización. Por la forma en la que se dene, este método será el que proporcione las cotas óptimas para las variables. Sin embargo, será mucho más costoso computacionalmente que otros métodos, como el FBBT. En Gleixner y otros (2017) se tratan las cuestiones que competen a este capítulo. 3.1. OBBT Clásico Dado un problema de optimización:              minimizar g0(x) sujeto a gi(x)≥bi, i = 1, . . . , m x≡(x1, . . . , xn)∈Rn xL k≤xk≤xU k, k = 1, . . . , n, (3.1) el OBBT calcula las cotas de las variables resolviendo los problemas:              minimizar / maximizar xk sujeto a gi(x)≥bi, i = 1, . . . , m x≡(x1, . . . , xn)∈Rn xL k≤xk≤xU k, k = 1, . . . , n, (3.2) 29 Capítulo 4 Implementación y Resultados Numéricos 4.1. Marco de la Programación El objetivo de este capítulo es, principalmente, mostrar los resultados numéricos de rendimiento de la programación de algunos de los métodos de ajuste de cotas explicados en secciones anteriores sobre problemas de optimización concretos. Para esto, se evaluará el número medio de variables cuya cota superior o inferior es mejorada en cada problema y la posible mejora de tiempo en la convergencia del programa de optimización RAPOSa, entre otros. Los métodos programados son el FBBT mediante aritmética de intervalos (sección 2.3) y el OBBT Clásico (sección 3.1), ambos integrados completamente en el código de RAPOSa. RAPOSa (Reformulation Algorithm for Polynomial Optimization-Santiago) es un solver especícamente diseñado para resolver problemas de optimización polinómicos con variables acotadas. Está programado completamente en lenguaje C++ y está basado en la técnica Reformulation-Linearization Technique (RLT) introducida en Sherali y Tuncbilek (1992). Está siendo desarrollado por varios investigadores entre los que el autor de esta memoria ha formado parte, ayudando en la implementación de algunas técnicas de bound tightening . Más información sobre RAPOSa se puede encontrar en González-Rodríguez y otros (2020). El FBBT mediante aritmética de intervalos está programado, únicamente, para problemas de tipo polinómico. La versión de FBBT integrada en RAPOSa está basada en 37 38 CAPÍTULO 4. IMPLEMENTACIÓN Y RESULTADOS NUMÉRICOS la función de FBBT 1 que está implementada en Pyomo (Hart y otros (2011)), función de la que el autor se ha encargado de entender y ayudar a su integración en RAPOSa. Otras funciones de FBBT también fueron testeadas para su posible incorporación, como la que presenta Couenne (Belotti y otros (2009)). El OBBT está también implementado pero solamente se ejecutará en el nodo raíz sobre la versión linealizada. La librería de problemas sobre las que se realizará el estudio numérico es MINLPLib (Bussieck y otros (2003)), no obstante, se realizaron pruebas también con la librería DS-TS (Dalkiran y Sherali (2016)). Sin embargo, la librería DS-TS no aportaba información relevante para el estudio numérico, por lo que estos resultados no se incluyen. Los problemas de ambas son de tipo polinómico, pero de origen muy diferente. Los de la librería DS-TS son problemas de grado 2 a grado 7 generados de manera aleatoria mientras que los de la librería MINLPLib son problemas que han surgido en contextos reales. La librería MINLPLib presenta 166 y la librería DS-TS presenta 180 problemas. Todas las ejecuciones de este trabajo se han llevado a cabo en el superordenador Finisterrae II, del Centro de Supercomputación de Galicia (CESGA). Especícamente, se emplearon nodos computacionales con 2 CPUs deca-core Intel Haswell 2680v3 con 128 GB de RAM concetados a través de una red Inniband FDR, y 1 TB de disco duro. El autor de esta memoria destaca así sus agradecimientos al CESGA por permitirnos realizar estas ejecuciones. 4.2. Rendimiento Estático En esta sección se estudiará el cambio en las cotas de las variables en los problemas de la librería MINLPLib únicamente en el nodo raíz (relajación lineal del problema polinómico). Se estudiará el porcentaje de variables cuyas cotas cambian en cada problema y el cambio medio relativo en el rango de estas. Se ejecutarán los métodos de ajuste de cotas por separado y también se tendrá en cuenta la combinación de ellos en la efectividad de los cambios. El cambio medio relativo calcula, para cada problema, el promedio del cambio relativo que experimentan las variables, esto es, el cambio absoluto (mayor que una tolerancia 1 La función FBBT de Pyomo se puede encontrar en la dirección https://github.com/Pyomo/pyomo/tree/main/pyomo/contrib/fbbt. 4.2. RENDIMIENTO ESTÁTICO 39 jada de 10−3 ) dividido entre el rango de la variable. El porcentaje medio de variables que cambian calcula, para cada problema, el promedio de variables cuya cota superior o inferior ha sido modicada (más de una tolerancia jada de 10−3 ). Se ejecutará para todos los problemas el FBBT no lineal, el FBBT en el problema linealizado, el OBBT en el problema linealizado, y los tres anteriores seguidos (como ya se indicó, solamente en el nodo raíz). El FBBT se ejecuta por defecto con un número máximo de 50 iteraciones y una tolerancia de cambio de 10−3 . El FBBT linealizado actúa sobre la versión linealizada del problema mientras que el FBBT no lineal actúa directamente sobre el problema original. CAMBIO MEDIO RELATIVO : Podemos observar como resulta el cambio medio relativo sobre la librería MINLPLib en la Imagen 4.1. Imagen 4.1: Cambio medio relativo en la librería MINLPLib. Se observa que, claramente, la técnica que domina el ajuste de cotas es la unión de las tres (FBBT no lineal, FBBT en el linealizado y OBBT en el linealizado), lo que es esperable. El OBBT en el linealizado tiene un comportamiento similar (ya que la mediana en los dos casos es muy parecida), lo que hace indicar que el peso del ajuste de cotas 40 CAPÍTULO 4. IMPLEMENTACIÓN Y RESULTADOS NUMÉRICOS combinado esté sobre el OBBT. El FBBT en el linealizado se comporta peor que el OBBT en el linealizado, lo que era esperable también. El FBBT en el linealizado tiene un comportamiento intermedio entre el FBBT no lineal y el OBBT en el linealizado. Realizando una comparación entre ejecuciones de FBBT con máximo número de iteraciones 2 y 50 para el caso no lineal y el caso linealizado, se obtienen los resultados de la Imagen 4.2: Imagen 4.2: Cambio medio relativo en la librería MINLPLib. Comparación con el número máximo de iteraciones. En esta gráca se observa que hay variables a las que el FBBT no ajusta sus cotas todo lo que podría en solo 2 iteraciones, ya que, claramente, el proceso con máximo 50 iteraciones proporciona mejores resultados, principalmente para el caso no lineal. PORCENTAJE DE VARIABLES QUE CAMBIAN : En las Imágenes 4.3 y4.4 se pueden observar los resultados de porcentaje de variables que sufren cambios en sus cotas superior e inferior respectivamente para cada problema en la batería MINLPLib. 4.2. RENDIMIENTO ESTÁTICO 41 Imagen 4.3: Porcentaje de variables cuya cota superior cambia en la librería MINLPLib. Imagen 4.4: Porcentaje de variables cuya cota inferior cambia en la librería MINLPLib. Se observa que, en general, los métodos ajustan más porcentaje de cotas superiores que inferiores en cada problema. Nuevamente, como era esperable, el método que mejores resultados proporciona es el combinado de FBBT (no lineal y linealizado) y OBBT (linealizado), tanto en la cotas superiores como en las inferiores. Además, el OBBT tiene un comportamiento similar a las tres técnicas en conjunto por lo que, de nuevo, el peso del ajuste de cotas está sobre el OBBT. 42 CAPÍTULO 4. IMPLEMENTACIÓN Y RESULTADOS NUMÉRICOS En este caso además, el rendimiento del FBBT no lineal presenta diferencias signicativas en las cotas superiores frente al rendimiento del FBBT en el linealizado. El FBBT no lineal, de media, cambia la cota superior al 51,43 % de variables mientras que, en el caso linealizado, de media cambia la cota superior al 37,303 % de variables. 4.3. Performance Proles Los performance proles son una herramienta introducida en Dolan y Moré (2002) destinada a analizar y comparar el rendimiento de programas de optimización. Compara el valor de una variable de relevancia para el rendimiento del programa (como, por ejemplo, el tiempo de convergencia) frente al mejor valor obtenido en dicha variable para cada opción de dicho programa (o para varios programas) sobre un conjunto de problemas. Son funciones no decrecientes, constantes a trozos y continuas por la derecha en cada punto de corte. Los performance proles serán de gran utilidad para el estudio del impacto que tiene el bound tightening en RAPOSa desde distintos puntos de vista. A continuación se muestra un ejemplo de cálculo de los performance proles . Ejemplo 4.1. Cálculo de los performance proles para las 3 opciones de un solver evaluando su rendimiento en 5 problemas. Se tienen los datos de la Tabla 4.1 de tiempo de resolución de los 5 problemas. Op. 1 Op. 2 Op. 3 Mejor Pb. 1 10 30 20 10 Pb. 2 4 2 1 1 Pb. 3 100 50 200 50 Pb. 4 140 20 20 20 Pb. 5 15 30 45 15 Tabla 4.1: Datos de tiempo para distintas opciones y distintos problemas. Calculando el ratio con respecto al mejor tiempo se tiene la Tabla 4.2. 4.3. PERFORMANCE PROFILES 43 Op. 1 Op. 2 Op. 3 Pb. 1 1 3 2 Pb. 2 4 2 1 Pb. 3 2 1 4 Pb. 4 7 1 1 Pb. 5 1 2 3 Tabla 4.2: Ratio con respecto al mejor tiempo. Por tanto la opción 1, la opción 2 y la opción 3 son las mejores en el 40% de los problemas (es decir, en 2 problemas), ya que para cada opción, el ratio 1 aparece en las columnas el 40% de las veces. Sin embargo, el ratio 2 aparece 1 vez en las opciones 1 y 3 y 2 veces en la opción 2. El ratio 3 aparece una vez en las opciones 2 y 3 y ninguna en la opción 4. El ratio 4 aparece una vez en las opciones 1 y 3 y ninguna en la opción 2. Finalmente solo queda el ratio 7 , que aparece en la opción 1 una vez. Esta información se resume en la Tabla 4.3 y en la Imagen 4.5. En el 40% de los problemas, las 3 opciones son las mejores tiempo. Sin embargo, en el 80% de los problemas, la opción 2 tiene un rendimiento que, como mucho, es 2 veces peor que el mejor resultado de esta opción, y para las opciones 1 y 3 esto solo se puede asegurar en el 60 % de los problemas. Ratio Op. 1 Op. 2 Op. 3 1 40% 40% 40% 2 60% 80% 60% 3 60% 100% 80% 4 80% 100% 100% 5 80% 100% 100% 6 80% 100% 100% 7 100% 100% 100% Tabla 4.3: Porcentaje de problemas según el ratio. Observando el ratio 3, la opción 2 es, como mucho, 3 veces peor que su mejor tiempo 44 CAPÍTULO 4. IMPLEMENTACIÓN Y RESULTADOS NUMÉRICOS para resolver todos los problemas, por tanto, la opción 2 resuelve todos los problemas en, como mucho, 3 veces el tiempo que tarda en resolver el problema más rápido. Sin embargo, esto solo es asegurable en el 60 % de los problemas para la opción 1 y el 80 % de los problemas para la opción 3. Finalmente, la opción 3 resuelve el 100 % de los problemas en, como mucho, 4 veces el tiempo que tarda en resolver el problema más rápido, y la opción 1 no puede asegurar esto hasta el ratio 7, es decir, 7 veces el menor tiempo obtenido con la opción 1. Imagen 4.5: Performance proles para el ejemplo 4.1. 4.4. Rendimiento Dinámico En esta sección se estudiará el efecto de las técnicas de ajuste de cotas en la resolución de los problemas de la librería MINLPLib. Se tendrán en cuenta distintas variables como la posible reducción de tiempo, la reducción de gap o el número de problemas resueltos. El gap (relativo) de un problema de optimización con función objetivo g0(x) se dene como el cociente g0(x)U−g0(x)L |g0(x)U|+ε, donde g0(x)U, g0(x)L son, respectivamente, las cotas superior e inferior de la función objetivo, obtenidas mediante ramicación y acotación durante la resolución del problema, y ε es una tolerancia jada ( 10−3 en este caso). En la Tabla 4.4 se puede observar una comparación de los distintos tipos de bound tightening aplicados a la batería de problemas MINLPLib en función de distintos criterios. 4.4. RENDIMIENTO DINÁMICO 45 Todas las ejecuciones se realizaron con un tiempo máximo de resolución de 10 minutos y con una tolerancia de 10−3 en el ajuste de cotas. El FBBT lineal y no lineal se ejecutaron en todos los nodos de resolución de los problemas. El FBBT (tanto en el linealizado como no lineal) con profundidad 10 es el FBBT programado que solamente se ejecuta en los nodos de profundidad múltiplo de 10. El OBBT solamente se ejecutó en el primer nodo, en la versión linealizada. Original OBBT FBBT FBBT FBBT FBBT lineal no lineal lineal no lineal prof. 10 prof. 10 gap medio 2818.04 1.06 1409.46 1409.53 2817.89 2817.91 gap mediano 0.71 0.41 0.34 0.41 0.34 0.39 tiempo medio 237.09 108.76 98.02 118.27 111.73 95.59 resueltos (107/168) 98 101 104 103 105 105 Tabla 4.4: Comparaciones entre distintos métodos de bound tightening en la batería MINLPLib. En una primera observación se muestran diferencias claras en los casos en los que se aplica el ajuste de cotas y en los que no se aplica. Observando el gap medio, se ve como claramente el OBBT frente al resto de casos lo reduce drásticamente. El FBBT lineal y no lineal lo reducen en un 50 % aproximadamente y el FBBT lineal y no lineal con profundidad 10 apenas lo reducen. No obstante, observando el gap mediano se ve que el del FBBT (en todas sus variantes) es inferior o igual al del OBBT, por lo que, en realidad, proporciona resultados mejores el FBBT en cuanto a reducción de gap. Sin embargo, la existencia de problemas atípicos para el FBBT que no lo son para el OBBT distorsiona gravemente el gap medio del FBBT y no el del OBBT. Observando el tiempo medio de resolución se aprecia también una clara mejora con respecto a la opción original. En los 5 casos de ajuste de cotas el tiempo medio se redujo en más de un 50 % . 52 REFERENCIAS Hart, W. E., Watson, J.-P. y Woodru, D. L.: 2011, Pyomo: modeling and solving mathematical programs in python, 3 , 219260. Messine, F.: 2004, Deterministic global optimization using interval constraint propagation techniques, RAIRO Operations Research 38 , 277293. Moore, R. E.: 2009, Introduction to interval analysis , Society for Industrial and Applied Mathematics. Puranik, Y. y Sahinidis, N. V.: 2017, Domain reduction techniques for global nlp an minlp optimization, Constraints 22 , 338376. Sherali, H. D. y Tuncbilek, C. H.: 1992, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, Journal of Global Optimization 103 , 225249.