Boundary Decomposition for Nadir Objective Vector Estimation

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find our method is novel and has theoretical guarantees.

We address your concerns as follows.

W1. Presentation.

Transition from Section 2 to Section 3. Thank you for raising this concern. It is better to choose ``Related Works'' as the title of Section 2. We will also include transitional statements at the beginning of Section 3.

Role of properties. The three properties imply that cone domination defines a strict partial order. These properties are not utilized subsequently. We apologize for the implicit statement and will simplify the description based on your response.

Relationship between theorems and the new method. We believe the relationship is clearly stated. Each theorem is associated with a corresponding explanation or utilized in a specific context. We may improve clarity by providing a summary.

Theorems 1 and 2 are primary theoretical foundations for employing BDNE to determine the nadir objective vector. The user-friendly parameter $\mu$ in BDNE is proposed based on Theorem 3. Theorem 5 is instrumental in some strategies of BDNE (e.g., the coping strategy for flat fitness). Theorem 4 extends Theorem 1. While it is not directly related to BDNE, it is crucial for proving Theorem 5.

Illustrations of new concepts. Thank you for the suggestion. We will show the level surfaces of boundary subproblems and their optimal solutions on an example $PF$ (see Figure 1 of the one-page PDF). Cone domination and proper Pareto optimality are not new concepts. We have cited relevant studies in our paper.

Motivation behind mentioning concepts. Cone domination has a strong connection with the boundary subproblem as reported in Theorem 2, which is the motivation for mentioning this concept. Proper Pareto optimality is introduced to replace the obscure parameter (i.e., $\alpha$) with an easy-to-understand one (i.e., $\mu$). We will improve the clarity in the revised paper.

Tables. Thank you for the suggestion. We will present the results in one table. An example is Table 1 of the one-page PDF.

W2. Significance of the accurate nadir objective vector.

We agree with you that normalization may not require an exact nadir objective vector. However, an accurate nadir objective vector is important in many scenarios and many exact methods are proposed in [1,2]. We list some consequences of inaccurate estimation of the nadir objective vector as follows:

• Inaccurate nadir objective vectors degrade the performance of exact algorithms [3], evolutionary algorithms [4], and multi-objective learning [5].
• An accurate nadir objective vector is often the assumption of interactive algorithms [6,7]. Inaccurate nadir objective vectors may cause biased decisions.

Existing exact methods have limitations in applicability (e.g., continuous problems). Heuristic methods only perform well on manually designed benchmark problems since they often have simple feasible objective regions [4,8,9]. Real-world problems usually have irregular feasible objective regions, making their nadir objective vectors difficult to estimate [10,11]. Therefore, we propose BDNE, which is the first method with theoretical guarantees and general applicability in multi-objective optimization. Our method can easily adopt various solvers for different tasks and achieve a trade-off between runtime and accuracy.

Q1. Eq. (3) versus Eq. (9).

The mathematical properties of Eq. (3) remain valid for Eq. (9). The solutions associated with the critical points are invariant after the normalization (i.e., scaling and translation), which is straightforward. We further explain the reasonability behind this conversion in Lines 185-188.

Q2. Ideal assumptions in Lines 128-130.

The statements in Lines 128-130 refer to an ideal method, not ideal assumptions. This ideal method aims to demonstrate the preliminary feasibility of boundary decomposition in identifying the nadir objective vector. It motivates us to propose the BLOP, which is a practical optimization task.

Q3. Criteria used to select test problems.

Please refer to Common Concern 3.

Q4. Too many function evaluations.

Our method can achieve a trade-off between runtime and accuracy. We aim to ensure the algorithm converges sufficiently, validating our theoretical claims empirically. Consequently, we allocate a large number of function evaluations for each algorithm.

Q5. Results on scalable problems with 3, 5, and 8 objectives.

Our theoretical results hold for any number of objectives. You can refer to Common Concern 3 for an explanation and the supplementary experiments.

References

[1] Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.

[2] On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.

[3] New $\epsilon$-constraint methods for multi-objective integer linear programming: A Pareto front representation approach. EJOR, 2023.

[4] A new two-stage evolutionary algorithm for many-objective optimization. TEVC, 2019.

[5] Hypervolume maximization: A geometric view of Pareto set learning. NeurIPS, 2023.

[6] Multiobjective optimization: Interactive and evolutionary approaches. 2008.

[7] A mini-review on preference modeling and articulation in multi-objective optimization: current status and challenges. Complex & Intelligent Systems, 2017.

[8] Regular Pareto front shape is not realistic. CEC, 2019.

[9] A survey of normalization methods in multiobjective evolutionary algorithms. TEVC, 2021.

