Download here - Gurobi

Que hay de nuevo en Gurobi 7.0
Gracias por acompañarnos. Comenzaremos pronto.
Bienvenidos al seminario web
Que hay de nuevo en Gurobi 7.0
Presentador
• Dr. Daniel Espinoza
• Desarrollador Senior en Gurobi
• Antes de unirse a Gurobi, fue Profesor Asociado en el Departamento de
Ingeniería Industrial, Universidad de Chile
• Trabajó principalmente en la optimización entera mixta
• Ha publicado numerosos trabajos en el campo de la programación
matemática, optimización computacional, y la investigación de operaciones
• Ha dado charlas sobre programación entera y programación entera mixta
en universidades de prestigio en todo el mundo
• Doctorado en Ingeniería Industrial del Instituto de Tecnología de Georgia
Copyright 2016, Gurobi Optimization, Inc.
3
Que hay de Nuevo?
• Nuevas incorporaciones
• Nuevos desarrollos en 7.0
• Principales y segundarias
• Mejoras en rendimiento
• Nuevo Gurobi Instant Cloud
Copyright 2016, Gurobi Optimization, Inc.
Los nuevos miembros del equipo Gurobi…
Daniel Espinoza
Senior Developer
Amal de Silva
Senior Support Engineer
Frank Häger
Managing Director –
EMEA Sales
Melita Romero
Marketing Manager
Michel Jaczynski
Senior Architect
Copyright 2016, Gurobi Optimization, Inc.
Principales adiciones en Gurobi 7.0
• Mejoras en la modelación con Python
• Relación mucho mas directa entre modelación matemática y código
• Restricciones generales (General Constraints)
• Para soportar fácilmente restricciones lógicas comunes en modelación
• Optimización Multiobjetivo
• Algoritmos para balancear objetivos contrapuestos
• Múltiples soluciones (Solution pools)
• Encuentra las n mejores soluciones en vez de sólo la mejor
• Nuevo modo para lazy update
• Simplifica la modelación
Copyright 2016, Gurobi Optimization, Inc.
Otras Mejoras
• API
• Mejoras en la interfaz de .NET
• Mejor uso de propiedades .NET
• Rutinas simplificadas para configurar parámetros en otras APIs orientadas a objetos
• Mejoras en nuestra herramienta para afinar rendimiento (Tunning Tool)
• Nuevo criterio de rendimiento
• Soporte para soluciones iniciales (MIP)
• Plataformas
• Soporte de Python 3.5 en Mac
• Y la distribución asociada en Anaconda Python
• Otros
• Nuevos criterios de parada:
• BestObjStop, BestBdStop: Detener la optimización en cuanto el objetivo o la cota alcanzan un valor específico
• Nuevos planos cortantes:
• InfProofCuts, StrongCGCuts
• Más control sobre heurísticas:
• DegenMoves
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la Modelación con Python
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la Modelación con Python
• Mejora significativa en qué podemos expresar con nuestra API en Python
• Nuevas funcionalidades
• Model.addVars: agrega un conjunto de variables (indexadas sobre conjunto de índices dados)
• Model.addConstrs: agrega un conjunto de restricciones (con expresiones generadoras en Python)
• tupledict: una colección de variables que permite fácilmente construir expresiones lineales en
subconjuntos
• Modelos en Python se vuelven más concisos y fáciles de leer
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la Modelación con Python - addVars
• Antes:
transporte = {}
for d in depositos:
for p in plantas:
transporte[d,p] = model.addVar(obj=costoTransporte[d,p])
• Ahora:
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
• Los primeros argumentos proveen índices
• En este ejemplo dos dimensiones
• Primero itera sobre la lista de depósitos, y luego sobre la lista de plantas
• Número de dimensiones es arbitrario, cada una indexada sobre los miembros de una lista o por un
entero
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la Modelación con Python - tupledict
• Nueva clase tupledict, retornada por model.addVars()
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
• Facilita la construcción de expresiones lineales en conjuntos de variables
• transporte.sum(): expresión lineal que captura la suma de las variables en el tupledict
• transporte.sum(d, '*'): suma sobre un subconjunto de variables
• transporte.prod(coeffs): suma ponderada
• Muy útil en distintas situaciones
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la Modelación con Python - addConstrs
• Antes:
for d in depositos:
model.addConstr(sum(transporte[d,p] for p in plantas) == demanda[d])
• Ahora:
model.addConstrs(transporte.sum(d, '*’) == demanda[d] for d in depositos)
Copyright 2016, Gurobi Optimization, Inc.
Modelando en Python
• Antes:
transporte = {}
for d in depositos:
for p in plantas:
transporte[d,p] = model.addVar(obj=costoTransporte[d,p])
for d in depositos:
model.addConstr(sum(transporte[d,p] for p in plantas) == demanda[d])
• Ahora:
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
model.addConstrs(transporte.sum(w, '*’) == demanda[d] for d in depositos)
Copyright 2016, Gurobi Optimization, Inc.
El poder de Python
• Python es un lenguaje de programación poderoso y versátil
• Miles de módulos disponibles para descargar
• Ejemplo:
• Agregando 6 líneas a nuestro ejemplo del TSP (usando el
paquete bokeh)…
ptseq = [points[k] for k in tour+[tour[0]]]
x, y = zip(*ptseq)
p = figure(title="TSP tour", x_range=[0,100],
y_range=[0,100])
p.circle(x,y, size=8)
p.line(x, y)
show(p)
Copyright 2016, Gurobi Optimization, Inc.
Restricciones Generales
Copyright 2016, Gurobi Optimization, Inc.
Restricciones Generales
• Tipos de restricciones:
• En 6.5:
• Restricciones lineales
• Restricciones cuadráticas
• Restricciones SOS
• En 7.0: nuevas restricciones generales
• Min, Max, Abs, And (y lógico), Or (o lógico), Indicator (implicancia lógica)
• Las restricciones generales son mas fáciles de leer, escribir y mantener
• Ejemplo: r = max(x1,x2,x3)
• Linearización:
• r = x1 + s1; r = x2 + s2; r = x3 + s3 (sj no-negativa)
• z1 + z2 + z3 = 1 (zj binaria)
• SOS1(s1,z1), SOS1(s2,z2), SOS1(s3,z3)
• ¿Cuál preferiría leer/escribir/mantener?
Copyright 2016, Gurobi Optimization, Inc.
Restricciones Generales
• Ejemplos:
• Model.addGenConstrAnd(x0, [x1,x2,x3,x4])
• Restringe la variable binaria x0 = x1 ˄ x2 ˄ x3 ˄ x4 (Y lógico)
• Model.addGenConstrIndicator(x0, 1, 2*x1 + 3*x2 + x3 + 2*x4 <= 1)
• Si x0=1, entonces la restricción lineal 2x1 + 3x2 + x3 + 2x4 <= 1 debe satisfacerse
• Disponible en todas nuestras APIs para lenguajes de programación
• Principalmente es una simplificación al momento de modelar, pero…
• Pre-procesamiento puede, en algunos casos, generar formulaciones más ajustadas
Copyright 2016, Gurobi Optimization, Inc.
Optimización Multi-objetivo
Copyright 2016, Gurobi Optimization, Inc.
Optimización Multi-objetivo
• Usuarios pueden especificar múltiples funciones objetivos
• Dos opciones para combinarlos:
• Blended (mezcla)
• Usuario define pesos para cada objetivo
• Los pesos son usados para combinar los objetivos en una única función objetivo
• Hierarchical (jerárquico)
•
•
•
•
Usuario define una prioridad para cada objetivo
Optimizamos objetivos con la máxima prioridad primero
Luego el objetivo con la segunda prioridad, pero sin degradar (demasiado) la función objetivo anterior
Repetimos para cada objetivo, en orden decreciente de prioridad
• Puede combinar ambas estrategias
• Dos parámetros para controlar la optimización
• MultiObjPre: nivel de pre-proceso para el modelo multi-objetivo completo
• MultiObjMethod: selecciona el método de optimización (barrier, simplex dual o primal) a usar para
objetivos siguientes, sólo para modelos continuos
Copyright 2016, Gurobi Optimization, Inc.
Múltiples soluciones
Copyright 2016, Gurobi Optimization, Inc.
Múltiples soluciones
• En 6.5, encontramos una solución óptima
• En 7.0, puede pedir:
• Las mejores k soluciones
• k soluciones dentro de un gap dado de la solución óptima
• Nuevos parámetros
• PoolSolutions: número máximo de soluciones a guardar
• Valor por defecto es 10
• Antiguamente guardaba todas las soluciones encontradas
• PoolSearchMode: estrategia para buscar soluciones
• 0: valor por defecto (búsqueda de una solución óptima)
• 1: múltiples soluciones (búsqueda de múltiples soluciones pero no sistemática)
• 2: k mejores soluciones (búsqueda sistemática de las mejores soluciones alternativas)
• PoolGap: gap máximo entre la mejor y la peor solución guardada
• Útil para limitar el tiempo de búsqueda
• ¿Para qué buscar soluciones con gap de 50% si no son relevantes?
Copyright 2016, Gurobi Optimization, Inc.
Múltiples soluciones
• Costo computacional usualmente pequeño, pero puede ser substancial
• Deshabilita reducciones duales en pre-proceso
• Reducciones duales: pueden eliminar una solución cunado es posible demostrar que una solución equivalente o
mejor existe que no usa una variable dada
• Reducciones duales pueden ser muy importantes en algunos casos
Copyright 2016, Gurobi Optimization, Inc.
Lazy Updates
Copyright 2016, Gurobi Optimization, Inc.
Nuevo modo de Lazy Update
• En Gurobi 6.5, los cambios al modelo son guardados en una cola
• Debe invocar update() para realizar los cambios guardados en la cola
• Ventajas y desventajas:
• Update es caro computacionalmente – es bueno controlar cuando ocurre
• Agregar las llamadas a update() puede ser tedioso
• Nuevo modo de lazy update en Gurobi 7.0
• Cambios al modelo aun se guardan en una cola, pero…
• Es posible usar variables y restricciones creadas recientemente sin tener que antes llamar update()
Copyright 2016, Gurobi Optimization, Inc.
Nuevo modo de Lazy Update
• Uso típico en Gurobi 6.5:
• Agregar nuevas variables al modelo
• Invocar update() para limpiar la cola de cambios y efectivamente agregar las variables
• Agregar restricciones que involucran estas nuevas variables
• El nuevo modo evita una llamada a update()
• Otros patrones de uso en Gurobi 6.5:
• Repetir:
• Agregar algunas variables al modelo
• Invocar update()
• Agregar algunas restricciones que usan estas nuevas variables
• Llamadas frecuentes a update() puede ser computacionalmente costoso
• Llamadas a update() no son necesarias
Copyright 2016, Gurobi Optimization, Inc.
Nuevo modo de Lazy Update
• Los ejemplos de Gurobi han sido modificados para usar el nuevo modo
• Todas las llamadas a update() desaparecieron de los ejemplos
• Patrón de uso poco común:
• Aquí hay un grupo de variables y restricciones
• ¿Puede recordarme que fue lo que agregé?
• Esto aún requiere una llamada a update() en el nuevo modo
Copyright 2016, Gurobi Optimization, Inc.
Otras mejoras
Copyright 2016, Gurobi Optimization, Inc.
Mejor soporte de propiedades .NET
• Mejor soporte de propiedades .NET
• Antes: model.GetEnv().Set(GRB.IntParam.MIPFocus, 2)
• Ahora: model.Parameters.MIPFocus = 2
• También mejora el soporte de ToolTips en Visual Studio
Copyright 2016, Gurobi Optimization, Inc.
Manejo de parámetros simplificado
• Cambiar o leer parámetros es más simple en otras APIs OO
• Acceso a ellos a través del modelo en vez de la variable de ambiente
• Ejemplo en Java
• Antes: model.getEnv().set(GRB.IntParam.MIPFocus, 2)
• Ahora: model.set(GRB.IntParam.MIPFocus, 2)
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en la herramienta de Performance Tuning
• En 6.5, tuning trata de minimizar el tiempo necesario para encontrar una solución óptima
• Si esto falla, el objetivo secundario es minimizar el gap final
• En 7.0, el nuevo parámetro TuneCriterion escoge el objetivo secundario:
•
•
•
•
•
-1: modo automático
0: minimiza el tiempo de ejecución
1: minimiza el gap final
2: mejor solución factible
3: mejor cota dual demostrada
• El objetivo primario siempre es minimizar el tiempo para encontrar una solución óptima
• También es capaz de incorporar MIP starts al proceso
Copyright 2016, Gurobi Optimization, Inc.
Plataformas
• Soporte de Python 3.5 en Mac
• Y un paquete para Mac Anaconda 3.5
• Soporte para R 3.3
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en desempeño
Copyright 2016, Gurobi Optimization, Inc.
Mejoras para MILP
• Branching
• Mejores costos sombras, especialmente para modelos SOS
• Mejoras en Pseudo cost
• Cortes
•
•
•
•
Nuevos cortes strong-CG
Nuevos cortes infeasibility proof
Mejoras en funciones sub-aditivas para cortes de Gomory
Otras mejoras en varias familias de cortes, agregación, separación, lifting, estabilidad numérica, etc.
• Conflict analysis
• Pre-procesamiento
•
•
•
•
•
Mejoras en uso de GUB y VUB en reducciones
Mejores agregaciones y más estabilidad numérica
Mejor fortalecimiento de coeficientes
Implementación más eficiente de algunas reducciones
Mejoras en pre-procesamiento de nodos
• Simetría
• Mejoras en velocidad y mayor agresividad para su detección
• Heurísticas
• Nuevas heurísticas y mejores en las ya existentes
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en LP
• Principalmente en concurrent
• Eliminar trabajo redundante, como la última optimización
• Mejor rapidez en modo concurrent no-determinístico
• Algunas mejoras en simplex dual, primal y barrier
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en SOCP/QCP
• Mejoras en el paso de centrado en Barrier
• Mejor manejo de columnas densas
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en MIQCP/MISOCP
• Mejores cortes en restricciones cuadráticas usando integralidad
• Mejoras y extensiones en pre-proceso en el nodo raíz y en los nodos
• Mejoras provenientes de mejoras en SOCP/QCP
• Mejoras provenientes de mejoras en MIP
Copyright 2016, Gurobi Optimization, Inc.
Mejoras en MIQP
• Mejora principalmente debidas a mejoras en MIP
Copyright 2016, Gurobi Optimization, Inc.
Gurobi 7.0 Comparaciones de Rendimiento
Copyright 2016, Gurobi Optimization, Inc.
Dos tipos de comparaciones
• Pruebas internas
• Lo más importante: comparar Gurobi de una versión a otra
• Basado en nuestra librería interna de 4131 modelos
• Pruebas competitivas externas
• Realizadas por Hans Mittelmann, en Arizona State University
• http://plato.asu.edu/bench.html
• Para MIP basadas principalmente en MIPLIB 2010
Copyright 2016, Gurobi Optimization, Inc.
Pruebas Internas
Copyright 2016, Gurobi Optimization, Inc.
Modelos MIP en la librería Gurobi
(4131 modelos)
1E+09
100000000
10000000
1,000,000
Columns
1000000
100,000
100000
10000
1000
100
10
1
1
10
100
1000
10000
Rows
100000
1000000
Copyright 2016, Gurobi Optimization, Inc.
10000000
100000000
Mejoras de rendimiento en Gurobi 7.0
Tipo de
Problema
>1s
>100s
#
Wins
Losses
Speedup
#
Wins
Losses
Speedup
LP: conc.
387
98
50
1.10x
126
53
23
1.25x
QCP
97
87
3
1.46x
15
13
1
1.66x
MILP
2048
976
560
1.22x
862
476
259
1.38x
MIQP
91
32
25
1.09x
24
8
8
1.18x
MIQCP
200
110
47
1.48x
54
36
9
2.64x
• Gurobi 6.5 vs. 7.0: > 1.00x significa que 7.0 es más rápido que Gurobi 6.5
Mejoras en rendimiento Continuas
Casi un factor de 2x promedio en cada versión
principal
V-V Speedup
Factor de ~43x
(siete años)
Cumulative Speedup
3.00
45.0
40.0
2.50
2.00
30.0
25.0
1.50
20.0
1.00
15.0
10.0
0.50
5.0
0.00
1.0 -> 2.0
2.0 -> 3.0
3.0 -> 4.0
4.0 -> 5.0
5.0 -> 6.0
Comparación entre pares de versiones de Gurobi
© 2016 Gurobi Optimization
6.0 -> 7.0
Factor de velocidad acumulada
Version-to-Version Speedup
35.0
Comparaciones Externas
Hans Mittelmann: http://plato.asu.edu/bench.html
Copyright 2016, Gurobi Optimization, Inc.
Tiempos de solución para MIP
Gurobi 7.0 vs. Competencia: Tiempo de solución
§ > 1.0 significa que Gurobi es más rápido
§
Benchmark
#
CPLEX 12.7.0
XPRESS 8.0
P=1
P=4
P=12
P=48
P=1
P=4
P=12
P=48
Optimality
87
1.26x
1.36x
1.05x
-
1.55x
1.49x
1.38x
-
Feasibility
33
-
1.41x
-
-
-
4.10x
-
-
Infeasibility
19
-
1.00x
-
-
-
1.77x
-
-
"Solvable" Optim.
214
-
-
1.10x
1.15x
-
-
2.02x
2.00x
}
Número de problemas resuelto en “solvable set”
}
}
}
P=12: Gurobi 209, Cplex 203, Xpress 179
P=48: Gurobi 210, Cplex 207, Xpress 182
Resultados completos de la comparación disponibles aquí (datos del 8 Noviembre, 2016):
}
}
}
}
http://plato.asu.edu/ftp/milpc.html: "Optimality", time limit 7200 sec.
http://plato.asu.edu/ftp/feas_bench.html: "Feasibility", time limit 3600 sec., primera solución
http://plato.asu.edu/ftp/infeas.html: "Infeasibility", time limit 3600 sec.
http://plato.asu.edu/ftp/solvable.html: "Solvable", time limit 7200 sec.
Copyright 2016, Gurobi Optimization, Inc.
Tiempos de solución para LP
§
Gurobi 7.0 vs. Competencia: Tiempo de solución
§ > 1.0 significa que Gurobi es más rápido
Benchmark
CPLEX 12.7.0
XPRESS 8.0
Mosek 8.0
Simplex
1.88x
1.01x
2.55x
Barrier
1.54x
0.99x
2.44x
Concurrent
1.92x
0.99x
-
}
Resultados completos disponibles aquí (datos del 8 Noviembre, 2016):
}
}
http://plato.asu.edu/ftp/lpsimp.html: Simplex, time limit 25000 sec.
http://plato.asu.edu/ftp/lpcom.html: Barrier and concurrent, time limit 25000 sec.
Copyright 2016, Gurobi Optimization, Inc.
Tiempos de solución para Modelos cuadráticos
§
Gurobi 7.0 vs. Competencia: Tiempo de solución
§ > 1.0 significa que Gurobi es más rápido
Benchmark
CPLEX 12.7.0
XPRESS 8.0
Mosek 8.0
3.25x
1.28x
0.83x
?
1.38x*
-
MIQP
1.24x
1.46x
-
MIQCP
1.41x
1.15x
-
SOCP
MISOCP
}
Resultados completos disponibles aquí (datos del 8 Noviembre, 2016):
}
}
}
http://plato.asu.edu/ftp/socp.html: SOCP, time limit 3600 sec.
http://plato.asu.edu/ftp/misocp.html: MISOCP, time limit 7200 sec.
http://plato.asu.edu/ftp/miqp.html: MIQP and MIQCP, time limit 10800 sec.
Copyright 2016, Gurobi Optimization, Inc.
Gurobi Instant Cloud
Copyright 2016, Gurobi Optimization, Inc.
La alternativa de Gurobi Cloud
• Gurobi ha ofrecido servicios Cloud por más de 5 años
• Características importantes:
• Múltiples opciones de licenciamiento
• Es posible instalar licencias perpetuas en máquinas en la nube o pagar por uso por hora
• Disponible en Amazon EC2
• EC2 tiene ~85% participación del mercado
• Puede usar cualquiera de nuestras API's (C, C++, Java, .NET, Python, MATLAB, R)
• Soporte completo de nuestro API
• No es necesario cambiar su código para usar Gurobi Cloud
• Seguridad
• Toda la comunicación es encriptada con AES 256-bit
Copyright 2016, Gurobi Optimization, Inc.
Nuevo Instant Cloud
• Completamente remozado Gurobi Instant Cloud
• Nuevo sitio web
• Nuevas utilidades para activar servidores
• Activar servidores directamente desde programas en los usuarios
• Usando el archivo gurobi.lic:
CLOUDACCESSID=79344c54-48af-4d37-8526-cb8e9b2a1743
CLOUDKEY=p3XNjBlP5piz5huuzisS6w
• Usando alguno de los APIs:
env = Env.CloudEnv(“79344c54-48af-4d37-8526-cb8e9b2a1743",
“p3XNjBlP5piz5huuzisS6w")
• Activar servidores usando una REST API
• Nuevo concepto de pool
• Permite a programas clientes compartir…
• Información de configuración
• Un conjunto de servidores
Copyright 2016, Gurobi Optimization, Inc.
Nuevo Instant Cloud – Nuevo sitio web
Copyright 2016, Gurobi Optimization, Inc.
Nuevo Instant Cloud – Pools
Copyright 2016, Gurobi Optimization, Inc.
Próximos Pasos
Ø Diapositivas de este seminario estarán disponibles
• Asistentes recibirán un correo electrónico
Ø Actualizaciones de Gurobi 7.0 para usuarios existentes
• Siga las instrucciones en la página web Que Hay de Nuevo en Gurobi:
http://www.gurobi.com/new
Ø Para más información, o solicitar prueba gratuita, contáctenos en [email protected]
Copyright 2016, Gurobi Optimization, Inc.
53