el número máximo de herramientas o antes de BoolVar ya no es factible de usar

Question

El problema de programación de enfermeras estándar que se utiliza como ejemplo para las herramientas quirúrgicas (ver por ejemplo https://developers.google.com/optimization/scheduling/employee_scheduling) intenta asignar valores booleanos a variables booleanas en la siguiente línea de código:

shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

Para este problema de juguetes, OR-Tools funciona bien, pero solo se crean 105 variables booleanas (5 enfermeras, 7 días, 3 turnos $\Rightarrow 3\times 5\times7=105$ booleanos para asignar si una enfermera determinada trabaja en un turno determinado).

Estoy explorando el uso de OR-Tools para resolver un problema de programación del mundo real más realista. Para el problema del mundo real con el que estoy lidiando, los turnos se asignan en incrementos de 15 minutos y hay más trabajadores y más roles involucrados. Al final, termino con 11,064 booleanos para asignar.

¿Son demasiados para esperar que OR-Tools funcione de manera realista? Encuentro que produce rápidamente un programa (no muy bueno) pero luego, incluso si lo dejo funcionar durante una hora, no mejora en absoluto con respecto al programa inicial que se le ocurrió en los primeros segundos.

¿Es este comportamiento típico de OR-Tools? ¿Alguna idea?

Answer 1

No hay buenas respuestas a esa pregunta. Depende del modelo, de la complejidad del problema. Mi reacción instintiva es que OR-Tools resuelve de manera rutinaria problemas más grandes de manera óptima, pero algunos problemas mucho más pequeños pueden ser imposibles de probar, o incluso de encontrar una solución factible.

OR-Tools es un buen solucionador de CP (ganó las 4 medallas de oro de los últimos 2 desafíos de minicinc). También es un solucionador de MIP decente (cerró 5 instancias abiertas de MIPLIB 2017 y mejoró los límites en algunas más).

Sugeriría, o repetiría, las sugerencias anteriores:

• compárelo con un solucionador de MIP comercial (Gurobi, Cplex, Xpress) y pruebe su suerte.
• comparar con CPLEX CP-Optimizer. No esperaría que fuera mejor después de las discusiones que tuve con los investigadores académicos que hicieron la comparación, pero esto podría ser un problema cuando el CPO se desempeña de manera excelente.
• envíe su modelo a la lista de correo de usuarios de o-tools y solicite ayuda o comentarios, en particular sobre los parámetros de búsqueda.