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

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$ 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 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.

1 Introduction

Set Covering Problems (SCPs) naturally arise alongside diverse human activities in conservation biology, environmental science, computer science, and management science. They have contributed to an increased need for combinatorial mathematical optimization of generalized covering models. An SCP instance includes a finite set of items that are grouped into a family of subsets such that each item in the set is to be included in at least one subset of the family. The goal of the single-objective SCP (SOSCP) is to determine a subset of sets from the family, including each item in at least one set such that the total cost associated with the selected sets is minimized. Numerous studies have now been developed to solve the SOSCP.

Since SCP applications with multiple conflicting objective functions are more realistic, Jaszkiewicz [21] in 2003 introduced a generalization to the SOSCP by adding multiple conflicting linear objective functions. This extended problem is known as the multi-objective SCP (MOSCP). The optimality concepts in multi-objective optimization problems (MOPs) view competing solutions in terms of trade-offs concerning the multiple conflicting objectives rather than in terms of a clearly defined hierarchy of preferences between solutions, as implied in single-objective optimization. Incompatibility between any two solutions in multi-objective optimization is typical. Therefore, the challenge of verifying optimality within a single-objective environment due to the solution set’s combinatorial structure increases when lifted into a multi-objective context. The MOSCP is one such example of note, and even its single objective counterpart is known to be NP-hard [23] as a combinatorial optimization problem.

In a multi-objective context, the concept of “optimum” has to be revisited. Instead of providing only one optimal solution, the approaches applied to MOPs should produce a set of solutions, known as Pareto optimal solutions. The Pareto optimal solutions form the Pareto set [8]. These solutions are optimal because there is no other better solution when all objective functions are taken into consideration. However, computing the exact Pareto set requires substantial computational effort to solve large-scale MOPs. Hence, approximation algorithms such as local search algorithms [1, 36], variable neighborhood search algorithms [27, 28], colony optimization algorithms [14, 24] are often used to estimate the Pareto sets of the MOPs. The approximations are commonly referred to as nondominated sets. A survey of such methods before the year 2000 can be found in [7, 9, 42]. Approximating the Pareto set of the MOSCP has received growing interest in the last two decades. In 2003 and 2004, Jaszkiewicz [21, 22] proposed the Pareto memetic algorithm (PMA) for multi-objective combinatorial optimization (MOCO) problems and used the MOSCP as a benchmark MOCO problem to analyze the performance of the PMA. In 2006, Prins et al. [37] proposed a two-phase algorithm to approximate the Pareto set of the bi-objective SCP. In 2011, Lust et al. [28] proposed a very large-scale neighborhood search method for solving MOCO problems and used the MOSCP as a benchmark problem to evaluate their performance. In 2014, Lust and Tuyttens [29] applied an improved version of the very large-scale neighborhood search method to the MOSCP. In 2014, Florios and Mavrotas [12] proposed an exact algorithm to compute the Pareto sets of multi-objective integer programs and used the MOSCP to verify the accuracy of the algorithm. In 2017, Weerasena et al. [47] proposed a heuristic algorithm that partitions the feasible region of the MOSCP by adding branching constraints to produce subproblems of the MOSCP and approximating the Pareto set of the MOSCP with the help of the subproblems. In 2018, Weerasena and Wiecek [46] proposed an algorithm called the $\epsilon$-approximation algorithm to approximate the MOSCP with a mathematically proven error bound.

Although the MOSCP focuses on covering each item at least once, the real-world applications of the SCP—such as vehicle routing, crew scheduling, and logical analysis of data [2, 3, 6, 16, 25, 30,31,32, 34, 38, 39, 45]—requires more than one set to cover each item (multiple covers). These problems are formulated as SOSCPs with generalized coverage constraints. In 2020, Weerasena [44] introduced a generalized MOSCP (GMOSCP) by adding generalized coverage constraints to the MOSCP, and proposed a heuristic algorithm to solve a reserve site selection problem in conservation biology with appropriately defined objective functions and coverage constraints.

In this study, we focus on approximating the Pareto set of the GMOSCP. The generalized coverage constraints and the multiple conflicting objective functions add an extra level of difficulty to this task. We propose an algorithm that depends on constructing and solving the GMOSCP subproblems through branching of the feasible region. The algorithm can be explained using a tree structure, and each node of the tree refers to a subproblem of the GMOSCP. The branching-algorithm inspired the development of our algorithm to solve single-objective mixed-integer optimization problems presented in [11]. This algorithm was applied to approximate the Pareto set of bi-objective mixed 0–1 integer linear programming problems in [40]. This algorithm is also successfully integrated into the algorithm proposed in [47] to approximate the Pareto set of the MOSCP. Our study presents a novel mathematically-driven heuristic algorithm to approximate the Pareto set of the GMOSCP by exploring the subproblems described by each node of the tree. Our search method identifies solutions established on two lexicographic rules for obtaining feasible solutions, and it is called the Lexicographic-Order Local Search (LOLS) algorithm.

In this paper, we argue that the number of sets needed to cover each item must be also be taken into consideration when the set selection rules are defined for the GMOSCP, since each item has multiple coverage requirements. This is the distinguished difference between the MOSCP approximation algorithms and the GMOSCP approximation algorithms. Our two lexicographic set rules are specially designed for this generalized case. The algorithm has three components, (1) initial stage, (2) constructive stage, and (3) improvement stage. The algorithm starts with a set of feasible solutions provided by the initial stage. The typical approach in obtaining solutions for the MOPS involves using certain replacement scalarizing functions that may depend on the objective values and also on some additional parameters.

In this study, we use achievement scalarization functions (ASF) proposed in [49], using a reference point and composite weighted $l_1$ and $l_\infty$ norms of the objective functions to scalarize the objective weight of the GMOSCP at the initial stage. We consider several scalarizations of the objective function vector using uniformly distributed weight vectors based on scalarizing achievement functions [10] concerning one reference point. We then solve the corresponding single-objective optimization problem, which is a common approach used in many earlier proposed algorithms [5, 13, 18, 20, 47] to obtain an initial feasible solution set. The advantage of using the reference points scalarization functions approach is that it benefits large-scale MOPs when approximating the Pareto sets in a parallel algorithmic framework [10].

In the constructive stage, we apply the local branching constraints to construct subproblems as in [11]. The branching constraints are defined based on Hamming distance [17], which is the absolute difference between a preferred solution $\bar{x}$ and a candidate solution x. Given the Hamming distance search length L, we add the branching constraints $N(\bar{x},x)\le L$ and $N(\bar{x},x)> L$, where N denotes the search space to partition the feasible region. The branching constraint $N(\bar{x},x)\le L$ with the regular GMOSCP constraints define subproblems of the GMOSCP. If the search space of the subproblem is not examined intensively, the opportunity of finding better solutions to the GMOSCP can be lost. To overcome such issues, our algorithm will ensure an extensive examination of each search space of the subproblem. Each search space is extensively searched for new solutions by performing several searches. The search region with $N(\bar{x},x)> L$ along with the regular GMOSCP constraints continued to be partitioned with respect to newly identified solutions. The partitioning of the feasible region of the GMOSCP using the branching constraints can be explained using tree-search strategy [11]. In the improvement stage, we examine each feasible solution further and improve the value of the objective vector by removing redundant sets.

