## 4 Methods for Generating a Near-Optimal Subset of Pareto Optimal Solutions
### Revised \(\epsilon\)-Constraint Method
**Corollary 2**. : _If \(f_{1}(\mathbf{x})\) can only take integer values (e.g., integer coefficients multiplied by integer decision variables), we can set \(\epsilon=1\) and use the revised \(\epsilon\)-constraint method to obtain a subset of Pareto optimal solutions whose objective vectors form the full set of nondominated objective vectors for the problem._  
The pseudocode for the revised \(\epsilon\)-constraint method is shown in Algorithm 2. ```
1:\(f_{1}^{\min}\leftarrow\min_{\mathbf{x}\in X}f_{1}(\mathbf{x})\) // \(f_{1}^{\min}\) represents the minimum objective value of the first dimension. ```  
**Algorithm 2** Revised \(\epsilon\)-constraint method ```
2:\(f_{2}^{\min}\leftarrow\min_{\mathbf{x}\in X}f_{2}(\mathbf{x})\) // \(f_{2}^{\min}\) represents the minimum objective value of the second dimension. 3:\(f_{1}^{\max}\leftarrow\min f_{1}(\mathbf{x})\) subject to \(f_{2}(\mathbf{x})\leq f_{2}^{\min},\mathbf{x}\in X\) // \(f_{1}^{\max}\) represents the minimum objective value of the first dimension when the second dimension achieves its minimum objective value. 4:\(\epsilon\leftarrow\) a small positive number such that \(f_{1}^{\max}-f_{1}^{\min}\) is an integer multiple of \(\epsilon\) // \(\epsilon\) represents the tolerance. 5:\(\hat{\mathbf{x}}(k)\leftarrow\) null, \(k\in\{0,1,\ldots,(f_{1}^{\max}-f_{1}^{\min})/\epsilon\}\) // \(\hat{\mathbf{x}}(k)\) represents an optimal solution obtained by [M2(\(k\))]. 6:\(\mathbf{x}^{*}(k)\leftarrow\) null, \(k\in\{0,1,\ldots,(f_{1}^{\max}-f_{1}^{\min})/\epsilon\}\) // \(\mathbf{x}^{*}(k)\) represents an optimal solution obtained by [M3(\(k\))]. 7:\(\Omega\leftarrow\varnothing\) // \(\Omega\) represents a multiset composed of obtained solutions by the revised \(\epsilon\)-constraint method. 8:for\(k\in\{0,1,\ldots,(f_{1}^{\max}-f_{1}^{\min})/\epsilon\}\)do
9: Solve the model [M2(\(k\))], and obtain an optimal solution \(\hat{\mathbf{x}}(k)\). 10: Solve the model [M3(\(k\))], and obtain an optimal solution \(\mathbf{x}^{*}(k)\). 11:\(\Omega\leftarrow\Omega\cup\{\mathbf{x}^{*}(k)\}\). 12:endfor
13: Discard solutions with the same objective vector in \(\Omega\) and retain only one of them. 14: Return \(\Omega\). ```

**Algorithm 2**_Cont._

### Improved Revised \(\epsilon\)-Constraint Method

The following improved revised \(\epsilon\)-constraint method, which generates exactly the same subset of Pareto optimal solutions as the above revised method, can improve the computational efficiency in many cases. Define a multiset \(\Omega:=\varnothing\). \(K:=(f_{1}^{\max}-f_{1}^{\min})/\epsilon\). Set \(k\gets K\). We solve the model [M2(\(k\))] and obtain an optimal solution \(\hat{\mathbf{x}}(k)\). We then solve the model [M3(\(k\))] and obtain an optimal solution \(\mathbf{x}^{*}(k)\). Let \(\Omega\leftarrow\Omega\cup\{\mathbf{x}^{*}(k)\}\). Let \(\hat{k}\) be the largest integer satisfying \(f_{1}^{\min}+\hat{k}\epsilon<f_{1}(\mathbf{x}^{*}(k))\). If \(\hat{k}<0\), return \(\Omega\) and stop. Otherwise, set \(k\leftarrow\hat{k}\) and repeat the above procedure of solving [M2(\(k\))] and [M3(\(k\))]. It is easy to see Propositions 3 and 4. **Proposition 3**. : _All solutions in \(\Omega\) are Pareto optimal, and no two solutions have the same objective vector._

**Proposition 4**. : _The improved revised \(\epsilon\)-constraint method generates the same subset of Pareto optimal solutions (more accurately, the same subset of nondominated objective vectors) as the revised \(\epsilon\)-constraint method._

Proof. : To differentiate the models and solutions of the revised method and the improved revised method, we add a prime \({}^{\prime}\) to the models and solutions of the improved revised method. Let us consider \"let \(\hat{k}\) be the largest integer satisfying \(f_{1}^{\min}+\hat{k}\epsilon<f_{1}(\mathbf{x}^{*}(k)^{\prime})\)\" in the improved revised \(\epsilon\)-constraint method. If \(\hat{k}=k-1\) in all cases, then the two methods are equivalent and generate the same subset of Pareto optimal solutions. Suppose that we have \(\hat{k}<k-1\) in at least one of the loops.