Generating All Nondominated Solutions for Multiobjective Discrete Optimization Problems

Optimization algorithms are typically developed with the purpose of optimizing a single objective. However, in many real-world applications two or more criteria are relevant. Any discrete optimization problem in which two or more objectives are considered is called multiobjective discrete optimization problem (MODO). In MODO, the main issue is to develop effective procedures to generate efficient solutions that have the property that no improvement in any objective is possible without sacrificing in at least one other objective. Many studies have been presented for MODO, including several specialized algorithms targeting specific problems. However, the majority of them solve bicriteria discrete problems, while only a few of them deal with more than two objective functions.

In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions [3]. In this algorithm, the search is managed over \((p-1)\)-dimensional rectangles where \( p \) represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known \( \varepsilon \)-constraint scalarization [1] and its contribution lies in the way rectangles are defined and tracked.

The notation for the algorithm is given below.

- The number of objective functions is denoted as \( p \).
- Each objective in MODO is denoted as \( f_j(x) \) where \( j \in \{1,\ldots,p\} \).
- \( \mathcal{Y}_N \) denotes the set of nondominated solutions.
- Ideal point denoted as \( y^I \in \mathbb{R}^p \) where \( y^I_j = \displaystyle \min_{x \in \mathcal{X}} f_j(x) \) for all \( j \in \{1,\ldots,p \}\).
- Components of \( y^U \in \mathbb{R}^p \) are upper bounds of each objective function, i.e. \( y^U_j = \displaystyle \max_{x \in \mathcal{X}} f_j(x) \) for all \( j \in \{1,\ldots,p \}\).
- A rectangle's lower and upper vertices are denoted as \( l \in \mathbb{R}^{p-1} \) and \( u \in \mathbb{R}^{p-1} \), respectively. With these bounds, a rectangle is defined as \( R(l,u)= \{\bar{y} \in \mathbb{R}^{p-1}, l \le \bar{y} \le u\} \) [2] .
- The \( i \)-th rectangle is denoted as \( R_i \) with its lower and upper vertices \( l_i, u_i \in \mathbb{R}^{p-1} \).
- All rectangles that need to be search are kept in the list \( L \), i.e. \( L = \displaystyle \bigcup_{i=1}^{|L|} R_i \) where \( |L| \) represents the number of rectangles in \( L \).
- A rectangle's volume-based measure is denoted as \( (R_i \rightarrow A) \) where \( R_i \in L \). \( (R_i \rightarrow A) = \displaystyle \prod_{\substack{j \in \{1,\ldots,p\} \\ j \neq k}} (u_{ij}-y^I_j) \).

- Version
- 1.0

- Date
- March, 2014