In [26], the authors argued that due to the bias introduced by the cost-efficient rule of the SOSCP, the feasible solutions may converge to a local optimum instead of a global optimum in some problem instances; altering the cost-efficient rules is a meaningful strategy to reach the global optima in SOSCP. These authors used the cost-efficient rule defined in [4], which identifies the best sets based on a ratio determined by the cost over the number of uncovered items of sets. It is proven that the Chvátal’s [4] greedy algorithm obtains a feasible solution within $\log m$ error terms, where m is the number of items in the test problem. Since the results yielded by this algorithm are very close to the optimal solutions, the study in [26] introduced slight modifications to Chvátal’s [4] cost-efficient rule, which is also a motivation from [43], and showed that their heuristic best performs on the SOSCP among the heuristics based on the solution quality. Encouraged by this research on the SOSCP, we extend some of these rules for the GMOSCP and investigate their effects when approximating the Pareto set. We discover that having reasonably well multiple priority rules in the LOLS algorithm results in a better approximation for the GMOSCP. Our experimental analysis shows that all components of the algorithm are important for the success of the algorithm. For example, our results indicate that the two lexicographic set selection rules yield a significant improvement in the approximation quality. Besides, the experimental analysis gives insight into specific components’ behavior, such as increasing either the number of scalarizations or the number of searches of the subproblems.

We have used a diverse set of GMOSCP instances with different parameter settings for the computational experiments. The GMOSCP can be reduced to an MOSCP by setting the number of sets needed to cover each item to one. Thus, the LOLS algorithm can be used to approximate the Pareto set of the MOSCP. We also analyzed the effectiveness of the LOLS algorithm with existing MOSCP algorithms. Our experimental comparison of the LOLS algorithm with the LB-AI algorithm shows that LOLS performance is very competitive or often superior on benchmark test problems.

The rest of this paper is arranged as follows: Sect. 2 describes the preliminaries on MOPs and the problem formulations. This section also provides the weighted-sum function and achievement scalarization function scalarization approaches of MOPs needed for our study. Section 3 provides the multiple cost-efficient rules and the approximation algorithm based on lexicographic set selection-rules. Section 4 provides the experimental setups, performance metrics, and test instances. Section 5 provides the results of the empirical analysis. We conclude the paper in Sect. 6.

2 Preliminaries and related background

Let ${\mathcal {R}}^p$ be a p Euclidean vector space. For two vectors $y^1, y^2 \in \mathcal {R}^p$, we write $y^1\leqq y^2$ if $y^1_q\le y^2_q$ for $q=1,\ldots ,p$; $y^1\le y^2$ if $y^1_q \le y^2_q$ for all $q=1,2,\ldots ,p$ and $y^1 \ne y^2$; and $y^1 < y^2$ if $y^1_q < y^2_q$ for all $q=1,2,\ldots ,p$. The nonnegative orthant of $\mathcal {R}^p$ is defined as $\mathcal {R}^p_\geqq =\{y\in \mathcal {R}^p: y\ge \underline{0}\}.$

Let $f:\mathcal {R}^n \rightarrow \mathcal {R}^p$ be an objective vector and let $Q=\{ q \ : \ q=1,2,\ldots ,p\}$ be an index set. A multi-objective optimization problem (MOP) is defined as below.

$$\begin{aligned} \begin{aligned} \text {min}\ f(x)= \displaystyle (f_1,\ldots ,f_p) \ \ \text { subject \ to }\ x \in X, \end{aligned} \end{aligned}$$

(1)

where $f_q:\mathcal {R}^n \rightarrow \mathcal {R}$ for $q\in Q$ is a scalar-valued function and x is feasible solutions in the the feasible set X. The outcome space Y is obtained by evaluating the p objective functions for $x\in X$. That is, $Y := f(X) \subset \mathcal {R}^p$.

The commonly used partial order optimality concept in multi-objective optimization is Pareto efficiency (or simply efficiency). A solution $x^* \in X$ is called an efficient solution for the MOP if there does not exist $x \in X$ such that $f(x) \le f(x^*)$. The image $f(x) \in Y$ of an efficient solution is called a Pareto outcome. We denote the set of all efficient solutions by $X_E$. The image of $X_{E}$ is denoted by $Y_p=f(X_E)$ and is referred to as the Pareto set [8]. A comparison of vectors can be used to check domination between any two elements in $Y\subset \mathcal {R}^p$.

Definition 1

If $x_1, x_2 \in X$ and $f(x_1) \le fx_2)$, then $x_1$ is said to dominate $x_2$ and $y_1 = f(x_1)$ is said to dominate $y_2 = f(x_2)$. An element $y^* \in Y$ is called a nondominated point of Y if there does not exist $y \in Y$ dominating $y^*$.

The ideal objective vector of an MOP can be defined as follows.

Definition 2

The ideal objective vector ${f}^{id}=(f_1^{*},\ldots ,f_p^*)$ is computed by

$$\begin{aligned} f_q^*=\underset{x\in X}{\min } \ f_q(x), \ q \in Q \end{aligned}$$

(2)

Below, we define the GMOSCP.

2.1 Generalized multi-objective set covering problem

The following notations are common in related SCP studies, and we use them throughout this text.

• 1. The set of m items $E =\{ e_1, e_2,\ldots ,e_m\}$ with the index set $I=\{i:i=1,2,\ldots ,m\}$

• 2. A family of n subsets of E, $S=\{ S_1,S_2,\ldots , S_n\}$ with the index set $J=\{ j \ : \ j=1,2,\ldots ,n\}$,

The GMOSCP is conceptually defined here as in Weerasena [44]. Let $a_{ij} = 1$ if $e_i \in S_j$ holds and $a_{ij} = 0,$ otherwise. Let $x\in \{0,1\}^n$ be the decision variable, such that $x_j=1$ if $S_j$ is selected to cover an item and $x_j=0$ otherwise. Symbolically, the GMOSCP is defined as below.

$$\begin{aligned} \begin{aligned} \text {min}\ f(x)= \displaystyle \bigg [f_1=\sum _{j\in J} c^1_j x_j,\ldots , f_p=\sum _{j\in J} c^p_j x_j\bigg ]&\text { subject \ to }\ x \in X\\ \end{aligned} \end{aligned}$$

(3)

where $c^q_j$ denote the cost of set $S_j$ regarding the objective function q for $q \in Q$, $f_q$ is a real-valued linear function such that $f_q:\{0,1\}^n \rightarrow \mathcal {R}$ and

$$\begin{aligned} \displaystyle X=\bigg \{x \in \{0,1\}^n: \sum _{j\in J}a_{ij}x_j \ge b_i \ \text {for} \ i \in I , \text {where} \ b_i>1 \ \text {for at least one} \ i \in I\bigg \}. \end{aligned}$$

(4)

The distinguishable difference between the MOSCP and the GMOSCP is the multi-cover constraint in which the coverage requirement is greater than one for at least one item. Using matrix notation, the GMOSCP can be written as

$$\begin{aligned} \min \ Cx \ \text {subject to } \ Ax\geqq b \end{aligned}$$

(5)

