SimCenter and Department of Mathematics Colloquium
Friday, March 12, 2021 at 2:00 PM
Contact Holley-Beeland@utc.edu for Zoom details.
Design of an algorithm with multiple-cost efficient rules for the generalized multi-objective set cover problem
Lakmali Weerasena (Department of Mathematics – The University of Tennessee at Chattanooga)
Abstract: Set covering optimization problems (SCPs) are relevant and of broad interest since their extensive applications in the real world. This study addresses the generalized multi-objective SCP (GMOSCP), which is an augmentation to the well-known multi-objective SCP (MOSCP) problem. A mathematically driven heuristic algorithm is proposed based on a branching approach of the feasible region to approximate the Pareto set of the GMOSCP. The algorithm consists of a number of components including an initial stage, a constructive stage, as well as 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$ and $l_\infty$ norms of the objective function vector. Uniformly distributed weight vectors defined with respect to this reference point support the constructive stage to produce a more widely and uniformly distributed Pareto set approximation. 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 converging of the approximations. We propose multiple cost-efficient rules in the constructive stage and investigate how they affect approximating the Pareto set. We have used a diverse set of GMOSCP instances with different parameter settings for the computational experiments.
Authors:
Lakmali Weerasena, Department of Mathematics, the University of Tennessee at Chattanooga, 615 McCallie Avenue, Chattanooga, TN 37403-2598, Lakmali-Weerasena@utc.edu,
Aniekan Ebiefung, Department of Mathematics, the University of Tennessee at Chattanooga, 615 McCallie Avenue, Chattanooga, TN 37403-2598, Aniekan-Ebiefung@utc.edu ,
Anthony Skjellum, SimCenter, the University of Tennessee at Chattanooga, 615 McCallie Avenue, Chattanooga, TN 37403-2598, Tony-Skjellum@utc.edu
Leave a Reply