Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
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
Metaheurísticas de correção e otimização para problemas de programação inteira binária minmax lamentável sob incerteza de intervalo
Primeiro orientador
Membros da banca
Resumo
The Binary Integer Programming problem (BIP) is a mathematical optimization problem,
with linear objective function and constraints, on which the domain of all variables is {0, 1}. In BIP,
every variable is associated with a determined cost coefficient. The Minmax regret Binary Integer
Programming problem under interval uncertainty (M-BIP) is a generalization of BIP in which the cost
coefficient associated to the variables is not known in advance, but are assumed to be bounded by an
interval. The objective of M-BIP is to find a solution that possesses the minimum maximum regret
among all possible solutions for the problem. In this paper, we show that the decision version of M-BIP
is Σ𝑝
2
-complete. Furthermore, we tackle M-BIP by both exact and heuristic algorithms. We extend three
exact algorithms from the literature to M-BIP and propose two fix-and-optimize heuristic algorithms.
Computational experiments, performed on the Minmax regret Weighted Set Covering problem under
Interval Uncertainties (M-WSCP) as a test case, indicates that one of the exact algorithms outperforms
the others. Furthermore, it shows that the proposed fix-and-optimize heuristics, that can be easily
employed to solve any minmax regret optimization problem under interval uncertainty, are competitive
with ad-hoc algorithms for the M-WSCP.
Abstract
O problema de Programação Inteira Binária (BIP) é um problema de otimização matemática,
com função objetivo linear e restrições, nas quais o domínio de todas as variáveis é {0, 1}. No BIP,
cada variável está associada a um determinado coeficiente de custo. O Minmax lamenta o inteiro binário
O problema de programação sob incerteza de intervalo (M-BIP) é uma generalização do BIP em que o custo
coeficiente associado às variáveis não é conhecido antecipadamente, mas é assumido como limitado por um
intervalo. O objetivo do M-BIP é encontrar uma solução que possua o mínimo máximo de arrependimento
entre todas as soluções possíveis para o problema. Neste artigo, mostramos que a versão de decisão do M-BIP
é Σ𝑝
2
-completo. Além disso, abordamos o M-BIP por meio de algoritmos exatos e heurísticos. Estendemos três
algoritmos exatos da literatura para M-BIP e propõem dois algoritmos heurísticos de correção e otimização.
Experimentos computacionais, realizados no problema de cobertura de conjuntos ponderados de arrependimento Minmax em
Incertezas de intervalo (M-WSCP) como caso de teste, indica que um dos algoritmos exatos supera
os outros. Além disso, mostra que a heurística proposta de corrigir e otimizar, que pode ser facilmente
empregados para resolver qualquer problema de otimização de arrependimento minmax sob incerteza de intervalo, são competitivos
com algoritmos ad-hoc para o M-WSCP.
Assunto
Heurística, Programação (Computadores)
Palavras-chave
Heuristics, Computers - Programming