where $A\in \{0,1\}^{m \times n}$ is a matrix such that $a_{ij}$ denotes the entry at the $i^{th}$ row and $j^{th}$ column of a matrix A, $C\in \mathcal {R}^{p \times n}$ is a matrix such that $c^q_j$ denotes the element at the $q^{th}$ row and $j^{th}$ column of the matrix C.

2.2 Exact methods

The approximation algorithm proposed in this study is developed based on the scalarizations of the objective function vector with respect to the Weighted-Sum Method and the Achievement Scalarizing Method, which are exact methods for finding efficient solutions of MOPs.

2.2.1 Weighted-sum scalarization

Let $\lambda =(\lambda _1,\ldots ,\lambda _p)^T\in \mathcal {R}^p_{\ge }$ be a weight vector containing weighting coefficients of the objective functions and, typically, $\lambda$ is normalized such that $\displaystyle \sum _{q\in Q}\lambda _q=1$. The scalarized GMOSCP with the weighted-sum scalarization with respect to the weight vector $\lambda$ can be written as follows:

$$\begin{aligned} \begin{aligned} \displaystyle \text {min}&\ f_{ws}(\lambda )= \ \sum _{q\in Q} \lambda _q f_q \\ \text { subject \ to }&x \in X. \end{aligned} \end{aligned}$$

(6)

where $f_{ws}(\lambda )$ denotes the scalarized weighted-sum objective function.

We obtain the relaxed weighted-sum problem in (6) by replacing the binary variables $x_j$ for $j\in J$ with nonnegative variables $x_j\ge 0$ for $j\in J$ as shown in (7)

$$\begin{aligned} \begin{aligned} \displaystyle \text {min}\ f_{rws}(\lambda )=&\ \sum _{q\in Q} \lambda _q f_q \\ \text { subject \ to }&x \in \bar{X} \end{aligned} \end{aligned}$$

(7)

where $f_{rws}(\lambda )$ denotes the relaxed weighted-sum objective function and

$$\begin{aligned} \displaystyle \bar{X}=\bigg \{x \in \mathcal {R}^n: \sum _{j\in J}a_{ij}x_j \ge b_i \ \text {for} \ i \in I , \text {where} \ b_i>1 \ \text {for at least one} \ i \in I\bigg \}. \end{aligned}$$

(8)

2.2.2 Achievement scalarization function

The technique of ASFs [48] performs well with reference points [10] that represent acceptable values for the objective functions. Let $F{(f|f^0,\lambda ,\rho )}: Y \rightarrow \mathcal {R}$ be a function, $f=(f_1,f_2,\ldots ,f_p)^T$ be an objective vector and $f^0=(f^0_1,f^0_2,\ldots ,f^0_p)^T\in Y$ be a reference point. The ASF, which is a combination of weighted $l_1$ and $l_\infty$ norms of the objective function vector, is defined as

$$\begin{aligned} F{(f|f^0,\lambda ,\rho )}=\underset{q\in Q}{\max }\bigg \{\lambda _q(f_q-f_q^0)\bigg \}+\rho \sum _{q\in Q} \lambda _q (f_q-f_q^0) \end{aligned}$$

(9)

where $\lambda =(\lambda _1,\ldots ,\lambda _p)\in \mathcal {R}^p_{\ge }$ is a vector containing weighting coefficients of the objective functions and $\rho$ is an arbitrary small positive number. We define the corresponding achievement optimization problem for the GMOSCP as

$$\begin{aligned} \begin{aligned} \underset{}{\min } \ F{(f|f^0,\lambda ,\rho )}=\underset{q\in Q}{\max }\bigg \{\lambda _q(f_q-f_q^0)\bigg \}+\rho \sum _{q\in Q} \lambda _q (f_q-f_q^0)\\ x\in X \end{aligned} \end{aligned}$$

(10)

Proposition 2.1

If $f^0$ is a reference point, then the model (10) provides an efficient solution $x^*$ for a given weight vector $\lambda$, and if $x^*$ is an efficient solution, then there exists a function $F{(f|f^0,\lambda ,\rho )}$ [41].

To find the optimal solution of the model in (10), we optimize the following equivalent problem.

$$\begin{aligned} &\quad\underset{}{\min }\, \theta \\ &\text {subject to}\, \lambda _q(f_q-f_q^0)+\rho \sum _{q\in Q} \lambda _q (f_q-f_q^0)\le \theta \ \forall \ q\in Q \\&\qquad x\in X \ \text {and} \ \theta \ \text {is a free variable} \end{aligned}$$

(11)

Using different weight vectors $\lambda$ for the same reference point $f^0$ leads to different optimal solutions for the achievement problem defined in (11). It is important to mention that this model has p number of additional constraints and one additional free variable compared to the classical weighted-sum method discussed in Sect. 2.2.1. Next we discuss the design of the algorithm.

3 Design of the approximation algorithm

In this section we present our definitions of lexicographic set selection rules and multiple cost-efficient rules.

Definition 3

A vector $\bar{x}\in \{0,1\}^n$ is called a partial solution if $\bar{x} \notin X$.

The proposed algorithm adds sets to convert the partial solution $\bar{x}\in \{0,1\}^n$ to a feasible solution $\bar{x} \in X$. The sets are identified using two priority preferences: (1) cost-efficient preference and (2) coverage-efficient preference. We use these two preferences according to the lexicographic order preference.

3.1 Lexicographic set selection rules

Let $\bar{x}$ be a partial solution and $\bar{b}=(\bar{b}_1,\ldots , \bar{b}_m)^T$ be the corresponding coverage. The additional number of sets needed to obtain a feasible solution from $\bar{x}$ is given by $b^T-\bar{b}^T=(b_1-\bar{b}_1,\ldots ,b_m-\bar{b}_m)^T$. An item $e_i$ for $i\in I$ is said to be covered if $b_i-\bar{b}_i\le 0$. Let $\bar{J}$ contain the indices of the sets selected for the partial solution $\bar{x}$ and $\bar{I}$ contain the indices of the covered items by the partial solution $\bar{x}$, respectively. We use Definitions 4 to 6 to define our lexicographic rules.

Definition 4

(Set Density) Let $S_j$ be a set for $j\in J\setminus \bar{J}$. The set density of $S_j$, denoted $s_j^d$, is defined as the number of uncovered items in the set $S_j$. That is,

$$\begin{aligned} s_j^d= |\{i\in I\setminus \bar{I}:a_{ij}=1\}|. \end{aligned}$$

The set density vector is denoted by $s^d=(s^d_1,s^d_2,\ldots ,s^d_n)^T\in \mathcal {Z}^n$. The set density $s_j^d$ is zero if the set $S_j$ is selected for a solution.

When selecting additional sets to cover uncovered items in SCPs, the cost of a set and the number covered by the set play major roles. Since our main goal is to minimize the total cost of selected sites, cost-efficient approaches should give a higher priority to the cost coefficients $c_j^q$ for $q\in q$ and $j\in J$ of the GMOSCP. Further, the set density defined in Definition 4 is related to the number of items in the set, but it is a dynamic factor for our algorithm as it changes from iteration to iteration. We describe this fact later in more detail. The multiple cost-efficient rules introduced for the SOSCP in [26] are functions of the cost coefficients and the items contained in the sets. Motivated by the [26] study, we define four different cost-efficient rules for the GMOSCP as functions of cost coefficients and set densities.

