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.

4 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.

Comenta

Your email address will not be published.

Puedes usar estas etiquetas y atributos de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.