Post on 02-Nov-2018
Simulación y Optimización de Procesos Químicos
Titulación: Ingeniería Química. 5º Curso
Optimización
MILP, MINLP(Mixed Integer (Non) L inear Programming) .
Octubre de 2009. José A. Caballero
Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Optimización Discreta
Programación Lineal de con variables discretas (MILP)
{ }1,0,,0
0..
min
∈ℜ∈≥
≤−++=
yxx
bByAxas
yaxcZ
n
TT
Algoritmos
I. EnumeraciónRamificación y Acotamiento(Land, Doig 1960; Dankin 1965)
Idea Básica: Partición sucesiva del espacio entero para eliminar regiones. Se lleva a cabo una búsqueda en árbol, donde cada nodo es un LP.
II. ConvexificaciónPlanos de corte (Gomory 1958; Crowder y col, 1983; Balas y col. 1993)
Idea Básica: resolver una serie de subproblemas LP añadiendo cada vez desigualdades válidas que corten soluciones previas.
Ramificación y Acotamiento ampliamente utilizadoIntegración de los métodos : RAMIFICACIÓN Y CORTE
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Enumeración exhaustivasólo válida para problemas pequeños
5. Variables binarias 32 combinaciones enteras10 Variables binarias 1024 combinaciones enteras50 Variables binarias 1015 combinaciones enteras100. Variables binarias 1030 combinaciones enteras1000. Variables binarias 103000 combinaciones enteras
Escala detiempo
(Microsegundos)
0
1020
1040
1010
1030
Microsegundos en un día
Microsegundos desde el ‘Big Bang’(Unos trece mil setecientos millones de años)
No funciona en MILP…
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
No funciona en MILP…
Relajación y Redondeo
Optimo entero
Optimo relajado
Redondeo: no-factible
NO-FACTIBLE
1
00 1
y2
y1
1
0
0
y2
y1
Optimo entero
Optimo relajado
Redondeo: factible
¡ SUB-OPTIMO !
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
No funciona en MILP…
{ }
1 2
1 2
1 2
min : 2
. . 2 1
, 0,1
Z y y
s a y y
y y
= ++ ≥
∈ Reemplazar{ }0,1y ∈
( )( )
1 1 1
2 2 2
0 1 1 0
0 1 1 0
y y y
y y y
≤ ≤ − ≤
≤ ≤ − ≤
Utilizando el código CONOPT2:
Punto Inicial: Resultado
1 2
1 2 1 2
0; 0
0.5; 0.5 0; 1; 2
y y no factible
y y y y Z
= = −= = = = = Sub-óptimo
Solución optima: 1 21; 0; 1y y Z= = =
Reformulación del problema como no lineal:
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Ramificación y Acotamiento
Particionamiento del espacio entero a través de una árbol binario
Nodo raíz(relajación LP)
y2= 0 y2= 1 y2= 0 y2= 1
y3= 0
y3= 1
y3= 0
y3= 1
y3= 0
y3= 1
y3= 0
y3= 1
y1= 0 y1= 1
Nodo l
Nodo k
Nota: 15nodos para 23 = 8 combinaciones 0-1
Nodo k descendiente del nodo l
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Nodo raíz(relajación LP)
y2= 0 y2= 1 y2= 0 y2= 1
y3= 0
y3= 1
y3= 0
y3= 1
y3= 0
y3= 1
y3= 0
y3= 1
y1= 0 y1= 1
Nodo l
Nodo k
Ramificación y Acotamiento
Sea el nodo k un nodo descendiente del nodo l
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Ramificación y Acotamiento
{ }1,0,,0
0..
min
∈ℜ∈≥
≤−++=
yxx
bByAxas
yaxcZ
n
TTDado que el nodo k es descendiente del nodo l
3.- SiLPk es una soluciónENTERA Zk ≤ Z*
Zk: LIMITE SUPERIOR
Reglas de eliminación de nodosNodo no factibleLímite inferior supera límite superior
1.- Si LPl es NO-FACTIBLE entonces LPk es NO-FACTIBLE
2.- Si LPk es FACTIBLE entonces Zl ≤ Zk
Incremento monótono de función objetivo
Zl : LIMITE INFERIOR
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Ramificación y Acotamiento
Para utilizar un algoritmo de R. A. hay dos decisiones que tomar:
1. Qué variable se selecciona para ramificar en cada nodo
2. Qué nodo, entre los abiertos, es el siguiente en la enumeración
Reglas de ramificación: Selección de variable
1.- Fijar prioridades en la variables para ramificación
2.- Seleccionar para ramificar aquella variable, entre las binarias, con un valor más cercano a 0.5.
3.- Coste Penalizado (Driebneck, 1966)
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Reglas de ramificación: Selección del nodo a ramificar
1.- Búsqueda en profundidad: Continuar siempre hacia delante en la rama seleccionada, y sólo volver hacia atrás cuando no se pueda continuar. Continuar siempre por la rama abierta más cercana al punto de retorno.
2.- Búsqueda en anchura:Continuar siempre por el nodo de mejor valor de función objetivo.
Ramificación y Acotamiento
En la práctica, cuando se trabaja con variables binarias, se utiliza dicotomía (siempre e prueba el valor y=0 e y=1 de la variable a ramificar) y búsqueda en profundidad. Aunque los ‘solvers’ modernos utilizan estrategias complejas de ramificación.
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
1,0,,;0
9385
023..
23min
321
321
321
321
=≥−≤−−−≤+++−
+++=
yyyx
yyy
yyyxas
yyyxz
1
z =5.8
[0.2, 1, 0] 5
4
y3=1
y3=0
z=6.75
no factible
[0, 0.75, 1]
3
2
y1=1
y1=0z=6
z=6.5
[0, 1, 0.333]
[1, 0.5, 0]
7
6y2=0
y2=1
no factible
[0, 1, 1]
z=8
Óptimo
9
8no factible
z=9
y2=1
y2=0
[1,1,0]
Ejemplo 1 MILP(DFS)
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
1,0,,;0
9385
023..
23min
321
321
321
321
=≥−≤−−−≤+++−
+++=
yyyx
yyy
yyyxas
yyyxz
1
z =5.8
[0.2, 1, 0] 5
4
y3=1
y3=0
z=6.75
no factible
[0, 0.75, 1]
3
2
y1=1
y1=0z=6
z=6.5
[0, 1, 0.333]
[1, 0.5, 0]
9
8y2=0
y2=1
no factible
[0, 1, 1]
z=8
Óptimo
7
7no factible
z=9
y2=1
y2=0
[1,1,0]
Ejemplo 1 MILP(BFS)
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
( )
{ }
1 2 3 4 5
1 2 3 4 5
1 2 4
min 5 3 2.3 1.4 0.95 10
. . 2.5 2 2 0.2 0.85 3
0.5 0.3 0.3 1
0,1 1,2,3,4,5i
z y y y y y
s a y y y y y
y y y
y i
= − + + + − ++ + + − ≤+ + ≤
∈ =
1
z =2.9
[1, 0.55, 0, 1, 1]
3
z =3.35
[0.64, 0, 1, 1, 1]
2
z =3.225
[1, 0, 0.15, 1, 0]
4
z =4.05
[0.64, 0, 1, 1, 1]
5
z =3.60
[1, 0, 0, 1, 0]
Cota superior
Nodo con valor mayorque cota superior. No esnecesario continuar poresta rama
6
no-factible
7
z =4.68
[0, 1, 0.4, 1, 1]
Nodo con valor mayorque cota superior. No esnecesario continuar poresta rama
OPTIMO
Ejemplo 2
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Ejemplo 3 (DFS)
1
z =2.35
[1, 0.55, 0, 1, 1]
2
z =2.35
0.64, 1, 0, 1, 1]
3
z =3.405
[1, 0, 0.15, 1, 0]
4
z =4.08
[0, 1, 0.4, 1, 0]
5
[no-factible]
6
[no-factible]
7
z =4.60
[0, 1, 0, 1, 0]
8
z =5.05
[0.64, 0, 1, 1, 1]
9
z =3.6
[1, 0, 0, 1, 1]
Cota superior
Cota superior
Nodo con valor mayorque cota superior. No esnecesario continuar poresta rama
OPTIMO
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Algunas consideraciones importantes
La dificultad para resolver un M ILP está relacionada con:
1. Tamaño del “GAP” de relajación2. Nº de variables 0-13. Nº de restricciones.
Sin embargo esto es específico de cada problema. Un problema con 20 variables binarias podría ser mucho más difícil de resolver que otro con 1000.
El correcto modelado del problema, es para los MILP de crucial importancia.
Algunas mejoras en los algoritmos de Ramificación y Acotamiento:
1. Reducción de coeficiente2. Eliminar restricciones redundantes3. Añadir desigualdades lógicas (aunque estrictamente no sean necesarias)4. Estrechar los límites de las variables5. Estrategias de ramificación especiales para algunas restricciones (o variables ej SOS1)6. Etc…
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Reducción de coeficiente
Considere la siguiente restricción { }0 0,1j j j jj
a y b a y≥ > ∈∑
Si ak > b reemplazar ak por b: { }0 0,1k j j j jj k
b y a y b a y≠
+ ≥ > ∈∑
Ejemplo:
1 2
1 2
2 1 (1)
1 (2)
y y
y y
+ ≥
⇓
+ ≥
10
1
(2)
(1)
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Correcto modelado y relaciones lógicas
Si la tarea Yi se lleva a cabo en cualquier período i=1..n entonces seleccionar la unidad Z.
Intuitivamente se pueden escribir 2 conjuntos de restricciones algebraicas válidas
Si el conjunto de restricciones lineales no es únicoEntonces…. ¿Cuál es la mejor opción?
Ejemplo: Una restricción habitual
znyn
ii ≤∑
=1Una única desigualdadA-
niyz i ,....,2,1=≥ Conjunto de n desigualdadesB-
Considerese el caso con i=2
2
1
yz
yz
≥≥
( )2
21 yyz +≥ A
B
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
y2y1
z
Caso A ( )2
21 yyz +≥ Región factible
Punto no enteroPunto no entero
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Caso BRegión factible
y2y1
z
2
1
yz
yz
≥≥
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Conjuntos de ordenación especial
SOS1 Considere la siguiente restricción 1ii I
y∈
=∑
En lugar de la regla habitual de ramificación :
• Se divide I en dos subconjuntos iguales I1 e I2
• Se ramifica sobre la dicotomía:1 2
0 0i ii I i I
y y∈ ∈
= ∨ =∑ ∑
1 2 3 4 0y y y y+ + + = 5 6 7 8 0y y y y+ + + =
5 6 0y y+ = 7 8 0y y+ = 1 2 0y y+ = 3 4 0y y+ =
7 0y = 8 0y = 5 0y = 6 0y = 3 0y = 4 0y = 1 0y = 2 0y =
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Programación No-Lineal de con variables discretas (MINLP)
{ }p
n
y
Xx
yxg
yxhas
yxf
1,0
0),(
0),(..
),(:min
∈
ℜ⊆∈
≤=
Ramificación y AcotamientoRavindran y Gupta 1985; Leyffer y Fletcher 2001Ramificación y corte:Stuubs y Mehrota 1999
Descomposición de Benders GeneralizadaGeofrion, 1972
Aproximaciones ExterioresDuran y Grossmann 1986; Yuan y col 1988; Fletcher y Leyffer 1994
LP/NLP Ramificación y AcotamientoQuesada y Grossmann 1992
Plano de Corte ExtendidoWesterlund y Petersen 1995
Algoritmos
MINLP
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Ramificación y Acotamiento
Enumeración en árbol
min : ( , )
. ( , ) 0
, 0 1
0
1
kLB
j
ki FL
ki FU
Z f x y
s a g x y
x X y
y i I
y i I
=≤
∈ ≤ ≤
≤ ∈
≥ ∈
Cada nodo es unNLP-1
Ventaja: Formulación sencilla, sólo requiere problemas de tipo NLP-1
Inconveniente:Potencialmente sería necesario resolver muchos NLPs
Convergencia global:sólo necesita que cada NLP-1 alcance su óptimo global
MINLP
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Los diferentes algoritmos se pueden derivar por la combinación de diferentes sub-problemas
min : ( , )
. ( , ) 0
, 0 1
0
1
kLB
j
ki FL
ki FU
Z f x y
s a g x y
x X y
y i I
y i I
=≤
∈ ≤ ≤
≤ ∈
≥ ∈
a) NLP Relajado (relajación de alguna binaria).Límite inferior
(NLP-R)min : ( , )
. ( , ) 0
k kU
kj
Z f x y
s a g x y
x X
=
≤
∈
b) NLP Variables binarias fijas.Límite Superior
(NLP-1)
1
min :
. ( , )
,
kj
u
s a g x y u
x X u R
≤
∈ ∈
c) NLP De Factibilidad para una yk fija.
Minimización de la norma infinito del vector de no-factibilidades(NLP-F)
MINLP
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
MINLP
Problema Maestro(Duran y Grossmann, 1986)
min :
. . ( , ) ( , )
1...
( , ) ( , ) 0
kL
kk k k k T
k
kk k k k T
j j k
Z
x xs a f x y f x y
y yk K
x xg x y g x y j J
y y
α
α
=
−≥ +∇
− = −
+ ∇ ≤ ∈ −
M-MILP
Notas:
a) El punto (xk, yk) k = 1…K se obtiene normalmente de NLP-1
b) Las linealizaciones se acumulan en cada iteración
c) Produce una secuencia no-decreciente de límites inferiores
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
x2
f(x)
x
Función objetivo convexa
x2
x2
x1
x1
x1
Región factible convexa
Subestimación de la función objetivo
Sobreestimación de la región factible
MINLP
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
MINLP
Algoritmo de las aproximaciones exteriores(implementado en GAMS como DICOPT)
NLP-1 Factible
Sí
ZM > Z*No
Corte Binario
SíFin
NLP-1
(y fijas)Cota Superior. Posible Solución. Nueva linealización en x óptima
Z* = mejor cota superior
MILP-M
Cota Inferior:Valores de yk para NLP-1
Función objetivo = ZM
NLP-RProblema relajado. Binarias
relajadas a continuas entre 0 y 1
NoNLP-F Problema de factibilidad
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
MINLP
Extensión a problemas con restricciones de igualdad:
La única modificación necesaria es a nivel del problema MASTER
min :
. . ( , ) ( , )
( , ) ( , ) 0
kL
kk k k k T
k
kk k k k T
j j k
Z
x xs a f x y f x y
y y
x xg x y g x y j J
y y
α
α
=
−≥ + ∇
−
−+ ∇ ≤ ∈
−
( ) ( , ) 0k
k k Ti i k
x xsign h x y i I
y yλ
− ∇ ≤ ∈ −
1....k K=
Relajación de la igualdad en desigualdad utilizando el signo del multiplicador de Lagrange
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Códigos comerciales para MINLP
DICOPT++(GAMS) Viswanathan y Grossmann (1990)
Aproximaciones exteriores
AOA (AIMSS)
Aproximaciones exteriores
MINLP (AMPL) Fletcher y Layffer (1999)
Ramificación y acotamiento
α-ECP Westerlund y Petersson (1996)
Plano de corte extendido (también bajo GAMS)
MINOPT Scheweiger y Floudas (1998)
Descomposición de Benders
BARON Sahinidis y col (1998)
Optimización global (también bajo GAMS)
SBB (GAMS)
Ramificación y acotamiento simple.
José A. CaballeroSimulación y Optimización de Procesos Químicos. Esta obra está bajo una licencia Reconocimiento-No comercial-Sin obras derivadas 3.0 España de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-nd/3.0/es/ o envie una carta a Creative Commons, 171 Second Street, Suite 300, San Francisco, California 94105, USA.Citar como: J.A. Caballero Suárez, material docente para la asig natura Simulación y Optimización de procesos Químico s, Octubre 2009. Universidad de Alicante.
Sistemas de modeladoProgramación Matemática
GAMS (Meeraus y col, 1997)
AMPL (Fourer y col, 1995)
AIMSS (Bisschop y col, 2000)
1. Sistemas de modelado algebraico: Modelos basados en ecuaciones
2. Capacidad de indexado. Permite plantear problemas grandes con poco esfuerzo
3. Diferenciación automática. El usuario no tiene que proporcionar información de
derivadas.
4. Conexión automática don diferentes códigos(sin cambiar la formulación del
modelo) y diferentes tipos de modelos(LP, MILP, NLP, MINLP …)