Definition 5

Let $\lambda \in \mathcal {R}^p_{\ge }$ be a weight vector. Let $\sum _{q\in Q}\lambda _q c^q_j$ and $s_j^d$ be the scalarized cost and the set density of the set $S_j$, respectively. The four cost-efficient rules are denoted as $g_1( \lambda , c_j), \ g_2( \lambda , c_j), \ g_3( \lambda , c_j)$ and $g_4( \lambda , c_j)$ where,

$\displaystyle g_1( \lambda , c_j)=\frac{\sum _{q\in Q}\lambda _q c^q_j}{s^d_j}$, $\displaystyle g_2( \lambda , c_j)=\frac{\sum _{q\in Q}\lambda _q c^q_j}{(s^d_j)^2}$,

$\displaystyle g_3( \lambda , c_j)=\frac{\sqrt{\sum _{q\in Q}\lambda _q c^q_j}}{s^d_j}$, and $\displaystyle g_4( \lambda , c_j)=\frac{\sum _{q\in Q}\lambda _q c^q_j}{\sqrt{s^d_j}}.$

The classical cost-efficient rule introduced by Chvátal et al [4] for the SOSCP identifies the best sets based on a ratio determined by the cost over the number of uncovered items of sets. Thus, the ratio is calculated by a fractional term in which the denominator and numerator consist of linear terms. Motivated by the multiple cost-efficient rules proposed in [26], we investigate whether there is a better relationship between cost-efficient value and set density other than this linear relationship for the GMOSCP. We have designed these rules to investigate the best relationship between the cost-value and the set density. The cost-efficient rule $g_1$ is a linear fractional rule while the cost-efficient rules $g_2,g_3,g_4$ are non-linear fractional rules. The rule $g_1$ considers the linear combination of all cost values over the set-density. In rules, $g_2, g_3, g_4$, we have non-linear terms either in the numerator or the denominator. With the cost-efficient rule $g_4$, we prioritize the cost-value considering a non-linear fractional term. Thus, in contrast to cost-efficient rules $g_1,g_2,g_3$, $g_4$ enable us to enables us to provide more priority for the cost-efficient value. We analyze their effects in Sect. 5.

Since the GMOSCP requires different multiple coverage for each item, we argue that the residual vector $b^r$, defined in Definition 6, plays a vital role in the number of selected sets in addition to these cost-efficient rules.

Definition 6

(Residual Vector with respect to a set) Let $S_j$ for $j\in J\setminus \bar{J}$ be an unselected set for a partial solution of the GMOSCP and $b^{j}\in \{0,1\}^m$ be the coverage of the set j. The residual vector $h(j)\in Z^m$ associated with the set $S_j$ is defined as $h(j)=\bar{b}-b^{j}$, where $\bar{b}$ is the coverage of a partial solution.

Although the cost-efficient sets are the main priority, the number of additional sets needed to satisfy the coverage of items provided by Definition 6 indirectly supports the cost-efficient rules provided in Definition 5. Therefore, we observe a conflict between the cost efficiency of a set and the residual value of an item. We select sets based on lexicographic order preferences which arises, obviously, when such conflicting objectives exist in a decision problem. This optimization ranks preferences by ordering the objective functions according to the importance of the decision maker. For our study, we define the lexicographic orders for the set selection as in Definitions 7 and 8.

Definition 7

(Lexicographic Order 1 (LO1)) Let $j_1,j_2\in J\setminus \bar{J}$ be two unselected sets for a partial solution of the GMOSCP and $\lambda \in \mathcal {R}^n_\ge$ be a weight vector. We say that the set $j_1$ is preferred over the set $j_2$ with respect to the cost-efficient rule $g_k$, denoted by $j_1 \underset{LO1}{\succeq } j_2$, if $g_k(\lambda , c_{j_1}) \le g_k(\lambda , c_{j_2})$.

Let $J_{best}$ denote the indices of the cost-efficient sets that can be used to cover the items $e_i\in I\setminus \bar{I}$ for a specified weight vector $\lambda \in \mathcal {R}^p_{\ge }$ according to LO1. Then $J_{best}(\lambda )$ is defined as $J_{best}(\lambda )=\arg \ \underset{S_j: e_i\in S_j}{\min } \bigg \{ g_k(\lambda , c_j)\bigg \} \ \text {for} \ k \in K=\{1,2,3,4\}$.

Definition 8

(Lexicographic Order 2 (LO2)) Let $b^r=b-\bar{b} \in \mathcal {Z}^m$ be a residual vector and $\lambda \in \mathcal {R}^n_\ge$ be a weight vector. Let $j_1,j_2\in J\setminus \bar{J}$ be two unselected sets for a partial solution of the GMOSCP. Let $h({j_1})=b^r-b^{j_1}\in \mathcal {Z}^m$ and $h({j_2})=b^r-b^{j_2} \in \mathcal {Z}^m$ be the two residual vectors associated with the set $j_1,j_2\in J\setminus \bar{J}$, respectively. We say that the the set $j_1$ is preferred over the set $j_2$, denoted by $j_i \underset{LO2}{\succeq } j_2$, if $\ \sum _{i\in I\setminus \bar{I}}h({j_1}) \le \sum _{i\in I\setminus \bar{I}}h({j_2})$.

We provide the following example to justify the importance of both orders, LO1 and LO2.

Example 01

Let’s consider an instance of a GMOSCP. Let $E=\{e_1,e_2,e_3,e_4\}$ be a set of four items ($m=4$) and $S_1=\{e_1,e_2\}$, $S_2=\{e_1,e_2,e_4\}$, $S_3=\{e_3,e_4\}$, $S_4=\{e_1,e_3\}$, $S_5=\{e_2\}$, $S_6=\{e_1,e_3\}$, $S_7=\{e_2,e_4\}$ be seven subsets of E ($n=7$) with cost vectors $c^1=(3, 1, 8, 10, 1,5,3)$ and $c^2=(4, 1, 5, 2,2, 10, 4)$, respectively. Let $b=(2,1,2,1)^T$ be the coverage vector and $\lambda =(0.6,0.4)^T$ be a weight vector. The initial set density vector is $s^d=(2,3,2,2,1,2,2)^T$. Assume that $\bar{x}=(0,1,0,0,0,0,0)^T$ is a partial solution. The corresponding coverage of $\bar{x}$ is $\bar{b}=(1,1,0,1)^T$. The updated set density and the residual vectors are $s^d=(1,0,1,2,0,2,0)^T$ and $b^r=(1,0,2,0)^T$, respectively. We obtain $\bar{J}=\{2\}, \bar{I}=\{2,4\}$. Left and right graphs in Fig. 1 illustrates the given GMOSCP and the updated GMOSCP with respect to $\bar{x}$, respectively.

Fig. 1

Graphical Illustration of Example 01

We illustrate the procedure for converting this partial solution $\bar{x}$ by first applying only rule LO1 and then applying both rules LO1 and LO2. First note that $b^{r}_{2}\le 0$ and $b^{r}_{4}\le 0$. Thus, we remove the items $e_2,e_4$ from further consideration. We find $J_{best}(\lambda )$ for the sets with $s^{d}_j \ne 0$ using the cost-efficient function $g_1(\lambda , c_j)$ defined in Definition 5.

