Covers and approximations in multiobjective optimization

Abstract

Due to the growing interest in approximation for multiobjective optimization problems (MOPs), a theoretical framework for defining and classifying sets representing or approximating solution sets for MOPs is developed. The concept of tolerance function is proposed as a tool for modeling representation quality. This notion leads to the extension of the traditional dominance relation to $t\hbox {-}$dominance. Two types of sets representing the solution sets are defined: covers and approximations. Their properties are examined in a broader context of multiple solution sets, multiple cones, and multiple quality measures. Applications to complex MOPs are included.

1 Introduction

In multiobjective optimization problems (MOPs), which occur frequently in many real-world applications, an optimal solution set, also known as the nondominated set, is implied by a partial order or a convex cone associated with the objective space of the MOP [59]. Traditionally, the partial order is based on the Pareto preference which, in case of minimization, is equivalent to the cone being the first quadrant of the objective space [12]. It has been shown in the literature that general convex cones are also beneficial since they provide a tool for modeling decision maker’s preferences. Refer to Noghin [43], Klimova and Noghin [33], Wiecek [58], Hunt et al. [29] for algebraic models of such polyhedral cones, and to Hunt et al. [30] for their applications in engineering design.

The success of applying multiobjective optimization in practice depends, among others, on the ability to compute the elements of the nondominated set. This set is typically large and it is often difficult or even impossible to obtain its exact description. For MOPs with continuous objective and constraint functions defined over a continuous feasible set, the nondominated set is usually infinite. It can be derived analytically only for certain classes of problems [18, 53], and otherwise it has to be approximated. For MOPs with a discrete feasible set, the nondominated set may have a finite number of elements. However, their computation may involve solving ${NP}$ hard problems. In particular, for most multiobjective combinatorial optimization problems the solution set is exponential in the size of the instance in the worst case [10]. In conclusion, even if it is theoretically possible to find the nondominated set, it is often computationally challenging and expensive to do so.

Because of the difficulties related to the structure of the nondominated set and the compounding computational challenges, a large variety of methods have been proposed for computing its elements, and numerous approaches have been developed to representing or approximating this set. All these methods and approaches rely on guaranteed or heuristic algorithms.

The former typically compute actual elements of the solution sets by means of algorithms which provide theoretical proofs for their correctness (refer to Ruzika and Wiecek [49] for a review of such methods for continuous MOPs in the period 1975–2003). Recent methods include the works of Martin et al. [40], Goel et al. [17], Efremov and Kamenev [9], Hartikainen et al. [23, 24]. The quality of discrete representations is discussed in Faulkenberg and Wiecek [15] who define the representation as a subset of the solution set.

Many methods have been proposed for generating approximations of the nondominated set which may contain dominated points but have an a priori guarantee on the approximation quality; some of these are referenced in Sect. 2.3. Heuristic and meta-heuristic methods (such as evolutionary and genetic algorithms) provide approximations of the nondominated set with points that are not necessarily in this set but that are feasible for the MOP and considered acceptable according to a principle or a quality criterion used for the approximation. These methods usually find approximating points quickly but have no proofs of correctness and, thus, are theoretically unsupported (see Coello Coello et al. [6], and many others).

Rules or criteria for evaluating approximation quality evolved from the concept of $\varepsilon \hbox {-}$nondominance that was introduced by Kutateladze [35] to relax additively the original efficiency of the solutions. Other concepts of additive $\varepsilon$-nondominance followed [38, 57]. They were introduced and investigated originally as types of efficiency (refer to Helbig and Pateva [25] for a survey) before they were used for approximation. The general idea behind $\varepsilon \hbox {-}$approximations is that the elements in the solution set are approximately dominated by the elements of the approximating set and the approximation quality is a function of $\varepsilon$.

Discrete $\varepsilon$-approximations of the nondominated set of the MOP have been proposed by various authors. Motivation for those approaches and an overview focusing on defining and measuring approximation quality is discussed in Sayin [51].

Due to the growing interest in approximation for MOPs and many different notions of approximations in the literature, a theoretical framework for defining and classifying sets representing or approximating solution sets for MOPs is proposed in this paper. The notion of representation is understood in a broad sense as any set being representative of the set to be represented, which is more general than the same notion defined by Sayin [51] who requires representations to be subsets of the set being represented. In this paper, the representation is not necessarily a subset of the represented set and its quality can be evaluated with different measures. Two types of sets serving as representations are defined: covers and approximations. A cover is a set so that any element of the set being represented is covered by at least one element in the covering set. Covering is defined here by a relaxed dominance relation using a tolerance function that determines the error or quality of the cover. An approximation set is defined as an inherently nondominated cover [23].

Covers and approximations are studied in a broader context of multiple solutions sets, multiple (constant) cones, and multiple quality measures. Multiple solution sets may result from a decomposition of the original MOP into smaller problems [16]; multiple cones may account for different decision makers having different preferences; while multiple quality measures may result from using different algorithms on the same problem. Properties of covers and approximations are derived for a variety of these cases representing different real-life circumstances. While the notions of $\varepsilon \hbox {-}$dominance had led researchers to the development of various types of approximations, the proposed tolerance function extends the traditional dominance to $t\hbox {-}$dominance in which the dominating element is replaced by its proxy or surrogate that is yield by the tolerance function.

The paper is organized in the following manner. In Sect. 2, common terminology and basic definitions are given, and the definitions of cover and approximation are presented. Their properties are studied in Sect. 3. Relevance of the results is illustrated in the context of decomposable systems in Sect. 4, while Sect. 5 concludes the paper.

2 Definitions and preliminary results

We begin with well established notations and definitions. We then introduce the central concepts of tolerance functions, covers and approximations. Finally, we give examples of tolerance functions and their application to derive covers or approximations.

2.1 Preliminaries

Throughout this paper let ${\mathcal {R}}^p$ be a Euclidean vector space, Y be a nonempty subset in ${\mathcal {R}}^p$, and C be a nonempty cone in ${\mathcal {R}}^p$. A set C in ${\mathcal {R}}^p$ is called a cone if $d \in C$ implies $\lambda d \in C$ for $\lambda \ge 0$. The set Y represents the set of outcomes resulting from an MOP but not explicitly available to the user, while the cone models the decision maker’s preferences.

For $y^1, y^2$ in Y, we use the notation $y^1\leqq y^2$ if and only if $y^1_k \le y^2_k$ for all $k=1,2,\dots ,p; y^1\le y^2$ if and only if $y^1_k \le y^2_k$ for all $k=1,2,\dots ,p$ and $y^1 \ne y^2; y^1 < y^2$ if and only if $y^1_k < y^2_k$ for all $k=1,2,\dots ,p.$ With the relations $\geqq , \ge$, and $>$ defined accordingly, we also define the cone ${\mathcal {R}}^p_{\geqq }:=\{y \in {\mathcal {R}}^p: y \geqq 0 \}$.

Cones are used to define cone-relations between the elements of the set Y, and dominated and nondominated elements in Y [59].

Definition 1

Let $y^1, y^2 \in Y$ and C be a cone in ${\mathcal {R}}^p$. A relation $\leqq _C$ on Y is defined by $y^1 \leqq _{C} y^2$ if and only if $y^2-y^1 \in C$, or equivalently, there exists $d\in C$ such that $d=y^2-y^1 \in C$. Furthermore a relation $\le _C$ on Y is defined by $y^1 \le _C y^2$ if and only if $y^2-y^1 \in C \setminus \{0\}$, or equivalently, there exists $d\in C, d\ne 0$ such that $d=y^2-y^1 \in C$.

When $C={\mathcal {R}}^p_{\geqq }$ is the Pareto cone, $\leqq _C$ and $\le _C$ reduce to $\leqq$ and $\le$, respectively.

Definition 2

