Programación lineal, de nuevo

Hoy me he retrasado en escribir por haber estado probando (y estresando, como hay quien dice), software para resolver problemas de programación lineal. En total, nada, unos diez millones de variables unos treinta millones de restricciones.

Nota: es un problema LP puro, nada de enteros, nada de pérdidas no lineales, etc.

  • Primera opción: Python + PuLP + CBC (de COIN-OR), que es el optimizador por defecto de PuLP. Rendimiento aceptable para el tipo de uso que se le acabaría dando. Se ha convertido en el benchmark.
  • Segunda opción: Python + OR-Tools (de Google), y en particular, Glop. Un tanto decepcionante: aunque ne términos de velocidad no es apreciablemente inferior a CBC, en muchos casos desistía y no encontraba ninguna solución.

Este tipo de problemas y yo nos reencontramos indefectiblemente cada cinco años. Así que, de una vez a otra, se me ha olvidado casi todo. De modo que si alguien tiene el asunto más fresco y le da rabia que algún diletante como opte por soluciones subóptimas y/o viejunas y esté entre asombrado e indignado de que ignore el último grito de la cosa, tiene la posibilidad de enmendarme a mí y enseñarnos, de paso, a todos, en los comentarios.

5 comentarios sobre “Programación lineal, de nuevo

  1. Jorge Martín Pérez 4 junio, 2020 16:30

    Hola Carlos,

    Te sugiero probar AMPL, es un lenguaje pensado para el modelado de problemas de optimización:
    https://ampl.com/

    Uno puede definir un problema entero en apenas 12 líneas:


    set NUTR;
    set FOOD;
    param cost {FOOD} > 0;
    param f_min {FOOD} >= 0;
    param f_max {j in FOOD} >= f_min[j];
    param n_min {NUTR} >= 0;
    param n_max {i in NUTR} >= n_min[i];
    param amt {NUTR,FOOD} >= 0;
    var Buy {j in FOOD} >= f_min[j], <= f_max[j];
    minimize Total_Cost: sum {j in FOOD} cost[j] * Buy[j];
    subject to Diet {i in NUTR}:
    n_min[i] <= sum {j in FOOD} amt[i,j] * Buy[j] <= n_max[i];

    Se puede integrar con Gurobi, CPLEX, Knitro, y otros solvers.
    El problema: es de pago.

  2. Enrique Gabriel Baquela 4 junio, 2020 20:04

    Hola, yo uso la suite de coin-or cuando tengo que usar open source. Si te pagan una licencia, cplex o gurobi son mas rápidos. Respecto de calidad de soluciones, con coin-or no he tenido problemas, pero depende mucho del tipo de problema. Hasta donde se, los dos paquetes comerciales anteriores implementan muchas heuristicas para evitar eso.
    Igualmente, en mi opinión, conviene invertir en licencias cuando los problemas son entero-mixtos. Si es lineal puro, a mi siempre me anduvo genial la suite coin-or.
    Solo por curiosidad, ¿que tipo de problema estás resolviendo?

  3. Aurelio 5 junio, 2020 0:30

    Yo te recomiendo Python + Pyomo + CBC

  4. Carlos J. Gil Bellosta 9 junio, 2020 15:09

    Eso justo sospechaba: que la ventaja de las aplicaciones comerciales estaba en los problemas más difíciles (programación entera y mixta) y no en los lineales puros, como el mío. Creo que en estos últimos, sin conocer la teoría sino de reojo, no hay tanto que rascar en términos de heurísticas, etc.

  5. David Hasson 29 julio, 2020 5:01

    Hola Carlos,

    1) Tal como recomendaron Aurelio y Enrique, Pyomo es probablemente el estándar para programación entera y programación lineal en Python, combinando con la suite de COIN-OR: CBC, CLP, etc… (y si tienes licencia de algún solver comercial como Gurobi/Cplex, también se puede conectar a ellos). Como referencia: a la fecha de hoy, hay 450 preguntas con tag ‘or-tools’ en stack overflow, 532 con tag ‘pulp’ y 780 de ‘pyomo’ (PuLP y PyOMO son otras alternativas en Python para modelamiento e interacción con solvers de optimización). De lo que tengo entendido, OR-Tools sirve especialmente si tienes un problema que pueda modelarse tomando provecho del framework de Constraint Programming que tiene, específicamente los tipos de variable y restriccion desarrollados para ruteo y packing (ver por ejemplo https://developers.google.com/optimization/routing).

    2) Respecto a benchmarks de distintos solver de optimización, existe por ejemplo uno que realiza año a año Hans Mittelmann usando distintos tipos de instancias, de diferentes tamaños: http://plato.asu.edu/bench.html incluye Glop, así como otros de la suite COIN-OR (CLP) y hasta aprox. 2018 también incluía software comerciales.

Los comentarios están desabilitados.