$$\begin{aligned} \begin{aligned} J(\lambda )=&\arg \ \underset{S_j: e_i\in S_j}{\min } \bigg \{ \frac{0.6*3+0.4*4}{1},\frac{0.6*8+0.4*5}{1}, \frac{0.6*10+0.4*2}{2}, \frac{0.6*5+0.4*10}{2} \bigg \}\\ =&\{1,4\}. \end{aligned} \end{aligned}$$

(12)

Based on Definition 7, the two sets $S_1$ and $S_4$ from Eq. (12) are equally likely to be selected.

Case 1: Apply only LO1

• 1. Assume that we selected the set $S_1$. We update the density and the residual vectors. Then the partial solution $\bar{x}=(1,1,0,0,0,0,0)^T$ and the coverage of the set $S_1$ is $b^1=(1,0,0,0)^T$. The updated residual vector $b^r=(0,0,2,0)^T$. Since $b^r_1\le 0$ we remove the item $e_1$ from further consideration, and the updated set density is $s^d=(0,0,1,1,0,1,0)^T.$ The only uncovered item at this stage is item $e_2$, since $b^r_2=2$, which implies that we need to add two more sets to cover this item.

• 2. Consider $J(\lambda )=\arg \ \underset{S_j: e_i\in S_j}{\min } \bigg \{ \frac{0.6*8+0.4*5}{1}, \frac{0.6*10+0.4*2}{1}, \frac{0.6*5+0.4*10}{1} \bigg \}=\{3,4\}$. Based on Definition 7, the two sets $S_3$ and $S_4$ are equally likely to be selected. Assume that we select the set $S_3$. We update the density and the residual vectors. Then $\bar{x}=(1,1,1,0,0,0,0)^T$ and the coverage of the set $S_3$ is $b^3=(0,0,1,0)^T$. The updated residual and the density vectors are $b^r=(0,0,1,0)^T$ and $s^d=(0,0,0,1,0,1,0)^T,$ respectively. We observe that $b^r_2=1$, which implies that we need to add one more set to cover this item.

• 3. Consider $J(\lambda )=\arg \ \underset{S_j: e_i\in S_j}{\min } \bigg \{ \frac{0.6*10+0.4*2}{1}, \frac{0.6*5+0.4*10}{1} \bigg \}=\{4\}$. We select $S_4$ and update the residual vector $b^r=(0,0,0,0)^T$. Since $b^r_i\le 0$ for all $i\in I$, we have a feasible solution $x=(1,1,1,1,0,0, 0)^T$ for the GMOSCP. The corresponding objective vector is $f(x)=(22,12)^T$.

Case 2: Apply LO1 and LO2

• 1. The sets $S_1$ and $S_4$ from Eq. (12) are equally likely to be selected. Since $|J_{best}(\lambda )|>1$ with LO1, we consider LO2. We find $\sum _{i\in I\setminus \bar{I}} h(j_1)=2$ and $\sum _{i\in I\setminus \bar{I}}h(j_4)=1$. Since $j_4\underset{LO2}{\succeq }j_1$, we select the set $S_4$. The updated residual and the set density vectors are $b^r=(0,0,1,0)^T$, $s^d=(0,0,1,0,0,1,0)^T$, respectively. Since $b^r_1\le 0$, we remove the item $e_1$ from further consideration. The only uncovered item at this stage is item $e_2$, since $b^r_2=1$, which implies that we need to add one more set to cover this item.

• 2. Consider $J(\lambda )=\arg \ \underset{S_j: e_i\in S_j}{\min } \bigg \{ \frac{0.6*8+0.4*5}{1},\frac{0.6*5+0.4*10}{1} \bigg \}=\{3\}$. We select the set $S_3$, and the updated residual vector is $b^r=(0,0,0,0)^T$. Since $b^r_i\le 0$ for all $i\in I$, we have a feasible solution $x=(0,1,1,1,0,0,0)^T.$ The corresponding objective vector is $f(x)=(19,8)^T$.

This example shows that if we consider only LO1, we use three more steps to obtain a feasible solution from $\bar{x}$; if we use both LO1 and LO2 , we use two more steps to obtain a feasible solution from $\bar{x}$. In fact, we observe that the objective vector $(19,8)^T$ is a nondominated vector comparing to the $\{(19,8)^T,(22,12)^T \}.$ This example highlights the need for using both LO1 and LO2 in the algorithm.

Thus $|J_{best}|>1$ implies that many sets have the same cost-efficient value. Then to identify the best set among the sets with the same cost-efficient values, we select the set that has the highest h(j) value for $j\in J_{best}$ based on LO2. If there is a tie with LO2, we break it arbitrarily.

3.2 Framework of the algorithm

In this section, we describe each component of the proposed approximation method. The lexicographic set selection approach with multiple cost-efficient rules is integrated into the algorithm proposed in [11]. The new algorithm is called LOLS and presented in Algorithm 1. Starting with the initial population, the algorithm returns an approximation $\hat{Y}$ for the Pareto set $Y_p$. The algorithm has two significant steps: Initialization $(Y_{ini},X_{ini})$ and Obtain Approximation set $\hat{Y}$. The Obtain Approximation step consists of five major procedures: (1) Constructing and solving subproblems (SubProblem); (2) Identifying Partial Solution (FindPartial); (3) Checking Coverage of sets (CheckCoverage); (4) Constructing a Feasible solution (ConvertFeasible); and (5) Improving a Feasible solution (ImproveFeasible).

The LOLS algorithm terminates if it does not find any new nondominated solutions after searching all the feasible regions of the subproblems. Thus, we iterate the algorithm after the initial step until we do not find any new nondominated solutions.

3.2.1 Initialization

In the initialization procedure, we construct and solve the achievement scalarization optimization problems given in (11) for the GMOSCP by using some user-defined preference weight vectors. Our preliminary work demonstrated that achievement scalarization optimization problems provided more Pareto points than the weighted-sum optimization problems for the same number of weight vectors. Further, the Pareto points are almost evenly distributed within the Pareto set with this method.

We define the number of weight vectors as a parameter. To obtain a reasonable approximation of the Pareto set, we need to solve a number of scalarized problems [36]. Proposition 2.1 implies that these solutions are efficient solutions of the GMOSCP. Here, we take the ideal point $f^{ideal}$ as the reference point. Thus, $f^{ideal}_q=\underset{x^*\in X}{\min }f_q(x^*)$. We use these efficient solutions as initial solutions $X_{ini}$. We evaluate the objective function $f_q$ for $q\in Q$ at these initial solutions to find the corresponding initial values for $Y_{ini}$.

3.2.2 Construct and solve subproblems

The technique for constructing and solving subproblems of the GMOSCP is given in Procedure 2. This is a divide-and-conquer approach. The procedure divides the GMOSCP into subproblems similar to the original problem and recursively solves the subproblems. The procedure then combines the solutions of the subproblems to solve the GMOSCP. Because divide-and-conquer techniques solves subproblems recursively, each subproblem must be more straightforward than the original problem. There must be a systematic approach to construct subproblems. We now give an explanation of the procedure.

