¿Cómo implementar sucursal y precio?
Una vez escuché que el algoritmo de sucursales y precios (B&P) se encuentra entre los más difíciles en quirófano, pero si se implementa bien, podría ser muy eficiente. ¿Hay otros algoritmos que también sean tan complicados?
Quiero implementar B&P en un problema. Entonces, ¿cómo elijo un problema que no sea demasiado complejo? Siéntase libre de sugerir más de un problema si cree que tiene un impacto en la forma en que se implementa el algoritmo, es decir, si aprenderé diferentes principios de diferentes problemas.
También necesito orientación. ¿Cómo empezar? ¿Cuáles son las trampas que se deben evitar? También se agradecería cualquier recurso que tenga un código de fuente abierta que esté bien documentado. Quiero elegir Python o C ++.
Respuestas
Antes de comenzar la implementación, me aseguraría de estar cómodo con todos los aspectos teóricos, que también son algo complicados. Este es un tema bastante avanzado en quirófano y requiere algo de experiencia. ¿Se siente cómodo con la función de ramificación y enlace, con el algoritmo simplex, con la descomposición de Dantzig-Wolfe, la generación de columnas, etc.?
Estás dudando entre Python y C ++. ¿Hay alguna razón para eso? Python es mucho más simple, pero C ++ será más rápido. Entonces, ¿esto es para la academia o para la industria?
También puede pago y envío DIPPY , que es una extensión de la pulpa (por lo que su Python) que permite a los usuarios especificar descomposiciones y personalizar la ramificación, la generación de corte, y la generación de la columna de DIP , desde dentro de un modelo de pulpa. Todo es de código abierto.
Usar un marco como SCIP puede ser una buena idea para comenzar. Al hacerlo, puede implementar rápidamente su formulación. Tiene interfaces tanto en C ++ como en Python. La documentación contiene ejemplos de sucursales y precios, le sugiero que les eche un vistazo. Para cualquier problema que tenga entre manos, puede utilizar el método de descomposición de Dantzig-Wolfe para generar un esquema de sucursales y precios.
Nah. Construir una interfaz ASL es difícil , BnP está bien. Suponiendo que esté familiarizado con sus componentes básicos (al igual que con cualquier otro algoritmo), el desafío radica en los detalles de implementación.
Hay algunas cosas que debe tener en cuenta para BnB en general, y para BnP específicamente:
BnB
- Heurísticas de aceleración: los algoritmos BnB solo funcionan bien si se combinan con ciertas heurísticas de aceleración como la reducción de dominio (por ejemplo, la propagación de restricciones) o buenas estrategias de ramificación (por ejemplo, pseudocostes).
- Para problemas grandes, necesita estructuras de datos buenas y escalables para evitar que el algoritmo se ralentice, especialmente si sus problemas son lo suficientemente grandes como para requerir la generación de columnas.
- Pure Python será 1,000-10,000 veces más lento que C ++ para cualquier problema de tamaño decente. La forma correcta de hacer esto es codificar las bibliotecas de C ++ para los cálculos de alto rendimiento e importarlas como objetos de Python usando las API de Python-> C ++ como boost Python. Esto puede llevarlo a 100 veces más lento que C ++.
- Por las dos razones anteriores, Python tiene sus límites debido al ancho de banda limitado para transferir datos entre diferentes partes de su código. En particular, muchas API de Python-> C ++ inevitablemente activan constructores de copia de C ++, lo que puede ser un gran problema si sus estructuras de datos son grandes. La memoria también puede convertirse en un problema.
- Ya que estamos en el tema, incluso si realmente sabe lo que está haciendo en C ++, lo mejor que puede hacer con el código híbrido es 100 veces más lento que C ++. Sin embargo, si está en ese nivel de saber lo que está haciendo, también podría hacerlo todo en C ++.
- MINOTAUR es el código BnB de código abierto C ++ mejor escrito que he visto hasta ahora (aunque no muy bien documentado hace unos años).
- Una cosa que la mayoría de la gente descuida al principio es que necesita una forma de obtener las matemáticas en su código. Piense en cómo hará esto desde el principio, ya que afectará muchas de sus decisiones de arquitectura.
BnP
- Una consideración de implementación importante aquí es que debe agregar columnas a la relajación a medida que avanza el procedimiento de solución. Esta puede ser una operación muy costosa, especialmente con matrices grandes, por lo que deberá investigar la forma más rápida que admita su solucionador lineal para agregar nuevas columnas. La reconstrucción de la matriz es la forma más sencilla, por supuesto, y en realidad está bien para muchos algoritmos, pero es un no-no para la generación de columnas.
Según su descripción, parece que su objetivo es aprender cosas nuevas, por lo que Python o C ++ están bien para ese propósito. Si desea usar su código para algo "real", usar C ++ hasta cierto punto será inevitable, por lo que depende de usted decidir qué desea aprender a programar. Sin embargo, tenga en cuenta que migrar código híbrido a C ++ puede ser bastante doloroso, por lo que si ve que tiene que ir con C ++ mejor, hágalo al principio del desarrollo.
De cualquier manera, prepárate mentalmente para una gran inversión y ¡diviértete!
Si desea ver el código fuente de C ++, existen algunos proyectos COIN-OR que proporcionan marcos para "precio y corte de sucursales" o "corte y precio de sucursales", como a veces se lo conoce. Dos que me vienen a la mente son BCP y Symphony .
Una de las ideas principales detrás de nuestro solucionador de descomposición GCG (gcg.or.rwth-aachen.de/dev) es ahorrarle el tiempo de experimentar con su propio código B & P y descubrir que B & P no es el enfoque correcto para su problema. Otra idea principal de nuestro solucionador es que una vez que descubra que B&P es un buen enfoque, puede usar GCG para hacer el trabajo por usted. Pruébelo, con suerte le ahorrará algunas horas. Descargue con SCIP en scipopt.org.