A point $y' \in Y$ is called a nondominated point of the set Y with respect to the cone C if there does not exist $y \in Y$ such that $y \le _C y'$. The set of all nondominated points of Y with respect to the cone C is denoted by N(Y, C).

The set N(Y, C) is the solution set of an MOP and our aim in this paper is to represent or approximate this solution set.

We assume the standard conditions guaranteeing both the existence of N(Y, C) [50] and its external stability. This latter property, also called domination property (e.g., Henig [26]), states that any dominated point is dominated by a point in N(Y, C). Standard sufficient conditions for ensuring both properties are C is a pointed closed convex cone and $Y \subseteq {\mathcal {R}}^p$ is a non-empty compact set (see Sawaragi et al. [50]).

If the cone C is the Pareto cone $(C={\mathcal {R}}^p_{\geqq })$, the set N(Y, C) reduces to the well-known Pareto set and is denoted as $N(Y,{\mathcal {R}}^p_{\geqq })$.

A polyhedral cone is defined as follows:

Definition 3

A polyhedral cone is a cone C in ${\mathcal {R}}^p$ for which there exists a $q\times p$ matrix $A \in {\mathcal {R}}^{q\times p}$ such that $C=\{d \in : Ad \geqq 0\}.$

The image of any subset $R \subseteq Y$ under the linear mapping represented by the matrix $A \in {\mathcal {R}}^{q\times p}$ is denoted by $A[R]:=\{ z\in {\mathcal {R}}^q : z=Ay \ , \ y\in R \}$.

2.2 Tolerance function, covers, and approximations

We now present the concepts newly introduced in this paper. We begin with a tolerance function that associates to each element in the set Y its image t(y) representing the largest tolerable deterioration that is acceptable on each component of y. To be well-defined a tolerance must satisfy two conditions as indicated in the following definition.

Definition 4

