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

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.