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.
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: 13 Mar 2020 *