Download here - Gurobi
Document related concepts
no text concepts found
Transcript
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