For each solution ${x}^h \in \hat{X}$, the branching constraints, denoted by $N(x^h, x) \le L$ and $N(x^h, x) \ge L+1$, are constructed where $N(x^h,x)\le L$ denotes the neighboring solutions of $x^h$ within L distance. Here the distance L is the Hamming distance [17], which is a positive integer. When $h=1$, the feasible region of subproblem $p^h$ is defined as $X\cap \{N(x^h, x) \le L\}$ and this subregion is searched for new nondominated points. We continue to partition region $X\cap \{N(x^h, x) \ge L+1\}$ by adding the branching constraints defined with respect to new nondominated solutions. For $x^{h+1}\in \hat{X}$ the algorithm considers previously unexplored subregion and partitions it by adding the branching constraint $N(x^{h+1}, x) \le L$ to define the subproblem $p^{h+1}$. The algorithm keeps partitioning the feasible region X until no nondominated solutions are found. The last subregion is searched separately since no more new nondominated solutions are available to continue the partitioning. Each search space is extensively searched for new solutions by performing several searches and the partitioning approach can be explained using a tree structure [11]. To identify the nondominated points in each subregion, we convert the vector objective function to a scalarized objective function $f_{ws}(\lambda )$ using weighted-sum scalarization described in Sect. 2.2.1 and also replace the integer variables with nonnegative variables (relaxed variables). We solve these modified subproblems. Here, for each subproblem, we solve the relaxed problems defined in model 6 for $\lambda \in \Lambda$. The number of relaxed sub-problems defined for each subproblem will be equal to the number of vectors in $\Lambda .$ Then we send the optimal solutions of the subproblems to Procedure 3 to identify the partial solution for the GMOSCP. A set of $\Lambda$ weight vectors can be used in this procedure for the scalarization. However, the size of the set $\Lambda$ is not clear in advance. Therefore, we consider it also as a numerical parameter as described and analyzed in Sect. 5.

3.2.3 Identify the partial solutions

We present the approach for identifying a partial solution in Procedure 3. A partial solution is constructed by identifying desirable sets and updating coverage requirements for items based on the desirable sets using an optimal solution $\bar{x}$ of subproblem $p^h$. Here, we assume that $\bar{x}_j$ is a desirable candidate if $x_j\ge 0.5$. If $\bar{x}_j$ is a desirable candidate for a feasible solution, we make $\bar{x}_j=1$ and add the index j to $\bar{J}$, where $\bar{J}$ is the index set of the selected sets to construct a feasible solution. We also identify the items covered by the set $S_j$ using Procedure 4 and update the corresponding residual values.

3.2.4 Identify coverage

Procedure 4 is used to identify the covered items by a given set and the corresponding residual vector. If the residual value for a given item $e_i$ is nonpositive, that means the coverage requirement of the item has been satisfied. Thus, the procedure adds the corresponding index to the index set of the covered items $\bar{I}$ and set $b^r_i=0.$ We also update the set densities in this procedure.

3.2.5 Construct feasible solutions

We present the approach for constructing a feasible solution in Procedure 5. The partial solution $\bar{x}$ produced by the subproblem $p^h$ is analyzed by this procedure. For the unselected sets $S_j$, for $j\in J \setminus \bar{J}$, the cost-efficient sets are identified using Definition 7 according to a cost-efficient rule $g_k(\lambda ,c_j)$. If $|J_{best}(\lambda )>1|$, then Definition 8 will be used to break the ties. Note that if more than one candidate set is available according to Definition 8, we break the ties arbitrarily and one of the four cost-efficient rules given in Definition 5 will be used. After identifying the best set, the covered items and the updated residual vector are obtained using the CheckCoverage procedure. The algorithm will continue the procedure until all items are covered and it returns a feasible solution based on cost-efficient rule $g_k(\lambda ,c_j)$.

3.2.6 Improve feasible solutions

We present the approach for improving a feasible solution in Procedure 6. The feasible solution $\bar{x}$ produced by the subproblem $p^h$ is improved by this procedure. For each set $j\in J$ such that $\bar{x}_j=1$, we check whether we obtain a feasible solution after removing the set $S_j$. All such sets are identified. We define a scalar cost for each such set $S_j$ as $\sum _{q\in Q}c^q_j$. Then we set $\bar{x}_j=0$ for the solution $\bar{x}$ starting from the highest scalar cost of such sets while maintaining the feasibility of the solution. We note that different preference rules can be used to improve the solutions at this stage.

According to this algorithm, the maximum number of iterations needed to convert an infeasible solution to a feasible solution is ${\sum _{i\in I}b_i}-|x|.$

4 Experimental outline

In this section, we present our test problems and performance metrics used to verify the algorithm’s performance. We also provide our approach to finding weight vectors for scalarizing the objective vector. We used a personal laptop equipped with an Intel I-7 processor and 8 GB memory for implementation.We implement the algorithm using MATLAB 2020 version. We use MATLAB intlinprog function in the initial stage to solve the scalarized optimization problems and lingprog function to solve the relaxed-scalarized optimization problems. Finally, we utilize MATLAB random number generator ‘rng(6)’, where 6 specifies the seed with ‘twister’, to generate random test problems.

4.1 Test problems

In this study, diverse test instances of the GMOSCP are considered as the test problems. We consider two sources for data: test problems from literature and randomly generated test problems. We conducted multiple analyses.

Test problems collected from [19] are called scp(l, m, n), where l, m,  and n stand for the test group, the number of items, and the number of sets in the test instances, respectively. Test problems provided in [19] are designed for the MOSCP with two objectives. Since our algorithm can be applied to the MOSCP, we use it without modification for comparison with the state-of-the-art MOSCP algorithms. For instance, scp(A, 40, 200) means the test instance is from group A and has 40 items and 200 sets. We expanded this data for the GMOSCP. First, we consider $b_i\in [b_l,b_u]$, where $b_l,b_u\in Z_+$ are upper bound and lower bound values for $b_i \ \forall \ i\in I$, respectively, and we identified the total coverage for each item ($\sum _{j\in J}a_{ij}, \ \forall \ i\in I$). If $\sum _{j\in J}a_{ij}\le b_i$ for some $i\in I$, then we set $b_i=1$. This modification guarantees the feasibility of the expanded test problems. These problems are denoted by gscp(l, m, n), where l, m,  and n stand for the test group, the number of items, and the number of sets in the test instances, respectively. Second, we generated random test problems using MATLAB random number generator. We specify m and n. Then we generated a random number $a_{ij}, \ \forall \ i\in I, \ j\in J$. If $a_{ij}\ge 0.5$, we set $a_{ij}=1$, otherwise we set $a_{ij}=0$. If $\sum _{j\in J}a_{ij}=0 \ \text {for some} \ i\in I$, then we set $a_{ij}=1$ for some $j\in J$. We used $b_i\in [b_l,b_u] \ \forall \ i\in I$, and, as before, if $\sum _{j\in J}a_{ij}<b_i \ \text {for some} \ i\in I$, then we set $b_i=1$. This procedure generates feasible GMOSCP test instances. The cost coefficients are generated as $c^q_j\in [c_l,c_u]$, where $c_l,c_u\in Z_+$ are the lower bound and upper bound values, respectively, for $c^q_j$ for $q\in Q,\ j\in J$. These test problems are called rscp(m, n). For instance, rscp(30, 500) means the random test instance with 30 items and 500 sets.