Let Y be a set in ${\mathcal {R}}^p$ and C be a cone in ${\mathcal {R}}^p$. A vector-valued function $t:{\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ such that

• (1) for all $y \in Y, y \leqq _{C} t(y)$, and

• (2) for all $y^1, y^2 \in Y$ if $y^1 \leqq _{C} y^2$ then $t(y^1) \leqq _{C} t(y^2)$, is called a tolerance function.

Example 1

For $Y \subset {\mathcal {R}}^p_{\geqq }$ and $C={\mathcal {R}}^p_{\geqq }$, the tolerance function $t(y) = \alpha y$, with $\alpha \ge 1$ is well defined. However, for $Y \subset {\mathcal {R}}^p_{\geqq }$ and $C= - {\mathcal {R}}^p_{\geqq },$ or $Y \subset {\mathcal {R}}^p_{\leqq }$ and $C={\mathcal {R}}^p_{\geqq }$, it is not.

The following property of the tolerance function will be useful.

Definition 5

Let Y be a set in ${\mathcal {R}}^p$. A vector-valued function $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ is called an ${A}\hbox {-}$invariant function on Y if $t(Ay)=At(y)$ for all $y\in Y$, where A is a $p\times p$ matrix.

Example 2

Let $Y\subset {\mathcal {R}}^2$ such that $Y=\{(2,3)^T, (1,1)^T\}$, $t_1,t_2: {\mathcal {R}}^2\mapsto {\mathcal {R}}^2$ be two functions defined as $t_1(y)=2y$ and $t_2(y)=2y+(1,1)^T$ for $y\in Y$, and $A=\begin{pmatrix} 2 &{} 3 \\ 1 &{} 2 \end{pmatrix}$. We obtain that $t_1(Ay)=At_1(y)$ for all $y\in Y$. Thus $t_1$ is an ${A}\hbox {-}$invariant function on Y. Let $\bar{y}=(2,3)^T$. We note that $t_2(A \bar{y})= (27, 17)^T, At_2(\bar{y})= (31, 19)^T$, and hence $t_2$ is not an ${A}\hbox {-}$invariant function on Y.

We can then relax the definition of a dominance relation, using a tolerance function, leading to the following definition of t-dominance relations.

Definition 6

Let $y^1, y^2 \in Y, C$ be a cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. A relation $\leqq _{C}^{t}$ on Y is defined by $y^1 \leqq _{C}^{t} y^2$ if and only if $y^1 \leqq _{C} t(y^2)$. Similarly, a relation $\le _{C}^t$ on Y is defined by $y^1 \le _{C}^t y^2$ if and only if $y^1 \le _{C} t(y^2)$.

As indicated in the following proposition, the tolerance function may be used to construct subsets of points, called indifference blocks, such that any two points within a same block t-dominate each other.

Proposition 1

Let B be a set in ${\mathcal {R}}^p$ defined as $B = (l + C) \cap (t(l) - C),$ where l is a point in ${\mathcal {R}}^p, C$ is a convex cone in ${\mathcal {R}}^p,$ and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ is a tolerance function distinct from the identity function. Then for any two points $y, y' \in B$, we have $y \leqq _{C}^{t} y'$.

Proof

Since $y \in B$, we have $y \leqq _{C} t(l)$ which, by Definition 4(1), transitivity of $\leqq _{C}$ due to C being convex, and Definition 6, gives $y \leqq _{C}^{t} t(l)$. Moreover, since $y' \in B$, using similar arguments we have $l \leqq _{C} y'$ and thus $l \leqq _{C}^{t} y'$. Since $\leqq _{C}$ is reflexive we have $t(l) \leqq _{C} t(l)$ and thus $t(l) \leqq _{C}^{t} l$ by Definition 6. Since $\leqq _{C}$ is transitive, so is the relation $\leqq _{C}^{t}$, which gives the result. $\square$

Given a set of attainable outcomes $Y\subset {\mathcal {R}}^p$, it is of interest to represent an arbitrary subset $R \subseteq Y$. We use the concept of t-dominance to define representations called t-covers.

Definition 7

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, C be a cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. A subset S of Y is called a t-cover of R with respect to C if for all $y \in R$ there exists $s \in S$ such that $s\leqq _{C}^{t} y$.

In other words, any element y of R is covered by at least one element in the cover which is at least as good as y up to a given tolerance. Observe that the cover may contain elements which do not belong to R. While the set R to be represented can be any subset of Y, the set N(Y, C) is typically chosen as R.

Fig. 1

t-covers a $C={\mathcal {R}}^2_{\geqq }$, b $C=\{d\in {\mathcal {R}}^2: 3d_1 + 2d_2\ge 0, \ d_1 + 2d_2 \ge 0 \}$

Example 3

Let $Y\subset {\mathcal {R}}^2$ such that $Y=\{y^1=(1,3)^T, y^2=(2,2)^T, y^3=(3,3)^T, y^4=(4,1)^T\}$, and $t: {\mathcal {R}}^2\mapsto {\mathcal {R}}^2$ be a tolerance function such that $t(y)=1.6y$ for $y\in Y$. Assume N(Y, C) is the set R to be represented.

• 1. Let $C={\mathcal {R}}^2_{\geqq }$ and note that $N(Y,C)= \{y^1, y^2, y^4\}$. This set is obviously a t-cover of R, but $\{y^1, y^4\}$ is also a t-cover of R, whereas $\{y^1\}, \{y^2\}$ and $\{y^4\}$ are not (see Fig. 1a).

• 2. Let $C=\{d\in {\mathcal {R}}^2: 3d_1 + 2d_2\ge 0, \ d_1 + 2d_2 \ge 0 \}$. Set $\{y^1, y^2, y^4\}$ is, here again, a t-cover of R. Note, however, that $y^2 \le _C y^4$ and that the resulting nondominated set $N(Y,C)=\{y^1, y^2\}$ is also a t-cover of R. Such t-covers that do not contain any dominated point will be called t-approximations (see Definition 8). It should also be observed that $\{y^1\}$ or $\{y^2\}$, or even $\{y^4\}$ which is dominated, are also t-covers (and t-approximations) of R (see Fig. 1b).

For the given cone and tolerance function, there may exist many $t\hbox {-}$covers. The collection of all t-covers of R with respect to a cone C is denoted by $\mathcal{{C}}_{t}(R,C$). This collection is not empty because it contains R itself, and also any superset of N(Y, C) under a convexity assumption.

Proposition 2

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, C be a convex cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. Then, for any set $S \supseteq N(Y,C)$, ${S} \in \mathcal{{C}}_{t}(R,C$).

Proof

Let $S = N(Y,C)$, then for any $y \in Y$, and thus for any $y \in R$, there exists $s \in S$ such that $s \leqq _{C} y$. Since t is a tolerance function, we have $y \leqq _{C} t(y)$. Since C is convex, relation $\leqq _{C}$ is transitive. Thus we get $s \leqq _{C}^{t} y$, and N(Y, C) is a cover of R. Since any superset of a cover is a cover, the result follows. $\square$

From the previous result, both N(Y, C) and Y are covers of R, when C is convex. Actually, under the same assumption, we prove that covering N(Y, C) is equivalent to covering Y.

Proposition 3

Let Y be a set in ${\mathcal {R}}^p$, C be a convex cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. Then $S \in \mathcal{{C}}_{t}(N(Y,C),C$) if and only if $S \in \mathcal{{C}}_{t}(Y,C$).

Proof

$(\Rightarrow )$ Let $S \in \mathcal{{C}}_{t}(N(Y,C),C$). Then, by Definition 7, there exists $s \in S$ such that $s \leqq _{C}^{t} y$, for any $y \in N(Y,C)$. Let $z \in Y \setminus N(Y,C)$. Then, there exists $y \in N(Y,C)$ such that $y \leqq _{C} z$, which, by Definition 4(2), implies $t(y) \leqq _{C} t(z)$. Thus, we have $s \leqq _{C} t(y) \leqq _{C} t(z)$, which, by transitivity of $\leqq _{C}$, due to C being convex, implies $s \leqq _{C}^{t} z$.

$(\Leftarrow )$ Let $S \in \mathcal{{C}}_{t}(Y,C$). Then, by Definition 7, there exists $s \in S$ such that $s \leqq _{C}^{t} y$, for any $y \in Y$ and thus for $y \in N(Y,C)$, since $N(Y,C) \subseteq Y$. $\square$

Some covers in the collection may contain a large number of points while other covers have small cardinality. It should be noticed that any compact subset of Y, and in particular any infinite subset R, admits covers of finite cardinality.

Proposition 4

Let Y be a set in ${\mathcal {R}}^p, R$ be a compact subset of Y, C be a convex cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. Then there exist finite covers in $\mathcal{{C}}_{t}(R,C$).

Proof

Since R is compact, there exists a finite union of indifference blocks $B_j$, as defined by Proposition 1, such that $\bigcup _{j=1}^k B_j \supseteq R$. Then, selecting from each block one point in Y, when it exists, defines a finite cover. $\square$

The previous result can be made more explicit for the Pareto cone, $C = {\mathcal {R}}^p_\geqq$. In this case, the compact subset R to be represented can be embedded in a hyperrectangle $\prod _{k=1}^p [l_i,u_i]$ where $l_i$ and $u_i$ are lower and upper bounds on values of the ith objective, $i=1,\ldots ,p$. It is then possible to partition the interval $[l_i,u_i]$ into $\ell _i$ subintervals $[l_i,t_i(l_i)), [t_i(l_i),t_i^2(l(i)), \ldots ,[t_i^{\ell _i-1}(l_i),t_i^{\ell _i}(l_i))$ with $t_i^{\ell _i-1}(l_i) \le u_i < t_i^{\ell _i}(l_i)$, for each $i = 1,\ldots , p$ where $t = [t_1,\ldots , t_p].$ This defines a hypergrid whose cells correspond to indifference blocks. Then, selecting from each cell of this grid one point in R, when it exists, defines a finite cover.

Also, inside a cover, some points may dominate other points. The points making up the cover can be classified into two groups, dominated points and nondominated points. As it is shown in Proposition 7, by removing all dominated points from a cover, the reduced set remains a cover, which motivates the following definition. If a cover does not contain any dominated points then this set is referred to as an approximation. In Hartikainen et al. [23], a set S satisfying $N(S,C)=S$ is called an inherently nondominated set.

Definition 8

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, C be a cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. A t-cover $S \in \mathcal{{C}}_{t}(R,C$) such that $N(S,C) = S$ is called a t-approximation of R with respect to C.

Given the cone and tolerance function, a t-approximation in general is not unique. The set of all t-approximations of R with respect to a cone C is denoted by $\mathcal{{A}}_{t}(R,C$).

In the following sections, for brevity we refer to t-covers and t-approximations simply as covers and approximations.

2.3 Examples of tolerance functions

While many tolerance functions can be defined, most of the functions used in the literature are of the following general form:

$$\begin{aligned} t(y) = \alpha ^TI_py + \beta \end{aligned}$$

where $\alpha \ge \mathbf 1 _p,$ $\beta \ge \mathbf 0 _p$, and $I_p$ is the identity matrix, with $Y \subset {\mathcal {R}}^p_{\geqq }$ and $C = {\mathcal {R}}^p_{\geqq }$.

Tolerance functions have been used according to two main perspectives, algorithmic and preference modeling. Even if these perspectives are quite compatible, they reflect different viewpoints and were advocated by different scientific communities.

The algorithmic perspective emphasizes the accuracy of the approximations and the possibility to compute such approximations in polynomial time. In this context, two types of tolerance functions have been studied, multiplicative and additive.

A widely studied multiplicative tolerance function assumes the form

$$\begin{aligned} t(y) = (1+\varepsilon )y \end{aligned}$$

where $\varepsilon \ge 0$ represents the accuracy of the description and can be chosen by a user as small as desired. The reason for considering this type of tolerance functions is a result by Papadimitriou and Yannakakis [45] which establishes, under very general conditions and for Pareto cones, the existence of $\varepsilon$-approximations whose cardinality is bounded by a polynomial in the size of the instance and $1/\varepsilon$. They also provide general techniques for constructing such approximations in time polynomial in the size of the instance and $1/\varepsilon$. The generation of $\varepsilon$-approximations of minimal cardinality is also investigated in Vassilvitskii and Yannakakis [55], Koltun and Papadimitriou [34], Diakonikolas and Yannakakis [8], Bazgan et al. [5]. Specific algorithms, providing $\varepsilon$-approximations with polynomial time guarantee, have been devised for specific problems such as the shortest path problem [22, 54, 56], the spanning tree problem [27], the knapsack problem [4, 14], specific scheduling problems [3].

Another multiplicative tolerance function is defined as

$$\begin{aligned} t(y) = \alpha y \end{aligned}$$

where $\alpha$ is a constant depending on the problem. Polynomial time constant approximation algorithms with this type of tolerance function have been proposed for the traveling salesman problem [1, 39], the max-cut problem [2], specific scheduling problems [52].

The additive tolerance function assumes the form

$$\begin{aligned} t(y) = y + \varepsilon \end{aligned}$$

where $\varepsilon \ge 0$ is again selected by the user. Random search algorithms for obtaining $\varepsilon \hbox {-}$approximations based on this function have been proposed [36, 37].

From a preference modeling viewpoint, a tolerance function represents indifference thresholds [47, 48]. An indifference threshold $q_j$ is defined as the largest performance difference on criterion j the decision maker is indifferent about , $j=1,\dots ,p$. Let q be the vector of indifference thresholds, a tolerance function t can thus be defined as

$$\begin{aligned} t(y) = y + q(y) \end{aligned}$$

for all $y \in Y$. Depending on the nature of the criterion, indifference thresholds are chosen either constant or variable. As indicated in Roy et al. [47], in practical situations, variable thresholds can often be modeled as affine functions, which corresponds to the general form given at the beginning of this subsection. In this context, any t-cover or t-approximation of a subset $R \subseteq Y$ can be indifferently proposed as a representation of R.

3 Properties of covers and approximations

In this section properties of covers and approximations are studied with respect to general cones with multiple solution sets and multiple tolerance functions. Results for the special case of polyhedral cones are also included.

3.1 Properties of covers

We consider covers of multiple sets in Y to be represented with respect to multiple cones and multiple tolerance functions. Multiple cones may model changing or different preferences of the decision makers engaged in the decision making process. Multiple tolerance functions may result from multiple sets and/or multiple cones, or simply from more or less effective algorithms.

We first give a result involving two sets, two cones, and one tolerance function, which shows the conditions under which a cover remains valid.

Proposition 5

Let Y be a set in ${\mathcal {R}}^p$, and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let $C_1, C_2$ be cones in ${\mathcal {R}}^p$ such that $C_1\subseteq C_2$. Let $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. If $S \in \mathcal{{C}}_{t}(R_1,C_1$) then $S \in \mathcal{{C}}_{t}(R_2,C_2$).

Proof

Let $S \in \mathcal{{C}}_{t}(R_1,C_1$). Then, by Definition 7, for all $y\in R_1$ there exists $s\in S$ such that $s \leqq _{C_1}^{t} y$. Since $R_2\subseteq R_1$, this is also true for all $y \in R_2$. Moreover, since $C_1\subseteq C_2, s \leqq _{C_1}^{t} y$ implies $s \leqq _{C_2}^{t} y$, which proves $S \in \mathcal{{C}}_{t}(R_2,C_2$). $\square$

Proposition 5 shows that a cover of a set R with respect to a cone C remains a cover of any subset of R with respect to any cone containing C. Special cases of Proposition 5 can be derived directly when considering one set or one cone. In the following we just state the most general results without mentioning all subcases (with only one set, or one cone, or one tolerance function).

Another direct consequence of Proposition 5 follows.

Corollary 1

Let Y be a set in ${\mathcal {R}}^p$ and $R_1, R_2$ be subsets of Y. Let $C_1, C_2$ be cones in ${\mathcal {R}}^p$ and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. If $S \in \mathcal{{C}}_{t}(R_1 \cup R_2,C_1 \cap C_2$) then $S \in \mathcal{{C}}_{t}(R_i,C_j$) for $i=1,2$ and $j=1,2$.

Extending Proposition 5 to the case of two tolerance functions requires an additional convexity assumption.

Proposition 6

Let Y be a set in ${\mathcal {R}}^p$, and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let $C_1, C_2$ be cones in ${\mathcal {R}}^p$ such that $C_1\subseteq C_2$ and $C_2$ is convex. Let $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C_2} t_2(y)$ for all $y \in {\mathcal {R}}^p$. If $S \in \mathcal{{C}}_{t_1}(R_1,C_1$) then $S \in \mathcal{{C}}_{t_2}(R_2,C_2$).

Proof

From Proposition 5, if $S \in \mathcal{{C}}_{t_1}(R_1,C_1$) then $S \in \mathcal{{C}}_{t_1}(R_2,C_2$), that is, for every $y \in R_2$ there exists $s \in S$ such that $s \leqq _{C_2}^{t_1} y$. Since $\leqq _{C_2}$ is transitive because $C_2$ is a convex cone, $t_1(y)\leqq _{C_2} t_2(y)$ implies $s \leqq _{C_2}^{t_2} y$, which proves $S \in \mathcal{{C}}_{t_2}(R_2,C_2$). $\square$

Basically the previous result shows that a cover for a given tolerance function also remains a cover when the tolerance function is relaxed. A particular interesting case of Proposition 6 is when tolerance functions are composed.

Corollary 2

Let Y be a set in ${\mathcal {R}}^p$, and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let $C_1, C_2$ be cones in ${\mathcal {R}}^p$ such that $C_1\subseteq C_2$, and $C_2$ is convex. Let $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions. If $S \in \mathcal{{C}}_{t_1}(R_1,C_1$) then $S \in \mathcal{{C}}_{t_2(t_1)}(R_2,C_2)$.

Proof

Since $t_2$ is a tolerance function, by Definition 4(1), we get $t_1(y)\leqq _{C_2} t_2(t_1(y)).$ $\square$

Another direct consequence of Proposition 6 follows.

Corollary 3

Let Y be a set in ${\mathcal {R}}^p$, and $R_1, R_2$ be subsets of Y. Let $C_1, C_2$ be convex cones in ${\mathcal {R}}^p$, and $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C_j} t_2(y)$ for $j=1,2$, for all $y \in {\mathcal {R}}^p$. If $S \in \mathcal{{C}}_{t_1}(R_1 \cup R_2,C_1 \cap C_2$) then $S \in \mathcal{{C}}_{t_k}(R_i,C_j)$ for $i=1,2, j=1,2$, and $k=1,2$.

