Que hay de nuevo en Gurobi 7.0Gracias por acompañarnos. Comenzaremos pronto.
Bienvenidos al seminario webQue 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…
Copyright 2016, Gurobi Optimization, Inc.
Daniel EspinozaSenior Developer
Frank HägerManaging Director –
EMEA Sales
Melita RomeroMarketing Manager
Michel JaczynskiSenior Architect
Amal de SilvaSenior Support Engineer
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:
• Ahora:
• 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.
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
transporte = {}for d in depositos:for p in plantas:transporte[d,p] = model.addVar(obj=costoTransporte[d,p])
Mejoras en la Modelación con Python - tupledict
• Nueva clase tupledict, retornada por model.addVars()
• 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.
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
Mejoras en la Modelación con Python - addConstrs
• Antes:
• Ahora:
Copyright 2016, Gurobi Optimization, Inc.
for d in depositos:model.addConstr(sum(transporte[d,p] for p in plantas) == demanda[d])
model.addConstrs(transporte.sum(d, '*’) == demanda[d] for d in depositos)
Modelando en Python
• Antes:
• Ahora:
Copyright 2016, Gurobi Optimization, Inc.
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])
transporte = model.addVars(depositos, plantas, obj=costoTransporte)
model.addConstrs(transporte.sum(w, '*’) == demanda[d] for d in depositos)
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)…
Copyright 2016, Gurobi Optimization, Inc.
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)
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)
1
10
100
1000
10000
100000
1000000
10000000
100000000
1E+09
1 10 100 1000 10000 100000 1000000 10000000 100000000
Col
umns
Rows
100,000
1,000,000
Copyright 2016, Gurobi Optimization, Inc.
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.18xMIQCP 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
Comparación entre pares de versiones de Gurobi
Factor de ~43x (siete años)
Casi un factor de 2x promedio en cada versión principal
© 2016 Gurobi Optimization
-
5.0
10.0
15.0
20.0
25.0
30.0
35.0
40.0
45.0
0.00
0.50
1.00
1.50
2.00
2.50
3.00
1.0 -> 2.0 2.0 -> 3.0 3.0 -> 4.0 4.0 -> 5.0 5.0 -> 6.0 6.0 -> 7.0
Fact
or d
e ve
loci
dad
acum
ulad
a
Vers
ion-
to-V
ersi
on S
peed
up
V-V Speedup Cumulative Speedup
Comparaciones ExternasHans Mittelmann: http://plato.asu.edu/bench.html
Copyright 2016, Gurobi Optimization, Inc.
§ 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
Tiempos de solución para MIP
} 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.
§ 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 -
Tiempos de solución para LP
} 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.
§ 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
SOCP 3.25x 1.28x 0.83x
MISOCP ? 1.38x* -
MIQP 1.24x 1.46x -
MIQCP 1.41x 1.15x -
Tiempos de solución para Modelos cuadráticos
} 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:
• Usando alguno de los APIs:
• 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.
CLOUDACCESSID=79344c54-48af-4d37-8526-cb8e9b2a1743CLOUDKEY=p3XNjBlP5piz5huuzisS6w
env = Env.CloudEnv(“79344c54-48af-4d37-8526-cb8e9b2a1743",“p3XNjBlP5piz5huuzisS6w")
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