Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/74271
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.creator | Iago Carvalho | pt_BR |
dc.creator | Thiago Ferreira de Noronha | pt_BR |
dc.creator | Christophe Duhamel | pt_BR |
dc.date.accessioned | 2024-08-19T20:23:55Z | - |
dc.date.available | 2024-08-19T20:23:55Z | - |
dc.date.issued | 2022 | - |
dc.citation.volume | 56 | pt_BR |
dc.citation.spage | 4281 | pt_BR |
dc.citation.epage | 4301 | pt_BR |
dc.identifier.doi | https://doi.org/10.1051/ro/2022198 | pt_BR |
dc.identifier.issn | 03990559 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/74271 | - |
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. | pt_BR |
dc.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. | pt_BR |
dc.format.mimetype | pt_BR | |
dc.language | eng | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.relation.ispartof | RAIRO Operations Research | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Heuristics | pt_BR |
dc.subject | Computers - Programming | pt_BR |
dc.subject.other | Heurística | pt_BR |
dc.subject.other | Programação (Computadores) | pt_BR |
dc.title | Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty | pt_BR |
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 | pt_BR |
dc.type | Artigo de Periódico | pt_BR |
Appears in Collections: | Artigo de Periódico |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fix-and-optimize metaheuristics.pdfA.pdf | 266.38 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.