We show now that nondominated sets play an important role as covers.

Proposition 7

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, C be a convex cone in ${\mathcal {R}}^p$, and $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function. If $S \in \mathcal{{C}}_{t}(R,C$) then $N(S,C) \in \mathcal{{C}}_{t}(R,C$).

Proof

We have $N(S,C) \subseteq S$. If $S = N(S,C)$ then the proof is complete. If $S \supset N(S,C)$, let $s \in S \setminus N(S,C)$. Then there exists $s' \in N(S,C)$ such that $s' \leqq _C s$. Consider all $y \in R$ such that $s \leqq _{C}^{t} y$. Since C is convex, $\leqq _{C}$ is transitive and we get $s' \leqq _{C}^{t} y$. Therefore, $S \setminus \{s\}$ is still a cover of R. Removing this way all elements from $S \setminus N(S,C)$, we obtain N(S, C) as a cover of R. $\square$

Using the previous results, this result is now extended to the case of multiple sets, multiple tolerance functions, and multiple cones. The following corollary shows the impact of filtering out dominated elements in this extended context. While Corollary 4(i) shows how to obtain a reduced cover with respect to a larger cone, Corollary 4(ii) addresses obtaining a reduced cover with respect to the same cone. Note that the reduction can be performed with respect to either cone.

Corollary 4

Let Y be a set in ${\mathcal {R}}^p$, and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let $C_1, C_2$ be cones in ${\mathcal {R}}^p$ such that $C_1\subseteq C_2$ and $C_2$ is convex. Let $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C_2} t_2(y)$ for all $y \in {\mathcal {R}}^p$.

• (i) If $S \in \mathcal{{C}}_{t_1}(R_1,C_1$) then $N(S,C_i) \in \mathcal{{C}}_{t_2}(R_2,C_2$) for $i = 1,2.$

• (ii) If $S \in \mathcal{{C}}_{t_1}(R_1,C_2$) then $N(S,C_i) \in \mathcal{{C}}_{t_2}(R_2,C_2$) for $i = 1,2.$

Proof

• (i) By Proposition 7 we have $N(S,C_1) \in \mathcal{{C}}_{t_1}(R_1,C_1$), and using Proposition 6 we obtain the result for $i=1$. By Proposition 6, $S \in \mathcal{{C}}_{t_1}(R_1,C_1$) implies $S \in \mathcal{{C}}_{t_2}(R_2,C_2$). Then the result for $i = 2$ is obtained from Proposition 7.

• (ii) By Proposition 6 we get $S \in \mathcal{{C}}_{t_2}(R_2,C_2$), which, due to Proposition 7, yields the result for $i = 2$. Since $C_1 \subseteq C_2$ implies $N(S, C_2) \subseteq N(S, C_1)$ [50], and considering that any superset of a cover is also a cover, we obtain the result for $i = 1$.