4.2 Performance metrics

We used two metrics that are the most frequently used measures in multi-objective optimization for analyzing the the performance of the LOLS algorithm.

Definition 9

C-Metrics [51] Let $R, S \subset X$ be two solution sets of GMOSCP. The metric $\mathcal {C}(R, S)$ specifies the fraction of the solutions in the set S that are dominated by at least one solution in the set R

$$\begin{aligned} \mathcal {C}(R,S)=\displaystyle \frac{|\{a'' \in S: \exists \ a'\in R: a' \ \text {dominates} \ a'' \}|}{|S|} \end{aligned}$$

The value $\mathcal {C}(R,S)=1$ implies that all solutions in S are dominated by or equal to solutions in R, while the $\mathcal {C}(R,S)=0$ indicates that none of the solutions in S is dominated by solutions in R. It is important to note that when comparing different approximations’ nondominated sets, both $\mathcal {C}(R,S)$ and $\mathcal {C}(S,R)$ have to be considered, since $\mathcal {C}(R,S)$ is not necessarily equal to $\mathcal {C}(S,R)$.

Definition 10

Hypervolume measure [51] The $\mathcal {H}$ measure gives the volume of the portion of the objective space that is dominated by the Pareto set from below and bounded by the nadir point from above. For two sets R and S, the set R is better than the set S with respect to the hypervolume measure if $\mathcal {H}(R) > \mathcal {H}(S)$.

4.3 Number of scalarization to obtain the initial population

Several strategies can be used to find weight vectors in $\Lambda$ for the initial stage and constructive stage of the subproblem. We use the uniformly distributed normalized vectors proposed in [20, 36]. For a weight vector $\lambda \in \Lambda$, each individual component $\lambda _q$ takes one of the values given in the set $\{l/s,\ l=0,1,\ldots , s\}$ such that $\displaystyle \sum _{q\in Q} \lambda _i=1$.

In our study we set $s=10.$ When $p=2$, each component $[\lambda _1,\lambda _2]$ of $\lambda \in \Lambda$ can be written as $[l/s,1-l/s]$, where $l=0,1,\ldots ,10$. Thus we solve 11 scalarized problems using ASF in the initial stage. This guarantees that $\displaystyle \sum _{q\in Q} \lambda _i=1$.

5 Experimental results

In this section, we present the numerical experiments that we conducted to test the LOLS algorithm’s performance in various test instances. In our computational experiments, we analyzed two main components of the LOLS algorithm. Both components are important for the approximation quality. The first component is the neighborhood length denoted by L, and the second component is the effects of the four different cost-efficient rules. We experimented with several values of L and obtained better results for $L=5,6,7$. We did not observe significant improvements for smaller or larger values of L. Therefore, in the following sections, we have included numerical results only for $L=5$ or $L=7$ or both. We also compare the approximations produced by each cost-efficient rule $g_k(\lambda ,x)$ for $k=1,2,3,4$. We denote the approximation sets produced by the four different cost-efficient rules by $\hat{Y}_{g{_k}}$ for $k=1,2,3,4$. We define $\hat{Y}$, the approximation set produced by LOLS, as the nondominated set of $\cup _{k=1}^4\hat{Y}_{g{_k}}$. We provide the values of all the parameters in the corresponding tables.

5.1 Comparisons of priority rules based on $\mathcal {C}$ metric

In this section, each cost-efficient rule’s effect is compared (pair-wise) regarding the $\mathcal {C}$ metric. The results are presented in Table 1 for $L=7$. The set R corresponds to the rule $g_{k_1}$ and the set S corresponds to the rule $g_{k_2}$ for $k_1\le k_2$. Here, the smaller the metric, the better the approximation. The best-performing rule appears in bold. In the case of a tie, neither is bolded. We observe a significant performance difference among the rules when comparing the test instances using the $\mathcal {C}$ metric. It can be observed that the cost-efficient rule $g_4$ outperforms the others on almost all test instances, although $g_1$ performs slightly better than $g_4$ on some instances. The rules $g_2$ and $g_3$ provide the same metric. We observe almost the same performance rate with $L=5$.

Table 1 $\mathcal {C}$-metric values of the approximations obtained by LOLS for $L=7$

5.2 Effect of search length

In this section, the effect of search length on approximations produced by each cost-efficient rule is compared with respect to the $\mathcal {H}$ measures. The results are presented in Table 2 for $L = 5$ and $L=7$. We note that improving the search length did not improve the results significantly for the test problems used in this study. Here, the higher the metric, the better the approximation. The best-performing rule appears in bold. Confirming the observations we made on the $\mathcal {C}$ metric, it can be observed that the cost-efficient rule $g_4$ outperforms the others on most test instances, although rule $g_1$ performs slightly better than rule $g_4$ on a few test instances. This observation confirms that in contrast to cost-efficient rules $g_1,g_2,g_3$, the rule $g_4$ enable us to enables us to provide more priority for the cost-efficient value. We did not observe a significant difference when $\mathcal {H}$ measure was applied to the combined approximation $\hat{Y}$ with $L = 5$ and $L =7$.

Table 2 Comparison of search length L in terms of $\mathcal {H}$ values for various GMOSCP instances

Table 3 summarizes the results of the $\mathcal {H}$ measure. For example, out of 32 gscp(l, p, m, n) test instances, 26 test instances provide a higher $\mathcal {H}$ measure for rule $g_{4}$ when $L=5$ (approximately 81.82%). Overall 81.48% and 88.89% of the total test problems, the rule $g_4$ performs well when $L=5$ and $L=7$, respectively. This analysis also confirms the observation we made based on the $\mathcal {C}$ metric. Overall, the rule $g_4$ outperforms the other rules.

Table 3 Summary of $\mathcal {H}$-measures for $L=5$ and $L=7$

5.3 Computational time of the LOLS

The computational time of the algorithm varies with the size of the test problem and the vector b. Table 4 shows the mean computational times. We group the test instances based on the number of sets. As we had expected, the run time increases as L increases. We observed a significantly high computational time for the test instances with more than 600 sets when $L=7$ compared to when $L=5$. Since we do not observe a dramatic change of the measures with increasing the value of L, our study concludes that a small search length like $L=5$ is enough, though it is an experimental factor.

Table 4 Average computational time using the four classes of increasing problem size over search length

