Improving logic-based Bender's algorithms for solving min-max regret problems

Abstract

Este artigo aborda uma classe de problemas sob incerteza de dados de intervalo, composta por min-max lamento generalizações de problemas clássicos de otimização 0-1 com custos de intervalo. Esses problemas são chamados de robustos-difíceis quando suas contrapartes clássicas já são NP-difíceis. O exato de última geração algoritmos para problemas de arrependimento no intervalo 0-1 min-max em geral funcionam resolvendo um problema misto correspondente -formulação de programação linear inteira em forma de decomposição de Benders. Cada um dos possivelmente exponencialmente muitos cortes de Benders são separados instantaneamente pela resolução de uma instância do clássico Contraparte do problema de otimização 0-1. Como esses subproblemas de separação podem ser NP-difíceis, nem todos eles podem ser facilmente modelados usando programação linear (LP), a menos que P seja igual a NP. Neste trabalho, nós descrever formalmente esses algoritmos por meio de uma estrutura de decomposição de Benders baseada em lógica e avaliar o impacto de três procedimentos de inicialização a quente. Esses procedimentos funcionam fornecendo resultados iniciais promissores cortes e limites primários através da resolução de um modelo linearmente relaxado e uma heurística baseada em LP. Extensos experimentos computacionais na resolução de dois problemas robustos-difíceis desafiadores indicam que esses procedimentos podem melhorar muito a qualidade dos limites obtidos pela estrutura de Benders dentro de um tempo de execução limitado. Além disso, a simplicidade e a eficácia destes procedimentos de aceleração tornam-nos uma opção facilmente reproduzível quando se lida com problemas de arrependimento no intervalo de 0-1 min-máx. em geral, especialmente a subclasse mais desafiadora de problemas robustos-difíceis.