$\square$

3.2 Properties of covers for polyhedral cones

Since the relationship between the nondominated set with respect to a general polyhedral cone and the Pareto cone is well established [50], we examine covers with respect to polyhedral cones and sets. Polyhedral cones containing the Pareto cone model relative importance of criteria [29, 43] and also reduce the nondominated set [30], which facilitates the resulting decision making process [29].

The following two propositions show the behavior of covers in the presence of linear transformation represented by the matrix of the cone.

Proposition 8

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, and C be a polyhedral cone in ${\mathcal {R}}^p, C=\{d \in {\mathcal {R}}^p: \ Ad \geqq 0\}$ where A is a $p \times p$ matrix. Let $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be an ${A}\hbox {-}$invariant tolerance function. Then ${S} \in \mathcal{{C}}_{t}(R,C$) if and only if $A[S] \in \mathcal{{C}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$).

Proof

$(\Rightarrow )$ Let $S \in \mathcal{{C}}_{t}(R,C$). Then by Definition 7, for all $y \in R$ there exists $s \in S$ such that $s \leqq _{C}{t(y)}$. By Definition 1, there exists $d \in C$ such that $d=t(y)-s.$ Since $d\in C$, we have $Ad=A(t(y)-s) \geqq 0$, or equivalently $As \leqq _{{\mathcal {R}}^p_{\geqq }}At(y)$. Since t is an ${A}\hbox {-}$invariant function, we obtain $As \leqq _{{\mathcal {R}}^p_{\geqq }}t(Ay)$. Thus, for all $Ay \in A[R]$ there exists $As\in A[S]$ such that $As \leqq _{{\mathcal {R}}^p_{\geqq }}^t Ay$. Therefore, $A[S] \in \mathcal{{C}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$).

$(\Leftarrow )$ Let $A[S] \in \mathcal{{C}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$). Then by Definition 7, for all $u \in A[R]$, with $u=Ay$ for some $y\in R$, there exists $\bar{u} \in A[S]$, with $\bar{u}=As$ for some $s \in S$, such that $As \leqq _{{\mathcal {R}}^p_{\geqq }}t(Ay)$. Since t is an ${A}\hbox {-}$invariant function, we obtain $A(t(y)-s)\geqq 0$, and thus $t(y)-s \in C$. Therefore, for all $y\in R$ there exists $s\in S$ such that $s\leqq _C^t y$, which completes the proof. $\square$

Proposition 9

Let Y be a set in ${\mathcal {R}}^p$ and R be a subset of Y. Let $C, C_1, C_2$ be cones in ${\mathcal {R}}^p$ such that C is a polyhedral cone, $C=\{d \in {\mathcal {R}}^p: \ Ad \geqq 0\}$ where A is a $p \times p$ matrix and ${\mathcal {R}}^p_{\geqq } \subseteq C$, and $C_1 \subseteq C_2$ and $C_2$ is convex. Let $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C} t_2(y)$ for all $y \in {\mathcal {R}}^p$. If ${S} \in \mathcal{{C}}_{t_1}(N(A[R], {\mathcal {R}}^p_{\geqq }), C_1$) then $S \in \mathcal{{C}}_{t_2}(A[N(R, C)], C_2$).

Proof

Since C is a polyhedral cone, $N(A[R], {\mathcal {R}}^p_{\geqq }) \supseteq A[N(R, C)]$ [58], and the result follows from Proposition 6. $\square$

Propositions 8 and 9 can be extended to two other propositions by replacing the polyhedral cone C with a polyhedral set $C, C=C(A,b)=\{d \in {\mathcal {R}}^p: \ Ad \geqq b\},$ where A is a $p \times p$ matrix and $b\in {\mathcal {R}}^p$, and the Pareto cone ${\mathcal {R}}^p_{\geqq }$ with the translated Pareto cone ${\mathcal {R}}^p_{\geqq b}:={\mathcal {R}}^p_{\geqq }+b=\{d\in {\mathcal {R}}^p: d\geqq b\}$. Such translated cones model approximate nondominated solutions that are of practical relevance [13]. The new proofs making use of the replacement exactly follow the two proofs above.

3.3 Properties of approximations

We established conditions under which a cover remains a cover when changing the set to be represented, the cone and/or the tolerance function (see Propositions 5, 6, and their corollaries). This can be extended to approximations with a notable exception regarding change of cones.

Proposition 10

Let Y be a set in ${\mathcal {R}}^p$ and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let C be a convex cone in ${\mathcal {R}}^p$, and $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C} t_2(y)$ for all $y \in {\mathcal {R}}^p$. If $S \in \mathcal{{A}}_{t_1}(R_1,C$) then $S \in \mathcal{{A}}_{t_2}(R_2,C$).

Proof

If $S \in \mathcal{{A}}_{t_1}(R_1,C$) we have $N(S,C) = S$ and, from Proposition 6 for $C=C_1=C_2$ we obtain $S \in \mathcal{{C}}_{t_2}(R_2,C$), which implies $S \in \mathcal{{A}}_{t_2}(R_2,C$). $\square$

The next result shows how an approximation can be obtained from a cover.

Proposition 11

Let Y be a set in ${\mathcal {R}}^p$ and $R_1, R_2$ be subsets of Y such that $R_2\subseteq R_1$. Let C be a convex cone in ${\mathcal {R}}^p$, and $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C} t_2(y)$ for all $y \in {\mathcal {R}}^p$. If $S \in \mathcal{{C}}_{t_1}(R_1,C$) then $N(S,C) \in \mathcal{{A}}_{t_2}(R_2,C$).

Proof

Using Corollary 4 (i) or (ii) for $C_1=C_2=C$. $\square$

Observe that the results in both propositions above are obtained for the same cone and do not hold when changing cones. Indeed, a result of the type ‘$S \in \mathcal{{A}}_{t}(R_1,C_1$) implies $S \in \mathcal{{A}}_{t}(R_2,C_2$)’ would require $C_1 \subseteq C_2$ to ensure that S remains a cover of R for $C_2$ (see Proposition 5). But $C_1 \subseteq C_2$ implies $N(S,C_2) \subseteq N(S,C_1)$. Since $S \in \mathcal{{A}}_{t}(R,C_1$), we have $S = N(S,C_1)$ and thus $S \supseteq N(S,C_2)$, whereas equality is required to establish $S \in \mathcal{{A}}_{t}(R,C_2$). However, the two propositions reveal the influence of changing sets and/or tolerance functions on approximations. Given a cover or an approximation, one can always use it to approximate a subset, and if desired, with relaxed tolerance.

The approximation is considered perfect when it does not allow any tolerance, which is modeled with the identity function. In this case, the set of all approximations reduces to the nondominated set provided that the set R to be approximated lies between N(Y, C) and Y.

Proposition 12

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset such that $N(Y,C) \subseteq R \subseteq Y$, and C be a cone in ${\mathcal {R}}^p$. Let $id: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be a tolerance function such that $id(y)=y$ for all $y \in {\mathcal {R}}^p$. Then $\mathcal{{A}}_{id}(R,C) = \{N(Y,C)\}$.

Proof

Let $S\in \mathcal{{A}}_{id}(R,C)$.

We show that $S \supseteq N(Y,C)$. Assume, by contradiction, that there exists $y \in N(Y,C) \setminus S$. Then, since $R \supseteq N(Y,C)$, we have $y \in R$. Moreover, since $y \in N(Y,C)$, there is no $s \in S$ such that $s \le _C y$, and even such that $s \leqq _{C} y$ since $y \not \in S$. In that case, S would not be a cover of R, which contradicts $S \in \mathcal{{A}}_{id}(R,C)$.

