Improving logic-based Bender's algorithms for solving min-max regret problems
Carregando...
Data
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Artigo de periódico
Título alternativo
Melhorando os algoritmos de Bender baseados em lógica para resolver problemas de arrependimento mínimo-máximo
Primeiro orientador
Membros da banca
Resumo
This paper addresses a class of problems under interval data uncertainty, composed of min-max
regret generalisations of classical 0-1 optimisation problems with interval costs. These problems are
called robust-hard when their classical counterparts are already NP-hard. The state-of-the-art exact
algorithms for interval 0-1 min-max regret problems in general work by solving a corresponding mixed-
-integer linear programming formulation in a Benders’ decomposition fashion. Each of the possibly
exponentially many Benders’ cuts is separated on the fly by the resolution of an instance of the classical
0-1 optimisation problem counterpart. Since these separation subproblems may be NP-hard, not all of
them can be easily modelled using linear programming (LP), unless P equals NP. In this work, we
formally describe these algorithms through a logic-based Benders’ decomposition framework and
assess the impact of three warm-start procedures. These procedures work by providing promising initial
cuts and primal bounds through the resolution of a linearly relaxed model and an LP-based heuristic.
Extensive computational experiments in solving two challenging robust-hard problems indicate that
these procedures can highly improve the quality of the bounds obtained by the Benders’ framework
within a limited execution time. Moreover, the simplicity and effectiveness of these speed-up procedures make them an easily reproducible option when dealing with interval 0-1 min-max regret problems
in general, especially the more challenging subclass of robust-hard 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.
Assunto
Otimização Matemática, Algoritmos de Computador, Lógica Matemática
Palavras-chave
Mathematical Optimization, Computer Algorithms, Mathematical Logic
Citação
Departamento
Curso
Endereço externo
https://hal.science/hal-03155546