Primal-dual heuristics for solving the set covering problem

Yelbay, Belma (2010) Primal-dual heuristics for solving the set covering problem. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
[img]Zip Compressed (Restricted to Repository Staff Only) - Repository staff only

Official URL: (Table of Contents)


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 [15]. 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 heuristic 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.

Item Type:Thesis
Uncontrolled Keywords:Combinatorial optimization. -- Set covering. -- Primal-dual approach. -- Heuristics. -- Birleşi eniyileme. -- Küme örtüleme. -- Temel-eşlenik yaklaşım. -- Sezgiseller.
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
ID Code:19047
Deposited By:IC-Cataloging
Deposited On:21 May 2012 12:44
Last Modified:25 Mar 2019 17:03

Repository Staff Only: item control page