Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/74271
Tipo: | Artigo de Periódico |
Título: | Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty |
Título(s) alternativo(s): | Metaheurísticas de correção e otimização para problemas de programação inteira binária minmax lamentável sob incerteza de intervalo |
Autor(es): | Iago Carvalho Thiago Ferreira de Noronha Christophe Duhamel |
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) |
Idioma: | eng |
País: | Brasil |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Departamento: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
Tipo de Acesso: | Acesso Aberto |
Identificador DOI: | https://doi.org/10.1051/ro/2022198 |
URI: | http://hdl.handle.net/1843/74271 |
Data do documento: | 2022 |
metadata.dc.relation.ispartof: | RAIRO Operations Research |
Aparece nas coleções: | Artigo de Periódico |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Fix-and-optimize metaheuristics.pdfA.pdf | 266.38 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.