Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty

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.