Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

Anh Viet Do; Aneta Neumann; Frank Neumann; Andrew M. Sutton

Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

Anh Viet Do, Aneta Neumann, Frank Neumann, Andrew M. Sutton

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023
Editors	A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, S. Levine
Publisher	Neural information processing systems foundation
ISBN (Electronic)	9781713899921
State	Published - 2023
Event	37th Conference on Neural Information Processing Systems, NeurIPS 2023 - New Orleans, United States Duration: Dec 10 2023 → Dec 16 2023

Publication series

Name	Advances in Neural Information Processing Systems
Volume	36
ISSN (Print)	1049-5258

Conference

Conference	37th Conference on Neural Information Processing Systems, NeurIPS 2023
Country/Territory	United States
City	New Orleans
Period	12/10/23 → 12/16/23

Bibliographical note

Publisher Copyright:
© 2023 Neural information processing systems foundation. All rights reserved.

Find It

Find It at U of M Libraries

Cite this

Do, A. V., Neumann, A., Neumann, F., & Sutton, A. M. (2023). Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds.), Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023 (Advances in Neural Information Processing Systems; Vol. 36). Neural information processing systems foundation.

Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems. / Do, Anh Viet; Neumann, Aneta; Neumann, Frank et al.
Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023. ed. / A. Oh; T. Neumann; A. Globerson; K. Saenko; M. Hardt; S. Levine. Neural information processing systems foundation, 2023. (Advances in Neural Information Processing Systems; Vol. 36).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Do, AV, Neumann, A, Neumann, F & Sutton, AM 2023, Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems. in A Oh, T Neumann, A Globerson, K Saenko, M Hardt & S Levine (eds), Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023. Advances in Neural Information Processing Systems, vol. 36, Neural information processing systems foundation, 37th Conference on Neural Information Processing Systems, NeurIPS 2023, New Orleans, United States, 12/10/23.

Do AV, Neumann A, Neumann F, Sutton AM. Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems. In Oh A, Neumann T, Globerson A, Saenko K, Hardt M, Levine S, editors, Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023. Neural information processing systems foundation. 2023. (Advances in Neural Information Processing Systems).

Do, Anh Viet ; Neumann, Aneta ; Neumann, Frank et al. / Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems. Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023. editor / A. Oh ; T. Neumann ; A. Globerson ; K. Saenko ; M. Hardt ; S. Levine. Neural information processing systems foundation, 2023. (Advances in Neural Information Processing Systems).

@inproceedings{28ccb086733a4d8da2a99a4705ea3aa0,

title = "Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems",

abstract = "We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.",

author = "Do, {Anh Viet} and Aneta Neumann and Frank Neumann and Sutton, {Andrew M.}",

note = "Publisher Copyright: {\textcopyright} 2023 Neural information processing systems foundation. All rights reserved.; 37th Conference on Neural Information Processing Systems, NeurIPS 2023 ; Conference date: 10-12-2023 Through 16-12-2023",

year = "2023",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

editor = "A. Oh and T. Neumann and A. Globerson and K. Saenko and M. Hardt and S. Levine",

booktitle = "Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023",

}

TY - GEN

T1 - Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

AU - Do, Anh Viet

AU - Neumann, Aneta

AU - Neumann, Frank

AU - Sutton, Andrew M.

PY - 2023

Y1 - 2023

N2 - We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.

AB - We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.

UR - http://www.scopus.com/inward/record.url?scp=85191169324&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85191169324&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85191169324

T3 - Advances in Neural Information Processing Systems

BT - Advances in Neural Information Processing Systems 36 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023

A2 - Oh, A.

A2 - Neumann, T.

A2 - Globerson, A.

A2 - Saenko, K.

A2 - Hardt, M.

A2 - Levine, S.

PB - Neural information processing systems foundation

T2 - 37th Conference on Neural Information Processing Systems, NeurIPS 2023

Y2 - 10 December 2023 through 16 December 2023

ER -

Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems

Abstract

Publication series

Conference

Bibliographical note

Find It

Other files and links

Fingerprint

Cite this