Title: Algorithm for generalised multi-objective set covering problem with an application in ecological conservation

Authors: Lakmali Weerasena

Addresses: Department of Mathematics, University of Tennessee at Chattanooga, 615 McCallie Avenue, Chattanooga, TN 37403-2598, USA

Abstract: In this study, we propose a generalisation to the classical set covering problem (SCP) which is one of the representative NP-hard combinatorial problems. In the SCP we are given a set of items and a collection of subsets of them. We find a sub-collection including each item in a given number of sets and introduce conflicting objective functions. We define the new problem as the generalised multi-objective SCP (GMOSCP). This an extension to the classical multi-objective SCP. Developing an algorithm to approximate the Pareto set of the GMOSCP is merited since the GMOSCP is also NP-hard. Thus, we propose an algorithm to approximate the Pareto set of the GMOSCP. Ecological conservation is a common field for its applications; therefore, the performances of the algorithm is verified using real data in ecological conservation. Several experiments have been conducted to validate the performance of the proposed algorithm and compared to Pareto solutions of the GMOSCP.

Keywords: multi-objective optimisation; algorithm; approximation; reserve site selection; ecological conservation.

DOI: 10.1504/IJMMNO.2020.106534

International Journal of Mathematical Modelling and Numerical Optimisation, 2020 Vol.10 No.2, pp.167 - 186

Received: 28 Feb 2019
Accepted: 25 Jul 2019
Published online: 09 Apr 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article