[10] An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.

[11] A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evolutionary Computation, 2021.

Thank you for your response. My primary concern is that the authors have not adequately addressed the practical significance of an exact nadir point. I would like to emphasize that most existing multi-objective optimization algorithms estimate the nadir point based on the current solution set. While I acknowledge that such estimates are not accurate, they do not constitute a bottleneck for these algorithms. I recognize that the exact calculation of the nadir point is an interesting problem, but I believe that the contribution of this paper to the field of multi-objective optimization is very limited. The empirical study in this paper only demonstrates that the proposed method could accurately calculate the nadir point, but not how the proposed method could improve the performance of a multi-objective optimization algorithm.

Inaccurate estimates do not constitute a bottleneck for multi-objective optimization algorithms.

We also respectfully disagree with this statement. Experimental results on existing benchmarks cannot reflect the algorithm's real capability, as these benchmarks are manually designed with special features and can only be used to evaluate the algorithm's specific properties [1]. We provide the following experiment to demonstrate that inaccurate nadir objective vector estimation can have a significant impact on algorithm performance. We consider MOEA/D and NSGA-III. We replace their nadir objective vector estimation methods with ours and denote the variant as "V1". The mean and standard deviation of the hypervolume metric values are reported in the table. We can find that both MOEA/D-V1 and NSGA-III-V1 significantly outperform their original versions, respectively. Additionally, MOEA/D-V1 exhibits clearly smaller standard deviations compared with its original versions (e.g., 0.01 versus 0.003), indicating more stable performance. NSGA-III-V1 also yields stable performance.

We hope the above experiment can help you better understand the significance of the accurate nadir objective vector.

[1] Ishibuchi et al. Performance of Decomposition-Based Many-Objective Algorithms Strongly Depends on Pareto Front Shapes. TEVC, 2017.

Limited contribution to multi-objective optimization.

We cannot agree with you on this point as well. Nadir point estimation has always been a fundamental yet important research direction in multi-objective optimization, and many papers have been published on this topic. We search on Google Scholar using ("nadir point" OR "nadir objective vector") AND ("estimate" OR "find" OR "compute") and return over 8,000 results. Compared with existing methods, our method is the first work with theoretical guarantees and general applicability. We would like to emphasize that our method is not only able to accurately estimate the nadir objective vector but also can trade off the accuracy for faster runtime. Our method can cope with scenarios that require the accurate nadir objective vector while ensuring broad applicability to cases that do not need an accurate nadir objective vector.

How the proposed method could improve the performance of an algorithm?

We further improve NSGA-III-V1 by focusing the search within the promising region defined by the nadir objective vector. The statistical results of the hypervolume metric are presented in the following table. The improved version of NSGA-III-V1 is termed NSGA-III-V2. According to the results, our method shows great potential to improve the performance of an algorithm. Moreover, we find that NSGA-III-V2 retains more solutions within the promising region compared with NSGA-III-V1 (30 versus 39 on TN1, 25 versus 32 on TN2, 32 versus 38 on TN3, and 25 versus 33 on TN4). This explains the performance improvement and demonstrates the effectiveness of the scheme.

Thanks for your further comments. Below is our point-to-point response.

Practical significance of an exact nadir point.

Firstly, we must clarify that our method is not just an exact algorithm, and its accuracy and runtime can be balanced via a controllable parameter. Secondly, we do not intend to claim that the accurate nadir objective vector is necessary for all multi-objective optimization scenarios. What we emphasize is that we should not ignore the cases where the accurate nadir objective vector is essential. There have already been a lot of works devoted to accurate nadir objective vector estimation [1-13]. We provide the following three examples:

• The nadir objective vector frequently serves as the reference point of scalarization methods. Some applications require specifying an accurate nadir objective vector beforehand [10,11]. An underestimated nadir objective vector makes some Pareto-optimal solutions unattainable, whereas an overestimated one results in poor uniformity of obtained objective vectors.
• The nadir objective vector determines the search space for some exact methods, such as AUGM-2. Exact methods without an accurate nadir objective vector may skip some Pareto-optimal solutions or exhibit longer runtimes. A recent experimental analysis can be found in [12].
• Many interactive methods, such as the NIMBUS method, require accurate nadir values to present the promising region of the objective space for decision-makers [13]. If inaccurate nadir values are given, more interactions are conducted or a biased decision is made.

[1] Ehrgott et al. Computation of ideal and nadir values and implications for their use in MCDM methods. EJOR, 2003.

[2] Klamroth et al. Integrating Approximation and Interactive Decision Making in Multicriteria Optimization. OR, 2007.

[3] Dhaenens et al. K-PPM A new exact method to solve multi-objective combinatorial optimization problems. EJOR, 2010.

[4] Florios et al. Generation of the exact Pareto set in Multi-Objective Traveling Salesman and Set Covering Problems. Applied Mathematics and Computation, 2014.

[5] Kirlik et al. Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.

[6] Köksalan et al. Finding nadir points in multi-objective integer programs. Journal of Global Optimization, 2015.

[7] Boland et al. A new method for optimizing a linear function over the efficient set of a multiobjective integer program. EJOR, 2017.

[8] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.

[9] Altamiranda et al. A New Exact Algorithm to Optimize a Linear Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programs. INFORMS Journal on Computing, 2020.

[10] Zhang et al. Hypervolume maximization: A geometric view of Pareto set learning. NeurIPS, 2023.

[11] Mena et al. Multi-objective two-stage stochastic unit commitment model for wind-integrated power systems: A compromise programming approach. International Journal of Electrical Power & Energy Systems, 2023.

[12] Mesquita-Cunha et al. New $\epsilon$-constraint methods for multi-objective integer linear programming: A Pareto front representation approach. EJOR, 2023.

[13] Branke et al. Multiobjective optimization: Interactive and evolutionary approaches. 2008.

Most multi-objective optimization algorithms estimate the nadir point based on the current solution set.

We respectfully disagree with this statement. Many works show that only multi-objective evolutionary algorithms often use the current solution set to estimate the nadir objective vector [1]. Other widely adopted nadir objective vector estimation methods include the pay-off table method [2], extreme-point-based methods [3], subset-selection-based methods [4], and exact methods [5].

[1] He et al. A survey of normalization methods in multiobjective evolutionary algorithms. TEVC, 2021.

[2] Reeves et al. Minimum values over the efficient set in multiple objective decision making. EJOR, 1988.

[3] Deb et al. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. TEVC, 2014.

[4] Mallipeddi et al. A twin-archive guided decomposition based multi/many-objective evolutionary algorithm. Swarm and Evolutionary Computation, 2022.

[5] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.

Thank you for your response. Now most of my major concerns have been satisfactorily addressed, so I increased my rating. I know it is very difficult to prepare the additional results during the rebuttal period, so I do appreciate your efforts. However, I strongly suggest the authors incorporate a more comprehensive and solid empirical study in the camera-ready version (if accepted) including a comparison with other strong baselines on more test problems and an ablation study to explore how BDNE helps improve the performance of MOAs in practical scenarios. I think a wide range of audiences may be interested in these results.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find this work is well organized, the analysis of existing methods is detailed and clear, and our method is demonstrated theoretically and experimentally.

we address your concerns as follows.

W1. Significance of BDNE.

The nadir objective vector is an essential component of several fundamental operations (e.g., normalization, interaction, and guided search) in multi-objective optimization. In many engineering problems, the nadir objective vector has already been utilized to facilitate optimization [1,2,3].

Despite the introduction of many exact and heuristic methods, a unified paradigm to estimate the nadir objective vector remains absent. Our method is the first one with theoretical guarantees and general applicability in multi-objective optimization. Our method can be applied to various scenarios by employing appropriate solvers. Furthermore, the trade-off can be easily determined by decision-makers via setting a parameter.

W2/Q1. Unchanged boundary subproblems waste computational resources. Can they change after some iterations?

These unchanged boundary subproblems use the unit vectors as their weight vectors. They motivate the search for the ideal objective vector, which serves as $\mathbf{z}^{r1}$. Besides, it enhances population diversity when the adjustable boundary subproblems become similar. In Table 1 of the one-page PDF, BDNE-V2 denotes BDNE removing boundary subproblems with unit vectors. We can find that BDNE outperforms BDNE-V2 across most instances. The effectiveness of these subproblems is demonstrated empirically.

Changing these subproblems after some iterations is an interesting idea. Further investigations will be conducted to explore this.

W3/Q3. Longer runtime.

The runtime for BDNE strongly depends on the implementation. The main loop of our implementation has a time complexity of $O\left(N^2\log(N)\right)$ where $N$ is the population size. The specific analysis is provided as follows. The reproduction procedure has a time complexity of $O(N)$. The calculation of $\mathbf{r}$ governs the complexity of the selection procedure, which has $O\left(N^2\log(N)\right)$. The adjustment of boundary weight vectors with $O\left(N\log\left(\frac{N}{m}\right)\right)$ is executed periodically. Therefore, The selection procedure governs the overall complexity. The main loop has the complexity $O\left(N^2\log(N)\right)$. We will include the computational complexity analysis in the revised version.

We use an effective selection procedure stated in [4], which can facilitate the application of BDNE to various problems. We can significantly reduce the complexity by using a simple selection procedure or choosing an alternative solver, which deserves further investigation.

W4/Q2. Criteria of setting $\mu$.

$\mu>0$ is a user-defined parameter, indicating a bounded trade-off preferred by decision-makers. Once $\mu$ is determined, $\alpha$ in Eq. (3) can be calculated (see Lines 155-162). If the preferences of decision-makers are not available, $\mu$ can be set to a reasonably large value. In the experimental studies, we demonstrate that BDNE with $\mu=100$ can have an overall good performance. We will improve the clarity in the revised paper.

Q4. BDNE versus exact methods on discrete problems.

A comparison of our methods to existing exact methods is summarized in the following table. The exact method involves a more complicated optimization task, which includes more single-objective optimization problems or slack variables. Some exact methods require the variable to be discrete. Moreover, existing exact methods do not accommodate a user-defined trade-off.

We choose an exact solver for BDNE to validate its effectiveness empirically. BDNE has a leading performance in terms of runtime (please refer to Common Concern 2).

References

[1] Weerasuriy et al. Performance evaluation of population-based metaheuristic algorithms and decision-making for multi-objective optimization of building design. Building and Environment, 2021.

[2] Mena et al. Multi-objective two-stage stochastic unit commitment model for wind-integrated power systems: A compromise programming approach. International Journal of Electrical Power & Energy Systems, 2023.

[3] Ekhtiari et al. Optimizing the dam site selection problem considering sustainability indicators and uncertainty: An integrated decision-making approach. Journal of Cleaner Production, 2023.

[4] Zheng et al. A generalized scalarization method for evolutionary multi-objective optimization. AAAI, 2023.

[5] Kirlik et al. Computing the nadir point for multiobjective discrete optimization problems. Journal of Global Optimization, 2015.

[6] Köksalan et al. Finding nadir points in multi-objective integer programs. Journal of Global Optimization, 2015.

[7] Özpeynirci et al. On nadir points of multiobjective integer programming problems. Journal of Global Optimization, 2017.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find our method is concise, has broad applicability, and demonstrates its effectiveness theoretically and experimentally.

we address your concerns as follows.

W1/W2. BDNE is a general approximate algorithm.

BDNE can accurately determine the nadir objective vector, as long as an exact solver is available. BDNE can achieve satisfactory performance for a specific task, as long as a suitable solver is utilized. This paper proposes a general framework applicable to various scenarios, such as multi-objective integer linear programming with available exact solvers, and multi-objective learning utilizing gradient information.

To demonstrate that BDNE can be a promising exact algorithm, we apply BDNE to the discrete problem and choose an exact solver. We test BDNE on the multi-objective assignment problem (MOAP) and the multi-objective knapsack problem (MOKP). 3 instances are randomly generated for each problem. The following table shows the mean and standard deviation of error metric values. Our method is accurate, while the heuristic method misses the nadir objective vector. The superiority is also demonstrated, as shown in Common Concern 2.

W3. Applicability of other multi-objective optimization algorithms for lower-level optimization.

We would like to clarify that the LLOPs constitute a set of single-objective optimization problems (SOPs) rather than an MOP. Therefore, not all multi-objective optimization algorithms are suitable for the lower-level optimization. Nevertheless, these SOPs can be solved sequentially or in parallel. We employ a decomposition-based multi-objective optimization algorithm to collaboratively address these SOPs, thereby enhancing optimization efficiency.

Q1. Evidence of really complicated feasible objective region.

Real-world problems usually have many constraints that can result in irregular feasible objective regions. A comprehensive review of these industrial cases is provided in [1,2].

Q2. Can the complicated lower-level optimization algorithm be changed?

Yes. We can change the selection strategy in this algorithm to reduce the complexity. This is because this algorithm employs an efficient selection strategy as described in [3], which governs the overall complexity. Moreover, the optimizer of LLOPs can be changed to any suitable one according to the task's properties. For example, use other decomposition-based evolutionary algorithm frameworks [4]. Local search (or gradient information, if available) can be employed to facilitate the convergence [5,6]. All single-objective optimizers such as GUROBI and BARON can also be applied to solve the LLOP, as the LLOP is a single-objective optimization problem.

Q3. Can the method proposed in (Gokhan et al. 2015) adopt the evolutionary algorithm as the solver?

This method relies heavily on an exact solver. This method is time-consuming and unreliable when the evolutionary algorithm is adopted. Specifically, its lower-level optimization problem, including two sequential single-objective optimization problems, exhibits high computational costs. Furthermore, uncertain optimality gaps arise when the evolutionary algorithm is adopted. As a result, the first single-objective optimization problem misleads the subsequent one, thereby presenting significant unreliability in the lower-level optimization process. The pay-off table, which is a key step, also cannot be accurately obtained.

In contrast, our method does not require the payoff table, and the lower-level optimization problem is an independent single-objective optimization problem.

Q4. Criteria used to select benchmarks.

Please refer to Common Concern 3.

Q5 & Q6. Ablation studies.

The experimental results are presented in Table 1 of the one-page PDF. BDNE-V1 denotes BDNE without the coping strategy for flat fitness. BDNE-V2 denotes BDNE removing boundary subproblems with unit vectors. The effectiveness of the two strategies is validated.

Q7. More detailed analysis of deficiencies of the heuristic methods.

We aim to point out that heuristic methods do not guarantee obtaining exact objective vectors. We construct an example $PF$ and then find all heuristic methods can not identify its nadir objective vector. We believe this example is clear and intuitive. Additional analysis is not necessary to support the above claim.

References

[1] Tanabe et al. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.

[2] Kumar et al. A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evolutionary Computation, 2021.

[3] Zheng et al. A generalized scalarization method for evolutionary multi-objective optimization. AAAI, 2023.

[4] Ke Li. A survey of decomposition-based evolutionary multi-objective optimization: Part I-past and future. arXiv preprint, 2024.

[5] Lara et al. HCS: A new local search strategy for memetic multiobjective evolutionary algorithms. TEVC, 2010.

[6] Lapucci et al. A memetic procedure for global multi-objective optimization. MPC, 2023.

Thank you very much for your time and effort in reviewing our work. We are glad to know that you find this work is important and well-written, the analysis of existing methods is convincing, and our method has wide applicability.

we address your concerns as follows.

Q1. Why is CMA-ES used for the optimization of upper-level problems but not for lower-level problems?

We utilize CMA-ES as the optimizer for ULOP for two reasons. First, CMA-ES is a state-of-the-art algorithm for single-objective black-box optimization. Second, optimal solutions to the LLOPs are not always available; instead, approximate solutions are often obtained. Consequently, the function values of the approximate solutions may exhibit noise. CMA-ES is suitable for this task as it demonstrates strong robustness in optimizing noisy functions [1].

CMA-ES can be used to solve the LLOP since the LLOP is a single-objective optimization problem. We utilize an MOEA to cooperatively solve the LLOPs. This is because the superiority of MOEAs is demonstrated empirically and theoretically in solving multi-objective black-box optimization problems [2,3].

Q2. Criteria of setting $\mu$.

$\mu>0$ is a user-defined parameter, indicating a bounded trade-off preferred by decision-makers. Once $\mu$ is determined, $\alpha$ in Eq. (3) can be calculated (see Lines 155-162). If the preferences of decision-makers are not available, $\mu$ can be set to a reasonably large value. In the experimental studies, we demonstrate that BDNE with $\mu=100$ can have an overall good performance.

Q3. A small value of $\mu$: Suppose I select a relatively small value of $\mu$ and obtain a point consisting of the optimal values of bilevel optimization problems. Does this mean that in the area where the objective vectors do not dominate the point, there are no Pareto optimal objective vectors with a minimum $M$ value less than $\mu$?

Yes. That is, the Pareto-optimal solution does not address the user-defined trade-off $\mu$ if it does not dominate the point constructed by the optimal values of BLOPs. The optimal solution of the $i$-th BLOP has the largest value of the $i$-th objective function among all the solutions addressing the trade-off. The conclusion can be deduced by Theorems 2 and 3. A satisfactory pseudo-nadir objective vector can be obtained if the decision-makers prefer a relatively small value of $\mu$. This preference-compatible property enables our method to have greater application potential. We will add the new claims and their proofs to the revised version.

Q4. Large error on CRE5-3-1.

Thank you for the careful review. The $PF$ of CRE5-3-1 is unknown and represented by the non-dominated objective vector set provided in [4]. The approximate $PF$ may be the reason for the large error since the results of DNPE and BDNE are similar.

Q5. Why are algorithms only tested on continuous problems?

We test BDNE on the discrete problem and choose an exact solver. Compared with exact methods, BDNE still has a superior performance in terms of runtime (please refer to Common Concern 2).

References

[1] Nikolaus Hansen. The CMA evolution strategy: A tutorial. arXiv preprint, 2016.

[2] Zhang et al. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. TEVC, 2007.

[3] Dang et al. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. AIJ, 2024.

[4] Tanabe et al. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing, 2020.