We show now that $S \subseteq N(Y,C)$. Assume, by contradiction, that there exists $y \in S \setminus N(Y,C)$. Then, there exists $y' \in N(Y,C)$ such that $y' \le _C y$. We just proved that $S \supseteq N(Y,C)$, which implies that $y' \in S$. In that case S would contain a dominated element y, which contradicts $S \in \mathcal{{A}}_{id}(R,C)$. $\square$

3.4 Properties of approximations for polyhedral cones

Analogous to covers, specific results are available for approximations in the presence of the linear transformation represented by the matrix of a polyhedral cone.

Proposition 13

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, and C be a pointed polyhedral cone in ${\mathcal {R}}^p, C=\{d \in {\mathcal {R}}^p: \ Ad \geqq 0\}$ where A is a $p \times p$ matrix. Let $t: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be an ${A}\hbox {-}$invariant tolerance function. Then ${S} \in \mathcal{{A}}_{t}(R,C$) if and only if $A[S] \in \mathcal{{A}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$).

Proof

$(\Rightarrow )$ Let $S \in \mathcal{{A}}_{t}(R,C$). Then by Definition 8, $S \in \mathcal{{C}}_{t}(R,C$) and $S = N(S, C)$. The latter implies $A[S] = A[N(S, C)]$. Since C is a pointed polyhedral cone, $N(A[S], {\mathcal {R}}^p_{\geqq }) = A[N(S, C)]$ [58], which gives $A[S] = N(A[S], {\mathcal {R}}^p_{\geqq })$. Since $S \in \mathcal{{C}}_{t}(R,C$), by Proposition 8 we have $A[S] \in \mathcal{{C}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$), which proves the result.

$(\Leftarrow )$ Let $A[S] \in \mathcal{{A}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$). Then by Definition 8 we have $A[S] \in \mathcal{{C}}_{t}(A[R],{\mathcal {R}}^p_{\geqq }$) and $A[S] = N(A[S], {\mathcal {R}}^p_{\geqq })]$. Due to Proposition 8 the former implies $S \in \mathcal{{C}}_{t}(R, C$). Since $N(A[S], {\mathcal {R}}^p_{\geqq }) = A[N(S, C)]$, the latter implies $A[N(S, C)] = A[S]$, and thus $N(S, C) = S$ owing to the pointedness of C, which proves the result. $\square$

Corollary 5

Let Y be a set in ${\mathcal {R}}^p, R$ be a subset of Y, and $C, C_1$ be cones in ${\mathcal {R}}^p$ such that C is a polyhedral cone, $C=\{d \in {\mathcal {R}}^p: \ Ad \geqq 0\}$ where A is a $p \times p$ matrix. Let $t_1: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ and $t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y)\leqq _{C_1} t_2(y)$ for all $y \in {\mathcal {R}}^p$. If ${S} \in \mathcal{{A}}_{t_1}(N(A[R], {\mathcal {R}}^p_{\geqq }), C_1$) then $S \in \mathcal{{A}}_{t_2}(A[N(R, C)], C_1$).

Proof

By Proposition 10 and recognizing the inclusion $N(A[R], {\mathcal {R}}^p_{\geqq }) \supseteq A[N(R, C)]$ because C is a polyhedral cone. $\square$

Notice, that in contrast to Proposition 9, Corollary 5 does not allow the change of cones in agreement with the observation that properties of approximations do not hold in that case. Proposition 13 and Corollary 5 can easily be extended to the polyhedral sets in a similar manner that is mentioned in Sect. 3.2 for Propositions 8 and 9 addressing the behavior of covers.

Having presented the properties of covers and approximations, in the next section we turn our attention to applied aspects of these results.

4 Decomposable systems

Certain real-life applications require the formulation of MOPs as a collection of coupled multiobjective subproblems. For example, in engineering design MOPs typically model the design process that requires specialization of design teams along distinct disciplines or decomposition of the object being designed into subsystems and components (e.g., Peri and Campana [46], Jilla and Miller [31]). In business applications, an overall MOP being a collection of multiobjective subproblems may model the management of business activities within a large international corporation, where decisions under multiple objectives are made locally in each country (e.g., Gomez et al. [19]). In military applications, a collection of coupled MOPs may model multi-team, multi-mission military planning and execution under partial information due to constraints in the communication bandwidth or due to required communication latencies [44]. Combinations of coupled MOPs rather than a single MOP are encountered when multiobjective modeling and optimization are applied to complex decision making problems [16]. Due to the complexity reflected in different feasible spaces, different software requirements, different decision makers, it is not possible to find the Pareto set for the overall MOP but it is desirable to decompose the overall problem into multiobjective subproblems, which are more easily optimized, and then construct the nondominated set of the original problem.

However, as explained in Sect. 1, even for a decomposed problem, it is often hard to obtain exact solutions to the subproblems and so the solution sets have to be represented separately before the overall representation can be constructed. The goal is then to represent the nondominated set of the overall system by representing the nondominated sets of the subproblems.

In this section we first extend the properties of covers and approximations to address the representation of the nondominated set of complex but decomposable MOPs, and then relate these properties to specially structured MOPs.

4.1 Covers and approximations for combined subsets

We present properties of covers and approximations for sets composed of subsets that are combined using the set operations such as the Cartesian product, algebraic sum, and union. Each result involves two sets, two cones, and two tolerance functions and can be generalized to a larger number of these items.

Proposition 14

Let $Y_i$ be a set in ${\mathcal {R}}^{p_i}, R_i$ be a subset of $Y_i, C_i$ be a cone in ${\mathcal {R}}^{p_i}$, and $t_i: {\mathcal {R}}^{p_i}\mapsto {\mathcal {R}}^{p_i}$ be a tolerance function for $i=1, 2$. Let $t: {\mathcal {R}}^{p}\mapsto {\mathcal {R}}^{p}$ be defined as $t(y_1, y_2) = (t_1(y_1),t_2(y_2))$ for $y_1\in {\mathcal {R}}^{p_1}$ and $y_2\in {\mathcal {R}}^{p_2}$, and $p=p_1+p_2$. Then

• (i) $S_1\in \mathcal{{C}}_{t_1}(R_1,C_1$) and $S_2\in \mathcal{{C}}_{t_2}(R_2,C_2$) if and only if $S_1 \times S_2\in \mathcal{{C}}_{t}(R_1\times R_2,C_1\times C_2$),

• (ii) $N(S_1,C_1)\in \mathcal {A}_{t_1}(R_1,C_1)$ and $N(S_2,C_2) \in \mathcal {A}_{t_2}(R_2,C_2)$ if and only if $N(S_1\times S_2, C_1\times C_2)\in \mathcal{{A}}_{t}(R_1\times R_2,C_1\times C_2$).

Proof

• (i) Let $S_i\in \mathcal{{C}}_{t_1}(R_i,C_i$) for $i = 1, 2.$ Then, by Definition 7, for all $y_i \in R_i$ there exists $s_i \in S_i$ such that $s_i \leqq _{C_i}^{t_i} y_i$, for $i = 1, 2$. These relations hold if and only if for all $(y_1,y_2) \in R_1 \times R_2$ there exists $(s_1,s_2) \in S_1\times S_2$ such that $t_1(y_1)-s_1 \in {C_1}$ and $t_2(y_2)-s_2 \in {C_2}$ or, equivalently, $(t_1(y_1) ,t_2(y_2))-(s_1,s_2 )\in C_1\times C_2$. That is, for all $(y_1,y_1)\in R_1\times R_2$, there exists $(s_1,s_2) \in S_1 \times S_2$ such that $(s_1,s_2)\leqq _{C_1\times C_2}^t (y_1,y_2)$ with $t=(t_1(y_1), t_2(y_2))$.

