Primal-dual heuristics for solving the set covering problem

Abstract

Küme örtüleme problemi çizelgeleme, üretim, hizmet planlama, ağ eniyilemesi, uziletişim gibi pek çok alanda uygulanan iyi bilinen bir birleşi eniyileme problemidir. Küme örtüleme probleminin NP-zor olduğu kanıtlanmış olup, problemin etkin bir şekilde çözümüne yönelik çok sayıda birerleme algoritmaları ve sezgiseller geliştirilmiştir. Bu çalışmanın temel amacı küme örtüleme problemi için etkin bir sezgisel geliştirmektir. Sezgisel temel-eşlenik yaklaşımına dayalı olup literatürde NP-zor birleşi eniyileme problemlerini yaklaşıklamak için kullanılmaktadır.Bu çalışmada, sezgiselin başarımını değerlendirmek için sayısal çözümlemelerle birlikte sezgiselin geliştirilme aşamalarında elde ettiğimiz gözlemler sunulmaktadır. Elde edilen sonuçlar sezgiselin çözüm kalitesi ve hesaplama zamanı açısından iyi sonuçlar verdiğini göstermektedir. Bunun yanısıra sezgiselin basit, kolay uygulanabilir, ve büyük ölçekli problemleri etkin bir şekilde çözme potansiyeli olduğunu göstermektedir.

The set covering problem (SCP) is a well known combinatorial optimization problem applied widely in areas such as; scheduling, manufacturing, service planning, network optimization, telecommunications, and so on. It has been already shown that SCP is NP-hard in the strong sense. Therefore, many heuristic and enumerative algorithms have been developed to solve SCP effectively. The primary purpose of the present study is to develop an effective heuristic for SCP. The heuristic is based on a primal-dual approach which is commonly used in the literature for approximating NP-hard optimization problems.In this study, we present numerical results to evaluate the performance of the heuristics as well as our observations throughout the development process. Our results indicate that the heuristic is able to produce good results in terms of both solution quality and computation time. Moreover, we show that the proposed heuristic is simple, easy to implement and has a potential to solve large-scale SCPs efficiently.