Set Cover Problems with Exponentially Many Constraints: Lagrangian Relaxation and Local Search Algorithms with Applications to Connected Dominating Sets
Autores
|
7540 |
539,519,3258
|
|
|
7541 |
539,519,3258
|
|
|
7542 |
539,519,3258
|
Informações:
Publicações do PESC
O problema de cobertura de conjunto, denominado em inglês como set cover problem (SCP), é um conhecido problema de otimização NP-difícil e encontra uma variedade de aplicações. Algumas dessas aplicações levam a formulações de SCP com uma quantidade exponencial de restrições. Um importante exemplo é o problema do conjunto dominante conexo mínimo (PCDCM), que encontra aplicações no design de redes de comunicação.
Ao longo das últimas décadas, algoritmos heurísticos para o SCP foram extensivamente investigados e heurísticas estado-da-arte têm se mostrado muito eficazes em produzir soluções de alta qualidade, até mesmo para instâncias de grande escala do SCP possivelmente com milhões de variáveis. Isso sugere que, para solução de problemas como o PCDCM, considerar uma formulação na forma de SCP pode se beneficiar desses algoritmos. No entanto, por mais promissor que possa parecer, esses algoritmos de SCP não foram projetados para lidar de maneira eficiente com uma quantidade exponencial de restrições.
Embora o SCP tenha sido muito estudado, um tratamento especializado para o SCP com um número exponencial de restrições ainda não foi relatado na literatura. Este trabalho visa ser o primeiro a tratar especificamente este caso. Focamos no desenvolvimento de algoritmos heurísticos que possam tanto lidar de maneira eficiente com o número excessivamente grande de restrições quanto ser eficazes na produção de soluções de alta qualidade. Mais especificamente, propomos um algoritmo relax-and-cut e um algoritmo de busca local para o SCP. Nossos algoritmos propostos incorporam um esquema dinâmico para lidar de maneira eficiente com o grande número de restrições. Isso é feito definindo convenientemente, a cada iteração, um pequeno subconjunto de restrições que são consideradas ativas e tratadas explicitamente, enquanto as restantes são inativas e tratadas implicitamente. Dessa forma, apesar do número exponencial de restrições, a complexidade de tempo de cada iteração é drasticamente reduzida, e os algoritmos não são apenas viáveis, mas também eficientes.
Como exemplo de aplicação dos nossos algoritmos relax-and-cut e de busca local, consideramos a formulação do SCP para o PCDCM e empregamos nossos algoritmos para resolver instâncias comuns na literatura e comparamos nossos resultados com heurísticas estado-da-arte especificamente projetadas para o PCDCM. De acordo com nossos experimentos computacionais, nosso algoritmo é o mais eficiente na produção de soluções de alta qualidade para o PCDCM, sendo o único a encontrar a melhor solução conhecida na literatura para todas as 41 instâncias consideradas, e em geral fazendo isso em um tempo comparável ou até menor.
The set cover problem (SCP) is a well-known NP-hard optimization problem and finds a wide range of applications. Some of these applications lead to SCP formulations with exponentially many constraints. One relevant example is the min connected dominating set problem (MCDSP), which finds applications in communications network design.
Over the past decades, SCP heuristics have been extensively investigated and state-of-the-art SCP heuristics have been shown to be very effective in producing high-quality solutions, even to large-scale SCP instances with up to millions of variables. This suggests that SCP formulations of problems such as MCDSP can benefit from these algorithms. However, promising as it may seem, these aforementioned state-of-the-art SCP algorithms are not designed to efficiently handle an exponential amount of constraints.
Although SCP has been extensively investigated, a specialized treatment of SCP with exponentially many constraints has not yet been reported in the literature. This work aims to be the first to specifically address this case. We focus on developing heuristic algorithms that can both efficiently handle the exceedingly large number of constraints as well as being effective in producing high-quality solutions. More specifically, we propose a relax-and-cut and a local-search algorithm for SCP. Our proposed algorithms incorporate a dynamic schema to efficiently handle the large amount of constraints. This is done by conveniently defining at each iteration a small subset of constraints that are considered active and are handled explicitly, whereas the remaining ones are inactive and handled implicitly. In this way, despite the exponentially many constraints, the time complexity of each iteration is drastically reduced, and the algorithms are not only viable but also efficient.
As an application of our proposed relax-and-cut and local-search, we consider the SCP formulation of MCDSP and employ our algorithms to solve benchmark instances from the literature and compare our results with state-of-the-art heuristics specifically designed for MCDSP. According to our computational experiments, our algorithm is the most efficient in producing high-quality MCDSP solutions, being the only one to find the best known solution reported in the literature for every one of the 41 benchmark instances, and generally doing so in comparable or even a shorter amount of time.