• (ii) Generalizing Proposition 3.9 of Gardenghi et al. [16] to the following set equality, $N(S_1\times S_2, C_1\times C_2) = N(S_1, C_1) \times N(S_2, C_2)$, the desired result is obtained.

$\square$

The next proposition requires that the emerging tolerance function be additively separable.

Proposition 15

Let $Y_i$ be a set in ${\mathcal {R}}^{p}, R_i$ be a subset of $Y_i, C_i$ be a cone in ${\mathcal {R}}^{p}$, and $t_i: {\mathcal {R}}^{p}\mapsto {\mathcal {R}}^{p}$ be a tolerance function for $i=1, 2$. Let $t: {\mathcal {R}}^{p}\mapsto {\mathcal {R}}^{p}$ be defined as $t(y_1+y_2)=t_1(y_1)+t_2(y_2)$ for $y_1\in R_1$ and $y_2\in R_2$.

• (i) If $S_1\in \mathcal{{C}}_{t_1}(R_1, C_1$) and $S_2\in \mathcal{{C}}_{t_2}(R_2, C_2$) then $S_1+ S_2 \in \mathcal{{C}}_{t}(R_1+R_2,C_1+C_2$).

• (ii) Let $C_i$ be a convex cone for $i = 1, 2$. If $S_1\in \mathcal {C}_{t_1}(R_1,C_1)$ and $S_2\in \mathcal {C}_{t_2}(R_2,C_2)$ then $N(N(S_1,C_1)+ N(S_2,C_2),C_1+C_2) \in \mathcal{{A}}_{t}(R_1+ R_2, C_1+C_2$).

Proof

• (i) Let $S_i\in \mathcal{{C}}_{t_1}(R_i,C_i$) for $i = 1, 2.$ Then, by Definition 7, for all $y_i \in R_i$ there exists $s_i \in S_i$ such that $s_i \leqq _{C_i}^{t_i} y_i$, for $i = 1, 2$. This implies that for $y_1+y_2\in R_1+R_2$ there exists $s_1+s_2\in S_1+S_2$ such that $t_1(y_1)-s_1\in C_1$ and $t_2(y_2)-s_2\in C_2$. Thus we have $t_1(y_1)-s_1+t_2(y_2)-s_2\in C_1+C_2$. That is, $s_1+s_2 \leqq _{C_1+C_2}^t y_1+y_2$, where $t(y_1 + y_2) = t_1(y_1) + t_2(y_2)$.

• (ii) Since $C_1, C_2$ are convex cones, $C_1+C_2$ is a convex cone. By Proposition 7, $N(S_i,C_i) \in \mathcal {C}_{t_i}(R_i,C_i)$ for $i = 1, 2$. By part (i), we have $N(S_1,C_1)+ N(S_2,C_2)\in \mathcal{{C}}_{t}(R_1+ R_2, C_1+C_2$), where $t(y_1+y_2)=t_1(y_1)+t_2(y_2)$ for $y_1\in R_1$ and $y_2\in R_2$. Thus, by Proposition 11, we obtain the desired result.

$\square$

The final proposition of this section deals with the union operator.

Proposition 16

Let $Y_i$ be a set in ${\mathcal {R}}^{p}, R_i$ be a subset of $Y_i, C_i$ be a cone in ${\mathcal {R}}^p$ for $i=1, 2$ such that $C_1$ is convex. Let $t_1, t_2: {\mathcal {R}}^p\mapsto {\mathcal {R}}^p$ be tolerance functions such that $t_1(y_1)\leqq _{C_1} t_2(y_1)$ for all $y_1\in {\mathcal {R}}^{p}$.

• (i) If $S_1\in \mathcal{{C}}_{t_1}(R_1,C_1$) and $S_2\in \mathcal{{C}}_{t_2}(R_2,C_2$) then $S_1\cup S_2 \in \mathcal{{C}}_{t_2}(R_1\cup R_2,C_1\cup C_2$).

• (ii) Let $C_1 \cup C_2$ be a convex cone. If $S_1 \in \mathcal{{C}}_{t_1}(R_1,C_1$) and $S_2 \in \mathcal{{C}}_{t_2}(R_2,C_2$) then $N(S_1\cup S_2, C_1 \cup C_2) \in \mathcal{{A}}_{t_2}(R_1\cup R_2,C_1\cup C_2$).

• (iii) If $S_1 \in \mathcal{{C}}_{t_1}(R_1,C_1$) and $S_2 \in \mathcal{{C}}_{t_2}(R_2,C_1$) then $N(S_1\cup S_2, C_1)\in \mathcal{{A}}_{t_2}(R_1\cup R_2, C_1$).

Proof

• (i) Let $S_1\in \mathcal{{C}}_{t_1}(R_1,C_1$) and $S_2 \in \mathcal{{C}}_{t_2}(R_2,C_2$). Then by Definition 7, for all $y_1 \in R_1$ there exists $s_1 \in S_1$ such that $s_1 \leqq _{C_1} t_1(y_1)$. Since $t_1(y_1)\leqq _{C_1} t_2(y_1)$ and $\leqq _{C_1}$ is transitive due to $C_1$ being convex, we obtain $s_1 \leqq _{C_1}^{t_2} y_1$. Moreover, for all $y_2 \in R_2$ there exists $s_2 \in S_2$ such that $s_2 \leqq _{C_2}^{t_2} y_2$. Therefore, for all $y \in R_1 \cup R_2$ there exists $s \in S_1 \cup S_2$ such that $s \leqq _{C_1}^{t_2} y$ or $s \leqq _{C_2}^{t_2} y$, which is equivalent to $t_2(y) - s \in C_1 \cup C_2$, and thus to $s \leqq _{C_1 \cup C_2}^{t_2} y$.

• (ii) By part (i), we have $S_1\cup S_2 \in \mathcal{{C}}_{t_2}(R_1\cup R_2,C_1\cup C_2$). Since $C_1\cup C_2$ is convex, by Proposition 11, we have the desired result.

• (iii) Directly follows from part (ii).

$\square$

In the next section we discuss the applicability of these results in the context of specific decomposable MOPs and the Pareto optimality.

4.2 Applications

Consider the overall MOP, that is referred to as the all-in-one (AiO) problem, and assume that it is decomposable into two multiobjective subproblems. Let the Pareto set of this AiO MOP be denoted as $N(Y, {\mathcal {R}}^{p}_\geqq )$, where the set $Y \subseteq {\mathcal {R}}^p, Y=f(X),$ is the image of the set of feasible decisions $X \subseteq {\mathcal {R}}^n$ with the vector-valued objective function $f: {\mathcal {R}}^n \rightarrow {\mathcal {R}}^p$, and $C = {\mathcal {R}}^{p}_\geqq$ is the Pareto cone.

Assume that $N(Y, {\mathcal {R}}^{p}_\geqq )$ is chosen as a subset R of Y to be represented. Assume also that $N(Y, {\mathcal {R}}^{p}_\geqq )$ is computationally intractable while representations of the Pareto sets of the subproblems are computationally achievable. The goal is to construct a representation of $N(Y, {\mathcal {R}}^{p}_\geqq )$ using the available representations.

Depending upon the properties of the feasible set X and the function f, three types of decomposition of the AiO problem into subproblems are presented which lead to three different scenarios of exact calculations of $N(Y, {\mathcal {R}}^{p}_\geqq )$. Each scenario is matched with a proposition in Sect. 4.1, which allows the construction of a desired cover or approximation of the AiO Pareto set $N(Y, {\mathcal {R}}^{p}_\geqq ),$ and is related to real-life applications from the literature.

