Design of a heuristic algorithm for the generalized multi-objective set covering problem

Lakmali Weerasena (), Aniekan Ebiefung () and Anthony Skjellum ()
Additional contact information
Lakmali Weerasena: University of Tennessee at Chattanooga
Aniekan Ebiefung: University of Tennessee at Chattanooga
Anthony Skjellum: University of Tennessee at Chattanooga

Computational Optimization and Applications, 2022, vol. 82, issue 3, No 6, 717-751

Abstract: Abstract Set covering optimization problems (SCPs) are important and of broad interest because of their extensive applications in the real world. This study addresses the generalized multi-objective SCP (GMOSCP), which is an augmentation of the well-known multi-objective SCP problem. A mathematically driven heuristic algorithm, which uses a branching approach of the feasible region to approximate the Pareto set of the GMOSCP, is proposed. The algorithm consists of a number of components including an initial stage, a constructive stage, and an improvement stage. Each of these stages contributes significantly to the performance of the algorithm. In the initial stage, we use an achievement scalarization approach to scalarize the objective vector of the GMOSCP, which uses a reference point and a combination of weighted $$l_1$$ l 1 and $$l_\infty$$ l ∞ norms of the objective function vector. Uniformly distributed weight vectors, defined with respect to this reference point, support the constructive stage to produce more widely and uniformly distributed Pareto set approximations. The constructive stage identifies feasible solutions to the problem based on a lexicographic set of selection rules. The improvement stage reduces the total cost of selected feasible solutions, which benefits the convergence of the approximations. We propose multiple cost-efficient rules in the constructive stage and investigate how they affect approximating the Pareto set. We used a diverse set of GMOSCP instances with different parameter settings for the computational experiments.

Keywords: Approximation; Algorithm; SCP; Multi-objective; Multi-cover (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00379-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:82:y:2022:i:3:d:10.1007_s10589-022-00379-7

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00379-7

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().