número máximo de BoolVar antes de ferramentas ou não é mais viável para uso

Question

O problema de programação de enfermagem padrão que é usado como um exemplo para ferramentas de cirurgia (ver por exemplo https://developers.google.com/optimization/scheduling/employee_scheduling) tenta atribuir valores booleanos a variáveis ​​booleanas na seguinte linha de código:

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

Para este problema de brinquedo, OR-Tools funciona bem, mas apenas 105 variáveis ​​booleanas são criadas (5 enfermeiras, 7 dias, 3 turnos $\Rightarrow 3\times 5\times7=105$ booleanos para determinar se uma determinada enfermeira trabalha em um determinado turno).

Estou explorando o uso de ferramentas OR para resolver um problema de agendamento do mundo real mais realista. Para o problema do mundo real com o qual estou lidando, os turnos são atribuídos em incrementos de 15 minutos e há mais trabalhadores e mais funções envolvidas. No final, acabo com 11.064 booleanos a serem atribuídos.

Isso é muito para esperar que as ferramentas OR funcionem de forma realista? Acho que ele produz rapidamente uma programação (não muito boa), mas mesmo que eu deixe funcionar por uma hora, ele não melhora em nada a programação inicial que surgiu nos primeiros segundos.

Este é o comportamento típico das ferramentas OR? Alguma ideia?

Answer 1

Não há boas respostas para essa pergunta. Depende do modelo, da complexidade do problema. Minha reação instintiva é que as OR-Tools rotineiramente resolvem para otimizar problemas maiores, mas alguns problemas muito menores podem ser impossíveis de provar, ou mesmo de encontrar uma solução viável.

OR-Tools é um bom solucionador de CP (ganhou todas as 4 medalhas de ouro nos últimos 2 desafios de minizinc). Também é um solucionador MIP decente (fechou 5 instâncias abertas do MIPLIB 2017 e aprimorou os limites em mais algumas).

Eu sugeriria ou repetiria as sugestões acima:

• compare com um solucionador MIP comercial (Gurobi, Cplex, Xpress) e tente a sorte.
• compare com CPLEX CP-Optimizer. Eu não esperava que fosse melhor após as discussões que tive com pesquisadores acadêmicos que fizeram a comparação, mas isso pode ser um problema quando o CPO tem um desempenho excelente.
• envie seu modelo para a lista de discussão de usuários de or-tools e peça ajuda ou comentários, em particular sobre os parâmetros de pesquisa.