• 1. Let the feasible set X be partitioned into two subsets, $X = X_1 \times X_2$, $X_i \subseteq {\mathcal {R}}^{n_i}, i = 1, 2$, and $n_1 + n_2 = n$. In other words, the AiO problem is decomposed into two MOPs, each with a distinct feasible set. Additionally, properties of the two vector-valued objective functions imply two types of decomposition that are given below. These models are used by a big class of engineering design problems modeled as multiobjective multidisciplinary optimization problems for which decomposition is indispensable for the computation of the AiO Pareto set (e.g., Huang et al. [28], Zhang et al. [60], Kang et al. [32]).

• (a) Assume that the function $f(x) = (f_1(x_1), f_2(x_2))$ is composed of functions $f_i: {\mathcal {R}}^{n_i} \rightarrow {\mathcal {R}}^{p_i}, i = 1, 2,$ where $p_1 + p_2 = p$. Then $Y = Y_1 \times Y_2$, where $Y_i = f_i(X_i), i = 1, 2$. Applying Proposition 3.9 of Gardenghi et al. [16], we obtain

  $$\begin{aligned} N(Y, {\mathcal {R}}^{p}_\geqq ) = N(Y_1\times Y_2, {\mathcal {R}}^{p_1}_\geqq \times {\mathcal {R}}^{p_2}_\geqq ) =N(Y_1,{\mathcal {R}}^{p_1}_\geqq )\times N(Y_2,{\mathcal {R}}^{p_2}_\geqq ). \end{aligned}$$

  Given a cover or approximation for $N(Y_i, {\mathcal {R}}^{p_i}_\geqq ), i = 1, 2,$ using Proposition 14, a cover or approximation of $N(Y_1\times Y_2, {\mathcal {R}}^{p_1}_\geqq \times {\mathcal {R}}^{p_2}_\geqq )$ for the AiO problem can be constructed.

Example 4

This model is used in Danduarand et al. [7] where an automotive design problem is presented as two coupled multiobjective subproblems. The layout of components in the underhood of the vehicle is optimized at the system level, while optimizing the design of one of these components, a battery, at the component level. The battery must not only be designed under demanding thermal criteria, but must itself be optimally placed within the underhood of the vehicle. Since the subproblems correspond to two distinct but coupled design processes that are carried out by distinct teams, they require different solution approaches to computing the Pareto set on each level and then construct the AiO Pareto set.

• (b) Under the assumption that the function f is additively separable, $(f(x) = f_1(x_1) + f_2(x_2)$, where $f_i: {\mathcal {R}}^{n_i} \rightarrow {\mathcal {R}}^p, i = 1, 2$), we have $Y=Y_1+Y_2$, where $Y_i = f_i(X_i), i = 1, 2$. Applying Proposition 3.3 of Gardenghi et al. [16], we obtain

  $$\begin{aligned} N(Y, {\mathcal {R}}^{p}_\geqq ) = N(Y_1+Y_2,{\mathcal {R}}^{p}_{\geqq } ) =N( N(Y_1 ,{\mathcal {R}}^{p}_{\geqq })+ N(Y_2,{\mathcal {R}}^{p}_{\geqq }), {\mathcal {R}}^{p}_{\geqq }). \end{aligned}$$

  Given a cover or approximation of $N(Y_i, {\mathcal {R}}_\geqq ^p), i = 1, 2,$ applying Proposition 15, a cover or approximation of $N(Y_1+Y_2,{\mathcal {R}}^{p}_{\geqq })$ for the AiO problem can be constructed. Note that additive separability is a property commonly found in engineering applications [21].

Example 5

For a specific example refer to Guarneri and Wiecek [20] where an automotive design problem involves the design of the suspension in order to optimize the comfort and the road-holding of the vehicle. These objectives depend upon the design of two components, the spring and the damper, that provide adequate levels of stiffness and damping for filtering the road unevenness. The overall problem consists of three coupled subproblems modeling the design of the suspension, spring, and damper. Again, the subproblems correspond to three different but coupled design processes that are carried out by different teams and require very different solution approaches.

• 2. Let the feasible set X be partitioned into two subsets, $X = X_1 \cup X_2, X_i \subseteq {\mathcal {R}}^{n_i}, i = 1, 2,$ and the function f be defined as $f: {\mathcal {R}}^{n_1 + n_2} \rightarrow {\mathcal {R}}^p.$ Then $Y=Y_1 \cup Y_2$, where $Y_i = f_i(X_i), i = 1, 2$. Extending Proposition 3.1 of Gardenghi et al. [16], we obtain the following result

  $$\begin{aligned} N(Y, {\mathcal {R}}^{p}_\geqq ) = N\big (Y_1\cup Y_2, {\mathcal {R}}^p_{\geqq } \big )=N\big (N(Y_1,{\mathcal {R}}^p_{\geqq })\cup N(Y_2,{\mathcal {R}}^p_{\geqq }), {\mathcal {R}}^p_{\geqq } \big ). \end{aligned}$$

  Given a cover or approximation for $N((Y_i,{\mathcal {R}}^p_{\geqq }), {\mathcal {R}}^p_{\geqq }), i = 1, 2$ and applying Proposition 16, a cover or approximation of $N\big (Y_1\cup Y_2, {\mathcal {R}}^p_{\geqq } \big )$ for the AiO problem can be constructed.

Example 6

This case is applicable to mixed-integer MOPs which find applications in facility location [41], radiation therapy planning [11], scheduling [42], and many others. Their feasible region can be decomposed into the union of subsets by fixing the integer variables to their feasible values. Let the feasible region $U = U_1 \times U_2$, where $U_1 \subseteq {\mathcal {R}}^{q}$ and $U_2 \subseteq \mathcal {Z}^{n - q}$ be the feasible sets for q continuous and $n-q$ integer decision variables in the mixed-integer MOP with the objective function of the form $f: {\mathcal {R}}^{n} \rightarrow {\mathcal {R}}^p,$ where $f(u) = f(u_1, u_2)$ for $u_1 \in U_1$ and $u_2 \in U_2.$ Since $U_2$ is a discrete set, U can be decomposed as $U= \bigcup _{{\bar{u}}_2 \in U_2}U({\bar{u}}_2),$ where $U({\bar{u}}_2) = \{u \in U: u = (u_1, u_2), u_2 = {\bar{u}}_2\}$. The image set $V = f(U)$ can then be decomposed as $V = \bigcup _{{\bar{u}}_2 \in U_2} V({\bar{u}}_2),$ where $V({\bar{u}}_2) = \{v \in V: v = f(u), u \in U({\bar{u}}_2)\}$. We obtain

$$\begin{aligned} N(V, {\mathcal {R}}^{p}_\geqq ) = N\big (\bigcup _{{\bar{u}}_2 \in U_2} V({\bar{u}}_2), {\mathcal {R}}^p_{\geqq } \big ) = N\big ( \bigcup _{{\bar{u}}_2 \in U_2} \big ( N(V({\bar{u}}_2), {\mathcal {R}}^p_{\geqq }), {\mathcal {R}}^p_{\geqq } \big ). \end{aligned}$$

The results presented above can obviously be generalized for more than two subproblems and for general convex cones C in place of the Pareto cone ${\mathcal {R}}^p_{\geqq }$.

5 Conclusions

In this paper we have proposed a unified approach to representing solution sets in multiobjective optimization. We have defined covers and approximations, and collected and proved their properties. The approach makes use of a tolerance function and cones. The former quantifies the representation quality while the latter model decision maker’s preferences.

Covers and approximations maintain their properties for subsets of the sets being represented with the same or higher tolerance. Covers allow one to enlarge cones; a cover representing a solution set with respect to a cone can be easily modified to become a cover of a subset with respect to an enlarged cone. Approximations do not have this flexibility and are permanently associated with a cone. We have shown the applicability of the results to the representation of the Pareto sets of complex but decomposable MOPs.

This paper motivates further research in two directions. Additional properties of covers and approximations can be studied in the context of specific MOPs they refer to. Algorithms for computing covers or approximations for complex and decomposable multiobjective decision making problems may be designed.