Primal-dual heuristics for solving the set covering problem

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

[thumbnail of BelmaYelbay.pdf] PDF
BelmaYelbay.pdf

Download (547kB)
[thumbnail of Restricted to Repository Staff Only] Zip Compressed (Restricted to Repository Staff Only)
BernaYelbay_Figures.zip
Restricted to Repository staff only

Download (340kB) | Request a copy

Abstract

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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 21 May 2012 12:44
Last Modified: 26 Apr 2022 09:55
URI: https://research.sabanciuniv.edu/id/eprint/19047

Actions (login required)

View Item
View Item