To demonstrate the LOLS algorithm’s computational efficiency, we compared the observed computational times of the LOLS algorithm with existing publications in LB-AI [47], 2PPLS [29], TPM [37], and PMA [22], averaged over types of the MOSCP test instances. The study proposed in [29] provides a table for average computational time comparison for some MOSCP test problems for 2PPLS, TPM, and PMA algorithms. The study proposed in [47] has extended the same table, including LB-AI algorithms computational time. Here, we used the same table format and included the computational time of the LOLS algorithm. As mentioned in [22], we also emphasize that the computational time depends on the computer type, programming language, and implementation style. Table 5 provides this comparison for the average computational times. For example in Table 5, row corresponding to SCP(–,10,100) provides the average time for the test instances of SCP(A,10,100), SCP(B,10,100), SCP(C,10,100) and SCP(D,10,100), respectively. The last two rows of this table provide the computer type. Note that the computational times of LOLS, LB-AI, 2PPLS algorithms are collectively better than the computational times of TPM and PMA. We also note that TPM has been executed on a Pentium IV with 1.8 GHz CPUs 512 MB of RAM [37], and PMA on a computer with 400 MHz [22]. Those computers are slower than the computers used in our study, LB-AI (I-3 processor and 2 GB RAM [47] and 2PPLS (Pentium IV with 3 GHz CPUs [29]). We observe that the LOLS algorithm performs computationally well when comparing these computational times.

Table 5 Comparison of LOLS, LB-AI, 2PPLS, TPM, PMA algorithms average run times

5.4 Comparison with a state-of-the-art algorithm for the MOSCP

We compare the performance of the LOLS algorithm to LB-AI [47], 2PPLS [29], TPM [37], and PMA [21] based on $\mathcal {H}$ measures for the MOSCP. Here, we present the $\mathcal {H}$ measure over nonscaled Pareto points for this comparison. We consider various scp(l, m, n) test problems, and Table 6 provides the corresponding measures. It can be observed that the LOLS algorithm significantly outperforms LB-AI on many instances in terms of $\mathcal {H}$ measure. One of the main differences between the LOLS algorithm and the LB-AI algorithm is constructing the initial solution set. The LOLS algorithm obtains the initial solutions by solving the scalarized GMOSCPs using achievement functions with one reference point. In contrast, the LB-AI algorithm obtained the initial solutions by solving scalarized GMOSCPs using the classical weighted-sum method. From this analysis, we observe that the LOLS algorithm significantly outperforms LB-AI on many instances of the $\mathcal {H}$ measure. This performance illustrates the advantage of integrating the achievement scalarization with a reference point over the classical weighted sum method in the partitioning algorithm proposed in [11]. We also observe that the LOLS algorithm outperforms TPM and PMA all the time and performs better on five test problems out of ten test problems compared to 2PPLS that have been considered in this study based on $\mathcal {H}$ measure.

Table 6 Comparisons with state-of-the-art algorithm on various scp(l, m, n) instances

5.5 Comparison with the Pareto set

We analyzed the performance metrics produced by the LOLS algorithm using the Pareto sets. We computed the exact Pareto outcomes by applying the $\epsilon$-constraint method [15]. We note that improved techniques for computing Pareto sets have been studied in recent literature [12, 33, 35, 50]. The nonscaled $\mathcal {H}$ measures for the benchmark test problems are also provided in [12, 29, 33, 47]. In addition, we provided the scaled (normalized) $\mathcal {H}$ measures for the Pareto sets in the last column of Table 2 and the nonscaled (non-normalized) $\mathcal {H}$ measures in the last column of Table 6 of the LOLS algorithm regarding the Pareto sets. By definition, the $\mathcal {H}$ measure of $Y_P$ is always larger than that of $\hat{Y}$. Based on the numerical data provided in Table 6, we observed that the LOLS algorithm performs well, and it indicates that the $\mathcal {H}$ measures are reasonable. Table 7 provides the comparison based on the $\mathcal {C}$ metric. We showed the results for $\mathcal {C}(\hat{Y}_{g_i},Y_p)$, $i=1,2,3,4$, and for $\hat{Y}$ when $L=7$. We do not show the results for $\mathcal {C}(Y_p, \hat{Y}_{g_i})$ since always $\mathcal {C}(Y_p, \hat{Y}_{g_i})=1$ for $i=1,2,3,4$. Specifically, we note that for the MOSCP cases, we have $\mathcal {C}(Y_p, \hat{Y}_{g_i})>0.5$ for 18 test cases out of 22 test cases. This means the LOLS algorithm finds more than 50% of Pareto points for most test problems. For the GMOSCP test problems we have $\mathcal {C}(Y_p, \hat{Y}_{g_i})>0.4$ for 10 test cases and for other test cases $\mathcal {C}(Y_p, \hat{Y}_{g_i})<0.4$. The GMOSCP is a challenging problem compared to the MOSCP due to the multi-cover constraints, thus difficult to obtain the majority of the Pareto points. Though, compared with $\mathcal {H}$ measures provided in Tables 2 and 6, we observe $\mathcal {H}({\hat{Y}})$ and $\mathcal {H}(Y_p)$ are very close, which implies that the points in the two sets $\hat{Y}$ and $Y_p$ are very close to each other. Thus, we conclude that the LOLS algorithm performs well on the test problems studied here.

Table 7 $\mathcal {C}$- metric comparisons with the Pareto set when $L=7$

6 Conclusion and future work

This paper proposes a novel algorithm, called the LOLS algorithm, that is based on the lexicographic ordering set selection approach to approximating the Pareto set of the GMOSCP. The algorithm is integrated into the branching of the feasible region algorithm proposed in [11] to solve single-objective mixed-integer optimization problems. In LOLS, the distribution of the initial population can be better maintained by abating and solving the scalarized GMOSCPs using achievement functions with a reference point. We investigated the performance of the LOLS algorithm in detail. We considered various test instances from the literature, and we also proposed a method for generating random test instances.

We introduced four different cost-efficient rules to convert partial (infeasible) solutions to feasible solutions. We investigated whether there is a better relationship between cost-efficient value and set density other than the classical linear relationship for the GMOSCP. The cost-efficient rule $g_1$ is a linear fractional rule while the cost-efficient rules $g_2,g_3,g_4$ are non-linear fractional rules. With the cost-efficient rule $g_4$, we prioritized the cost-value considering a non-linear fractional term. Thus, in contrast to cost-efficient rules $g_1,g_2,g_3$, we dicovered that the rule $g_4$ performed well on the GMOSCP. We discovered that having reasonably well multiple priority rules in the LOLS algorithm results in a better approximation for the GMOSCP. In addition, we investigated a better-performing cost-efficient rule for the GMOSCP among the four cost-efficient rules proposed in the study. The GMOSCP can be reduced to MOSCP if $b_i\ge 1$ for all $i\in I$. Thus, we compared the performance of the LOLS algorithm with the state-of-the-art MOSCP algorithms. This comparison shows that the LOLS algorithm significantly outperforms the LB-AI algorithm, the most recent algorithm available in the literature to solve the MOSCP on many problem instances in terms of the $\mathcal {H}$ measure. One of the main differences between the LOLS algorithm and the LB-AI algorithm is constructing the initial solution set. The LOLS algorithm obtains the initial solutions by solving the scalarized GMOSCPs using achievement functions while the LB-AI algorithm obtains the initial solutions by solving scalarized GMOSCPs using the classical weighted-sum method. Comparing the LOLS algorithm with LB-AI, 2PPL, TPM, and PMA shows that the LOLS algorithm is more efficient.

The following are possible areas for further investigation: Investigating other lexicographic cost-selection rules that benefit the GMOSCP is also worth exploring. Also, an ANOVA-type analysis can be used to compare approximations of the Pareto set based on each cost-efficient rule.