Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty
| dc.creator | Iago Carvalho | |
| dc.creator | Thiago Ferreira de Noronha | |
| dc.creator | Christophe Duhamel | |
| dc.date.accessioned | 2024-08-19T20:23:55Z | |
| dc.date.accessioned | 2025-09-09T01:31:53Z | |
| dc.date.available | 2024-08-19T20:23:55Z | |
| dc.date.issued | 2022 | |
| dc.description.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. | |
| dc.format.mimetype | ||
| dc.identifier.doi | https://doi.org/10.1051/ro/2022198 | |
| dc.identifier.issn | 03990559 | |
| dc.identifier.uri | https://hdl.handle.net/1843/74271 | |
| dc.language | eng | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.relation.ispartof | RAIRO Operations Research | |
| dc.rights | Acesso Aberto | |
| dc.subject | Heurística | |
| dc.subject | Programação (Computadores) | |
| dc.subject.other | Heuristics | |
| dc.subject.other | Computers - Programming | |
| dc.title | Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty | |
| dc.title.alternative | Metaheurísticas de correção e otimização para problemas de programação inteira binária minmax lamentável sob incerteza de intervalo | |
| dc.type | Artigo de periódico | |
| local.citation.epage | 4301 | |
| local.citation.spage | 4281 | |
| local.citation.volume | 56 | |
| local.description.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. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG |