Research map / Learning theory and algorithms / Combinatorial and search optimization
Boundary Decomposition for Finding Nadir Objective Vector in Multi-Objective Discrete Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BDNC, an exact algorithm that computes the nadir objective vector of multi-objective discrete optimization problems by solving m bilevel problems built on boundary decomposition, with a lazy rectangle-pruning upper level and any exact single-objective solver at the lower level.
Problem
Computing the exact nadir objective vector of multi-objective discrete optimization problems (MODOPs), which is needed for decision-making but is hard to obtain with guarantees and low cost.
Approach
Applies boundary decomposition to recast nadir (critical point) search as m bilevel problems; the lower level is a boundary scalarization solved by any exact solver, and the upper level prunes an (m-1)-dimensional rectangle search space using propositions that mark invalid regions, with a lazy pruning order.
Key results
- BDNC has the best average rank (1.2) over 24 test problems (4 problem types, 720 instances), versus KL 2.2, KS 2.8, FD&IS 3.8 in median runtime.
- BDNC significantly outperforms KS and FD&IS on all 24 problems in median runtime per Wilcoxon tests at 0.05 level.
- BDNC has timeouts on only 3 instances of large-scale 5-objective MOAP, whereas the other methods time out on most 5-objective large instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BDNC instead of KL | MOAP, 3 objectives, 20×20 · MOAP, 3 objectives, 20×20 | median runtime (seconds): 107 -> 23.2 | Helped |
| Use BDNC instead of KL | MOAP, 4 objectives, 10×10 · MOAP, 4 objectives, 10×10 | median runtime (seconds): 21.2 -> 22.9 | Hurt |
| Use BDNC instead of KL | MOAP, 5 objectives, 10×10 · MOAP, 5 objectives, 10×10 | median runtime (seconds): 214.1 -> 265.7 | Hurt |
| Use BDNC instead of KL | MOAP, 3 objectives, 30×30 · MOAP, 3 objectives, 30×30 | median runtime (seconds): 1518.4 -> 192.3 | Helped |
| Use BDNC instead of KL | MOAP, 4 objectives, 15×15 · MOAP, 4 objectives, 15×15 | median runtime (seconds): 627.8 -> 163.4 | Helped |
| Use BDNC instead of KL | MOKP, 3 objectives, 200 variables · MOKP, 3 objectives, 200 variables | median runtime (seconds): 142.4 -> 96.6 | Helped |
| Use BDNC instead of KL | MOKP, 4 objectives, 50 variables · MOKP, 4 objectives, 50 variables | median runtime (seconds): 39.7 -> 37.1 | No clear effect |
| Use BDNC instead of KL | MOKP, 5 objectives, 50 variables · MOKP, 5 objectives, 50 variables | median runtime (seconds) | Helped |
| Use BDNC instead of KL | MOILP, 3 objectives, 80 variables · MOILP, 3 objectives, 80 variables | median runtime (seconds): 13.9 -> 18.6 | Hurt |
| Use BDNC instead of KL | MOILP, 4 objectives, 40 variables · MOILP, 4 objectives, 40 variables | median runtime (seconds): 22 -> 19.7 | Helped |
| Use BDNC instead of KL | MOILP, 5 objectives, 40 variables · MOILP, 5 objectives, 40 variables | median runtime (seconds): 928.7 -> 258.4 | Helped |
| Use BDNC instead of KL | MOSPP, 3 objectives, 50×50 · MOSPP, 3 objectives, 50×50 | median runtime (seconds): 52.4 -> 26.8 | Helped |
Surprising findings
- KL is faster than BDNC on the 3-objective MOILP and the 4-objective small-scale MOSPP, though gaps are small.
Limitations
- Guarantees depend on mild conditions and the finiteness of the Pareto front for convergence.
- Results depend on the choice of trade-off parameter mu (set to 10^6 in experiments when no preference is given).
- Anytime performance is not yet refined; the authors note future work on the pruning method.
Experimental setup
Datasets: randomly generated MOAP instances randomly generated MOKP instances randomly generated MOILP instances randomly generated MOSPP instances
Benchmarks: MOAP MOKP MOILP MOSPP
Metrics: median runtime (s) best and worst runtime (s) number of timeouts
Baselines: KS (Kirlik and Sayın 2015) KL (Köksalan and Lokman 2015) FD&IS (Özpeynirci 2017)
Builds on: boundary decomposition Kirlik and Sayın (2015) method Köksalan and Lokman (2015) method
Closest papers by meaning
- Boundary Decomposition for Nadir Objective Vector Estimation (NeurIPS 2024 · similarity 0.95)
- Using Clustering to Strengthen Decision Diagram Bounds for Discrete Optimization (AAAI 2024 · similarity 0.82)
- Smooth Tchebycheff Scalarization for Multi-Objective Optimization (ICML 2024 · similarity 0.82)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.82)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.82)
- Boundary Exploration for Bayesian Optimization With Unknown Physical Constraints (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.