Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems
Authors: Anh Viet Do
Aneta Neumann
Frank Neumann
Andrew M. Sutton
Venue: NeurIPS 2023 poster (2023)
Keywords: minimum weight base problem
multi-objective optimization
approximation
evolutionary algorithm
TL;DR: The paper studies the multi-objective minimum weight base problem and analyzes the run-time of MOEA/D in finding an approximation.

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.

Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems
Anh Viet Do
Aneta Neumann
Optimisation and Logistics
Optimisation and Logisties
The University of Adelaide, Australia
The University of Adelaide, Australia
Frank Neumann
Andrew M. Sutton
Optimisation and Logistics
Department of Computer Science University Minnesota Duluth, USA
The University of Adelaide, Australia
Abstract
We study the multi-objective minimum weight base problem, an abstraction classical NP-hard combinatorial problems such the multi-objective minimum spanning tree problem. We prove some important properties the convex hull the non-dominated front, such its approximation quality and upper bound 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-paranie parameter polynomial time, in the oracle model. Experiments are conducted random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Further- more, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.
Introduction
Evolutionary algorithms have been widely used to tackle multi-objective optimization problems in many such as robotics, pattern recognition, data mining, bioinformatics, scheduling and planning, and neural network training [35]. Their population-basee search operators make them natural choice for simultaneously handling several possibly conflicting objectives. Many generic evolutionary multi-objective frameworks have been developed to supply basic implementations for any problem, and to provide templates that can be fine-tuned for specific applications (we refer to [30) for an overview of common approaches). Such features, along with their strong empirical performances challenging applications, have led them becoming one of the most attractive topics to researchers and practitioners alike.
Among evolutionary multi-objective algorithms (EMOs), arguably the most exemplary dominance- based approaches such as GSEMO and NSGA variants, with the former often being considered a baseline. Another popular technique for multi-objective optimization is decompose the multiple objectives into a single-objective subproblem. The MOEA/D algorithm is state-of-the-ard application
of this technique in evolutionary computation 29 31]
Despite the prevalence of EMOs on practical applications, rigorous analyses of their runtime behavior meaningful problems scarce. Nevertheless, these kinds of analyses critical for (1) providing performance guarantees and guidelines to practitioners who use and develop these techniques in the field, and (2) promoting the explainability of heuristic search and optimization techniques by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

clarifying their working principles through a careful mathematical analysis. Run-time analyses on the performance of evolutionary algorithms have been provided for simple algorithms such as GSEMO in both artificial benchmark problems 7 and others such as bi-objective minimum spanning tree
18 28 and constrained submodular optimization [21 22 23 In recent years, theoretical analyses of state of the art approaches such as NSGA-II and MOEA/D have been conducted [22 14 13
34 6
However, these run-time results have only been given for artificial benchmark problems.
In this paper, we present for the first time rigorous results on MOLA/D for a classical multi-objective optimization problem, namely the multi-objective minimum weight base problem. This problem. falling under the matroid optimization category, significantly generalizes the previously studied bi-objective minimum spanning tree problem. In this work, we focus on approximating the non- dominated front, as its size can be exponential in the problem size. In particular, we show that MOEA/D obtains factor 2-approximation for two objectives in expected polynomial time. Previous analyses for the special case of graphic matroid (i.e. spanning forests) were only able to show peeudo-oolyooiil run-time for GSEMO and NSGA-II to obtain this approximation [8 We further extend the analyses by deriving fixed-parameter polynomial expected run-time in instances with 2 objectives to reach k-approximation. That is, unlike the previous runtime bounds, ours is both polynomial and weight-free under fixed k in light of the findings by Rechel et. al. 227
Instrumental to our analyses is a deeper understanding of the problem, and as such, we formally examine certain properties of the multi-objective minimum weight base problem. We first prove tight approximation guarantee from computing the convex hull of the non-dominated front, extending the known guarantee for two objectives [88] With this in mind, we explore insight regarding this convex hull, including vertex complexity and the structural relation among solutions whose weights constitute said convex hull. In addition, we briefly formulate an efficient deterministic approach to enumerate extreme points, which achieves a smaller approximation factor in lower (and weight-free) runtime than recently proposed framework for general multi-objective minimization instances [I] These findings may be of interest in areas beyond runtime analysis.
2 Preliminaries & Problem
First, we give an overview of relevant matroid theory concepts, with terminologies adopted from the well-known text book (20] on the subject.
Definition 1. A tuple M = (E,I c 25) is matroid af 0 I, b) Vx S SycEyel = X c) Vx,y E [x] < lyl = Ee E y \ x (e) I. The set E is the ground set, and I is the independence collection. A base of M is maximal set in I.
Definition Given a matroid M (E, I), its rank function, r 2 - N, is defined as r(x) max( y E 2 O I), and the rank of M is r(E). A matroid is completely characterized by its rank function.
To give examples, a K-rank uniform matroid over E admits the independence collection I (x S E |x] & K). characterizing a cardinality constraint. In linear algebra, representable matroid describes linear independence among a vector set. In graph theory, given an undirected graph graphic matroid M (E, I) defined by G is such that I contains all edge sets forming forest subgraph G. A base of a graphic matroid a spanning forest, which itself is an object of much interest. Dual to the graphic matroid, the bond matroid M = (E, I") is such that I' contains all edge sets x whose removal from E preserves every pairwise connectivity in G. The matroid properties emerge in many combinatorial structures of various optimization problems (20
(V, E),
classical application of matroids in optimization is in the minimum weight base (MWB) problem. Given a weighted matroid (E, w), this problem asks to find base in this matroid minimizing w. The most arguably well-known special case of MWB problem is the minimum spanning tree (MST) problem. It is known that the classical Greedy algorithm minimizes (and maximizes) arbitrary weight over base collection any matroid (24
From the exchange property between independent sets (specifically the symmetric-exchange property proven in R) we see that Greedy can also enumerate all minimum weight bases, thus characterizes the optimality of any MWB instance. proof of this quality is also included in (8).

---

The multi- multi--beeectve minimum weight base (MOMWB) is a natural multi-objective extension to MWB. Given a k-weighted matroid (E, r, w E (N*)(x(E)) where E is the ground set, r is the rank function of the matroid, and the weight vector a solution x E {0, 1)18i is wx (also called the image of x under w). the multi-objective problem asks to find non-dominated set of bases in (E,r) minimizing Here, k is the number of objectives.
We denote m := [E], == r(E), and observe that is base in (E,r) implies |x] = n. Given an objective vector function f and solutions x and y, x dominates y, denoted with x if y, iff f()) E R We see that x 5f iff ee (f((()) - f(x) 2 O, ie.. y has greater scalarized objective value than across all linear trade-offs. We denote the set of images of non- dominated solutions with F, and vertices of its convex hull Conv(F) are called extreme points. For convenience, let Conv(F) contain only points in F and that its faces be conventionally defined, i.e. as continuous Euclidean subspaces.
Since F can be exponentially large, we consider instead approximating it by finding solutions mapped to CF) Such a set is known to guarantee a 2-approximation of the non-dominated set for = 18 under the following definition.
Definition 3 (Minimization). Given k non-negative objective functions f == (f) solution c-approximates a solution y for some 2 0 Of f(x) e R A solution set X c-approximates (or is a c-approximation of) a solution set Y if every y E Y is c-approximated by at least a x E X.
We formally describe categories of solutions of interest. Here, we only consider feasible solutions, e.g. bases in a MWB or MOMWB instance. Furthermore, a subset of E is characterized by a bit-string in {0, 1)(8| so both set and bit operations on solutions are well-defined, and we use both representations throughout the paper.
Definition 4. A solution is supported solution to an instance with f f (fi
and a solution set if there a linear offe-off À [o, 1J (0) where x E argmin yes AT f(y). trade-off set A is complete if UZeA argmin fly) contains all supported solutions. A supported solution z is extreme if there is X' E [0, 11f where for all x E argmin yes f'y) f(z)== f(x). A set containing a trade-off for each extreme solution is called sufficient.
Note we assume that every instance admits solution minimizing f for every A E [0, 11 Of course, this holds for MOMWB due to the solution set being finite. We see that supported solutions are precisely the solutions whose images lie on Conv Intuitively, complete trade-off set decomposes the multi-objective instance in such a way to allow enumerating all supported solutions via exactly solving scalarized instances. Since supported solutions that are not extreme are mapped to points on the faces of Conv(F), we have the following observation.
Observation 1. For each supported solution minimizing AT there is an extreme solution minimizing f. For every A E [0, 1]*, there is an extreme solution minimizing fff.
However, for linear functions, the number of supported solutions can be very large, also consider finding a representative subset which, as we will see, is sufficient to give an approximation guarantee.
Definition 5. A solution set X is sufficient to instance with objective functions f if for every extreme solution y, there is x E X where f(x) = f(y). The analogy for supported solutions is called complete solution set.
With this definition, the set of solutions that are mapped to the extreme points is sufficient. In fact, the size of minimal sufficient set is exactly the number of extreme points. Note that while the set of all supported solutions is unique, there can be multiple distinct minimal sufficient sets due to duplicate images. We briefly prove approximation factor by any sufficient set, which is not restricted to MOMWB.
Theorem (Minimization). Given k 2 I and a non-negative k-objective instance where for each objective i there is 8, 0 so that fi(x) (0, (0,8, for all solutions every sufficient solution set P k-approximates all solutions. This factor is tight for all k. even if P is a complete solution set.
'The integrality does not affect the algorithms' behaviors, and is used only to ease the analysis. The positivity assumption ensures that approximation factors are meaningful.
3

---

We denote the weight scalarization with trade-off 2 with w == A www so (E, r, (()) is a scalarized instance at A. All proofs, including the one for the above result, are included in the Appendix.
3 Properties of Conv(F) in Multi-Ohjective Minimum Weight Base Problem
Here, we derive various properties of Conv(F) with implications on the complexity of approximating F. Since these solutions are optima of linearly scalarized instances, we use the properties of the Greedy algorithm, known to guarantee and characterize optimality in linear optimization over a matroid.
The Greedy algorithm starts from an empty set and adds elements to it in increasing weight order while maintaining its independence, until base is reached. In essence, Greedy operates on permutation over E and produces a unique solution so we can characterize its outputs via permutations. We say permutation over F, E (I...., .,., sorts the weight if, for all i I,..... Wr11() S (++)) As mentioned, Greedy run on a permutation that sorts the weight to be minimized returns a minimum weight base. More importantly, all minimum weight bases can be obtained by running Greedy on all sorting permutations. This allows us to derive properties of any solution mapped onto (F) using Greedy's 's behaviors. In particular, we can circumvent the difficulty of examiniig weights by examining permutations instead, essentially looking at the weight- induced rankings rather than the weights themselves. As such, all results in this section are weight-free and hold for arbitrary real weights. We refer to [I] for a teight-depnndent algorithmic treatment of CFnv(F) under general settings.
Observation 2. A MOMWB instance defined over ground set E satisfies the following: (1) its objective functions are linear, and (2) there is surjective mapping from the set of permutations over to the set of supported solutions.
To simplify analysis, we restrict the trade-off space non-negative 1-norm unit vectors U {a [0, 1]k Σ a; = 1). let πy be a permutation sorting (() for à U. For each i E E, let
w; (wy,)) and for each pair i, E, let 8.f- w, wy and A. aa laEU: U::U:0 : = o) be the iff A E Ar,. Finally,
(k- -ddimensional set characterized by the fact that for all A U. w; -²) w (2) let A be the multiset of con-emppy Ar, where 5t, # O, HA be the multiset of convex (k (1-11-ppoyyope in U defined by intersections of half-spaces bounded by hyperplanes in A and the boundary of U, and A' be the set of points in U where each point lies in the interior of a polytope in HA, we show that A and A' encompass complete solution set and sufficient solution set, respectively. Note that 8.j Wi Wi = 0, the inclusion of either i or j in solution does not change its image under w
Lemma 1. For any Q E HA, the set of all bases minimizing (A) remains constant for all À (nt(( and these bases share an image under w. Furthermore, they also minimize (() for all À E Q.
This immediately gives the upper bound on the number of extreme points, which is the maximum number of space partitions by hyperplanes: the formula for this is given in (32.. Note that Lemma Jnny requires properties in Observation 2 which hold for the broader class of set systems that is matroid embeddings since all minimum weight bases in such a system are exactly Greedy bases
Corollary 1. The size of minimal sufficient solution set to a k-oojective instance safisfying properties in Observation 2 is at most yk (m(mn-1)/2), and A' is sufficient trade-off set.
We remark that we deliberately choose each trade-off in A' from the interior of each polytope. This is because a zero trade-off coefficient assigned an objective, then bases minimizing the weight scalarized by such trade-off may not be non-dominated. Furthermore, such scalarized weights admit optima whose images under w are identical, which is necessary to ensure that the first optimum an optimization algorithm finds using these trade-off's is an extreme solution. Moreover, this trade-off
We include polytopes with empty interiors in HA account for overlapping hyperplanes in A. Furthermore, we assume these hyperplanes are ordered arbitrarily along their normal direction for the purpose of defining interior-free polytopes: h such hyperplanes form h 1 polytopes.
Given a set A in metric space, Int(A) is the set of its interior points.
4

---

selection scheme also guarantees that said algorithm does not discard vertices of Conv(F) over time, unless it stores all found optima.
Given a solution set S. the 1-Hamming neighborhood graph of S is an undirected graph Gj (S, {a b) la @ bl s 1)), and S is I-Hamming connected if G₁ is connected. Neumann [1]] proved for spanning trees that given the non-dominated front being strongly convex, the set of supported solutions is 2-Hamming connected. We show that this even holds for matroid bases without the convexity assumption. For simplicity, we assume, for the rest of the analysis, fixed orderings among each class of elements E sharing w;. We will see that the existence of such elements does not affect the 2- 2-Hamming connectivity among supported solutions.
We first show that as the trade-off off moves continuously within U, the permutation sorting the scalarized weight is transformed incrementally by exchanging two adjacent positions, which we call an adjacent swap.
Lemma 2. For any a, a' E U. let A' = (ai)/ be the multiset of intersections between the line segment connecting and a' and hyperplanes in A, indexed in the order from a to a', there is shortest sequence of adjacent swaps from Na to Ra, (Fa, Ti...., The R.)), where for all i = I,..., h, Tj sorts w(a). If w(a) w/a') can be sorted by multiple permutations, the claim holds assuming that Ta and Ne have maximum Kendall distance [
Next, we show that an adjacent swap on the sorting permutation incurs an at most 2-bit change in the minimum weight base.
Lemma 3. Let I and r' be permutations over that are one adjacent swap apart, and x and x' are Greedy solutions on them, respectively, then Ix @ x'1 S 2. Furthermore, let u, u E E where r(u) = r(u)+ + and r'())= = r' I, xx @ x'I = 2 iff x' = x {u) U (o).
Lemma [ and 3 indicate that there is a sequence of 2-bit flips between any pair of supported solutions such that every step also gives supported solution. Therefore, starting from supported solution, we can compute the rest of Cony(F) with 2-bit variations.
Regarding weight-sharing elements, for a supported solution x minimizing (A) if there is class of equal-weight elements Z partially intersecting x, then all supported solutions minimizing (()) containing different elements in Z can be reached from x by a sequence of 2-bit flips, each step in which produces a supported solution also minimizing ( This is because Z is located consecutively in πy and can be arranged arbitrarily (leading to the Greedy solution minimizing w()),, and there is sequence of adjacent swaps between any two such permutations touching only elements in Z. Furthermore, if there are multiple such classes whose elements share a scalarized weight at some trade-off A, the relative inter-class orderings in any valid πд can be shuffled arbitrarily with an adjacent swap sequence that neither, at any step, changes any pairwise intra-class ordering, nor breaks the sorting property. For these two reasons, the set of permutations sorting all scalarized weights is 1-Kendall connected (Kendall-diig -isttacee equivalence to Hamming connectivity), thus the relative intra-class orderings, and consequentially the presence of multiple elements within each such class, does not affect 2-Hamming connectivity.
Corollary 2. Given solutions x and y where {wx, wy) S Conv(F), there is non-empty set of solutions /z1)/_1 where x = zz, y y= Zh, 8 Z++1 = for all i = I,..., h-1 and {wz])/ (=1 S Conv(F),
Lemma 3 also lets us derive stronger bound on the number of distinct Greedy solutions as the trade-off moves in a straight line, giving an upper bound on the number of extreme points in case 2
Theorem 2. Given n (0, m)) a, and X is minimal set of extreme solutions such that for each 0 E [0, 1], X contains a solution minimizing w w((1-0)+0b)) |X] s hm - h(h + 1)/2+ + I where h =
V2 min m - n) -1.
Corollary 3. A bi-objective MWB instance (t.e. k = 2) admits at most O(m minn m n)) extreme points.
We remark that aside from the trivial cases n E (1, m - 1), we did not find an instance where this bound is tight. As far as we are aware, it is an open question whether this bound is optimal.
*Kendall distance between two permutations equals the minimum number of adjacent swaps needed to transform into the other [17]
5

---

Algorithm 1: Finding extreme points and a complete trade-off set (adapted from (10)
Input: Multi-weighted matroid (F, r, w)
Output: S.A
S, 0:
2 < (e:)
< all permutations over kl,
while A \ A' + 0 do
for 2 E A' do
Vp P. ap - base minimizing w()) prioritizing weights ranked by p;
S SU (pp)pep;
A' - UA:
non-negative normal vectors to facets of Conv((wx) S));
Algorithm 2: Special case of Algorithm [ for k
Input: Bi-weighted matroid (E,r, W1, w2)
Output: S,
1 S,A' < 0:
+ {0, 1);
3 while A \ # do
for 2
A' do
a, b - bases minimizing (1 A)w1 Aw2 prioritizing wi and w2, respectively;
$ S ba;
A' - A'
A 0:
element indexes of S in increasing wi order; for E (l....,,55 1} do
10
8,, Sr(p(al)) w)Sx((), w2S w2Sx(1+1);
12
A A- AU (8. 8z)};
4 Exact Computation of Extreme Points
In this section, we describe deterministic framework that finds a solution for each extreme point, as well as a complete trade-off set. This framework, modified from the algorithm proposed in [IO] for bi-objective MST, is outlined in Algorithm[] scalarized weights, and iteratively computes new extreme points based information from previous ones. Intuitively, each subset of extreme points contains, for each extreme point y Z, a facet separating from y. This means y can be discovered by minimizing the weight scalarized along the normal direction of this facet, essentially expanding Conv(Z) (Z) to "touch" y. This iterative process begins with an optimum in each objective, and ends when all new normal vectors are duplicates of ones found previously, indicating that the current convex hull cannot be expanded further and equals Conv(F). The special case of this algorithm for k = is given in Algorithm 2 which treats trade-offs as scalars.
[ It calls another algorithm (e.g. Greedy) to find MWB to
such that its convex hull is "inside" Conv ()) and
Algorithm 1 naively implemented, requires O # poly(k) + +!m log m)) operations and O(k! calls to the matroid rank oracle where # is the number extreme points. Fach iteration the main loop adds at least extreme point, and redundant points excluded from future iterations via A'. Here, we assume updating trade-off for each new vertex takes poly(k) operations.
We remark that exhaustive tie-breaking over all objectives is done at line ensure that the computed points are the vertices of Conv(F) instead of interior points its faces, and that all extreme points accounted for when the termination criterion is met. Furthermore, if the trade-off assigns value to some objectives, this also guarantees that the resulted solutions are non-dow non-dominated. This subroutine be improved by grouping together objectives whose sorting permutations agree (in relative orderings) among elements tied by (A)

---

Algorithm 3: MOEA/D for MOMWB
Input: A MOMWB instance, trade-off set A, neighborhood size N
Output: S
A2 A, BA N nearest neighbors of in A (Euclidean distance);
2 Ví E P. Px - a random sample from (0, 1)m;
S 0:
4 while stopping conditions not met do for À do
X + uniformly sampled from Pa;
y independent bit flips on x with probability 1/m;
D < {I E B2 Vz E f(()) < f((z);; + {I E B) Vz f(y) = f(());
10
e E P1 [y):
11
e T, - Pi (y) removing solutions with duplicate images;
12
S non-dominated individuals in S (y) under relation Zgi
5 MOEA/D With Weight Scalarization
Multi-Objectivn Evolutionary Algorithm based on Decomposition (MOEA/D), introduced 33 is co-evolutionary framework characterized by simultaneous optimization of single-objective subproblems a multi-objective problem. While there are many approaches to decompose the multi-objective into single-objectives, we consider the classical approach that is weight scalarization [15]. as hinted in preceding sections. This simple scheme is sufficient in approximating F and even enumerating Conv(F).
5.1 Description
MOEA/D uses two fitness functions, a scalar function formulated by the decomposition scheme and vector function for dominance checking (33. To account for the matroid base constraint, use the penalty term formulated in [26], which was adapted from prior work on MST [19]. Letting Wmax == max (t,e) (1,,,,)) x) Wie, we have the fitness fa of {0, 1}" "M at trade-off 2, and the fitness vector g for dominance checking where 1 is the one vector.
(xx == m(n - r(x) Wmax + (1) x, g(x) == m(n (xx) wx
The MOEA/D for the MOMWB problem is outlined in Algorithm 3 The fitness functions defined in Eq. (T) and the input trade-off set realize the decomposition, and the algorithm evolves a population for each scalarized subproblem with potential neighborhood-be -asedd collaboration. During the search, it maintains -ondimminteed solution S, which does not influence the search and is returned as output. An optimum to each scalarized subproblem is supported solution. Note in this formulation, MOFA/D keeps ties in each subproblem, allowing all found optima to participate in mutation operations. This is to avoid having to flip more than two bits to jump from supported solution to an uncollected point in Conv(F). We will see that while this may increase the population size, it does not affect the run-time to reach optimality in each subproblem.
5.2 Expected Time To Minimize Scalarized Weights
In the following, we do not assume particular value of N. and the results hold for any N 2 1. Furthermore, we exclude the trivial instances with n and n O, which admit exactly one base each.
Lemma 4. MOEA/D working trade-off set A finds a base's 's superset for each À A within O(AAmm log expected search points.
Let OPT, be the optimal value to (E,r, r, w()),, we have the following drift argument proven in 26 for the standard bit mutation in the MWB problem.
Lemma (26). Proposition 9). Given a trade-off E [0, 1] and x e (0. 13", ifx supersets base, then there 2-bit 2-bitfflips and 1-bit flips reducing fa(x) average by (fi(x) - -OTT)) /m.
7

---

We use the same ideas as the proof of Theorem 2 in [26,, while sharpening argument to derive slightly tighter bound.
Theorem 3. MOEA/D working on trade-off set A finds MWBs to instances scalarized by trade- offs in A in O (IA)m log n ΣAEA m² (1og(m n) + log Wmax + log d;)) expected search points where d2 == min a > 0: a², a(1 - A) N).
In order for MOEA/D to reach k-approximation and not lose it afterwards, it suffices that A is sufficient and each scalarized subproblem admits optima with a unique image. As mentioned and from Lemma] I this can be obtained by sampling from the interiors of convex polytopes in HĄ. For k= = 2, this can be done by taking a complete scalar trade-off set A (e.g. as returned by Algorithm 2 and include (a b)/2 (which is an interior point) for each non-empty interval (a, b) bounded by consecutive elements in U {0, 1}. Under the integer weights assumption, this method gives rational trade-offs whose integral denominators O w max), so we have the following bound from Corollary
3
Corollary 4. For a bi-objective instance, MOEA/D working minimal sufficient trade-off off set finds n)((llg(( nt) + log Wmax) log ri) expected
sufficient solution within O0m2 number of search points.
This method can be generalized to higher dimensions. Instead of taking an average of two consecutive elements, we can take the average of the vectors normal to facets of Conv(F) that meet at an extreme point, as this ensures the resulted trade-off À is not norma to any h-faces of Conv(F) for all h E [1,k], and that said extreme point minimizes w2) Since each facet is determinable by k points with integral coordinates, each such (I-norm unit) vector admits rational coordinates with denominator at most kww-x- Therefore, the trade-offs derived by this method admit rational representations whose denominators are O(kk+1 wh wmax), giving the run-ting run-time upper bound from Corollary under the assumption that k is sufficiently small.
Corollary Given k k-obbjective instance where k (m) and k E of o(Wmax), MOEA/D working on minimal sufficient trade-off set guarantees k-approximation within O(m" (m(log(m m - n) + (k 1) log Wmax) + log π)) expected number of search points.
As a side note, since MOEA/D uses standard bit mutation, we can replace Wmax with m and remove log d2 from the bound in Theorem 3 to arrive at weight-frre asymptotic bounds (27).
5.3 Expected Time To Enumerate Conv(F)
We see from Corollary 2 that MOEA/D with complete trade-off set can collect all points in Conv (F) with 2-bit flips starting from an optimum to each subproblem. As mentioned, this is afforded by allowing all found optima to undergo mutation.
Theorem 4. Assuming distinct supported solutions have distinct images under w, MOEA/D working on minimal complete trade-off set A, and starting from an optimum for each enumerates C : CFnv(F) in O(AAIC[?3m)) expected number of search points.
With this, Theorem 3 and Corollary 3 and T we have the following expected run-time bounds under the distinct image assumption. Note this assumption can be removed by having MOEA/D keep duplicate images at line 11
Corollary 6. For a bi-objective instance, MOEA/D working on a minimal complete trade-off set enumerates == Conv(F) in expected time O(m² 0 (n, m (mmmmmmmmm-)))) +33 Wmax + +CC logn)) n)).
Corollary 7. Given a k-objective instance where E omm) and k E o(Wmax), MOEA/D working on minimal complete trade-off set enumerates C == Conv(F) in expected time O (m(log m n) + (k+ 1) log Wmax |C(2) + log
'If à is normal to a face of Conv(F), then all points in this face minimize w (2), convex combination of vectors normal to some faces is normal to their (assumed non con-empty) intersection, the intersection of h adjacent d-faces a (d h + 1) face, and extreme point vertex is O-face.
8

---

Experimental Investigation
In this section, we perform computational runs of MOEA/D on various bi-objective minimum spanning tree instances. Spanning trees in a connected graph G (V, E) are bases the graphic matroid defined by G admitting the ground set E. The rank of such matroid (i.e. the size of the spanning tree) equals |V] - 1 and its rank function is defined with r(x) = |V] 171-ccle cc(x) where cc(x) is the number of connected components in (V.x). In notations, we have [V] and m [B]. We use simple undirected graphs in our experiments, and the edge-set representation of solutions in the implementations of the algorithms 25
6.1 Setting and Performance Metries
We uniformly sample graphs with [V] E {26, 51, 101) and [E] {150, 300). In this procedure, edges are added randomly into an empty graph up to the desired edge count, and this is repeated until connected graph is obtained. Each edge weight is an integer sampled independently from U111, 100). We generate two weighted graphs with each setting, making 12 instances total.
With this experiment, we aim to measure the algorithms' performances in finding solutions mapped to all extreme points, we denote this set of target points with R. We compare MOEA/D against GSEMO, previously studied for its performance in bi-objective MST [18]. For GSEMO, we use the fitness function g defined in Eq. T. Since GSEMO checks for dominance in each iteration across its entire population, we set N == |A| for MOEA/D to match. Here, the input A to MOEA/D is derived from a complete trade-off set output by Algorithm 2 in the manner described in Section 5.22 The points given by Algorithm| I Jaee the target points R, and each run is terminated if all target points are hit. Additionally, each run is terminated after most [3] log (m - n)] evaluations (each evaluation is call to function g). Each algorithm is run on each instance 10 times. Their performances are measured with the followings (S is the final population returned by the algorithm):
Success rate: The number of runs where all target points are hit within the evaluation budget.
Cover rate: The proportion of hit target points after termination, |R n {wx S)|/|R|. A is successful if this reaches 100%.
Modified inverted generational distance (IGD+): The distance between the output and the target points [6]. YEE minxes ΣE= (max( (wxx, yı. 0/) A run is successful if this reaches 0.
T: The number of evaluations until all target points are hit.
We remark that the fitnesses fa can be quickly computed alongside g. incurring minimal overheads. In fact, the run-time bottleneck is in checking the number of connected components.
6.2 Experimental Results
The results are shown in Table I with IGD+ and cover rate from MOEA/D omitted due them being 0 and 100% across all instances, respectively. These are contextualized by the listed instance-specific parameters. Of note is the number of target points [R] which is smaller than the upper bound in Theorem in all instances.
Immediately, we see the GSEMO failed to hit all target points within the evaluation budget in most runs, while MOEA/D succeeded in every run. In most cases, GSEMO hit at most one target point. Inspecting the output points and IGD+ reveals that its population converged well to the non-dominated front, yet somehow misses most extreme points. In contrast, MOEA/D hit all target points within up to 92% of the evaluation budget, though there are significant relative variances in the run-times.
Inspecting the run-times of MOEA/D in relation the evaluation budgets, we see that the means of ratios remain fairly stable across instances. This suggests the asymptotic bound in Theorem 3 is not overly pessimistic. Instances 5 and are particularly interesting as they are ostensibly the easiest due to the small number of extreme points, yet MOEA/D seems to require the most fractions of the budget. Given that these instances exhibit the smallest m n, this can be explained by the interference of lower-order terms in the asymptotic bound, which are not counted in the budgets.

---

Table I: Means and standard deviations of performance statistics from GSEMO and MOEA/D bi-objective MST instances. Means and standard deviations T are computed over successful runs only. All differences statistically significant.
GSEMO
MOEA/D
Id
[R] max eval.
Suc. rate
Cover rate
IGD+
T/max eval.
Suc.
T/max eval.
150
25
39
127 6
2/10
2.540.06%
0.13+0.11
79 %
10/10
50 15%
150
25
31
10103247
0/10
3.1 14%
0.25+0.32
N/A
10/10
43+11%
150
50
45
13988205
0/10
1.9=0.1%
1.740.7
N/A
10/10
52+11%
150
50
45
13988205
0/10
2+0.083%
0.92+0.23
N/A
10/10
47+12%
150
100
35
9242155
0/10
2.5%0.13%
2.6+1.2
N/A
10/10
63+15%
150
100
36
9506216
0/10
2.2+0.21%
3.7+2.3
N/A
10/10
58+11%
25
45
68243769
3/10
2.2+0.031%
0.06:0.072
86+13%
10/10
41=11%
300
25
49
74309882
1/10
2
0.076+0.083
9440%
10/10
40=8.1%
300
50
66
98392434
0/10
1420.048% %
0,49
N/A
10/10
50+11%
10
300
50
63
93920051
0/10
1.5+0.045%
0.840.24
N/A
10/10
60+ 60+15%
11
300
100
79
113013110
0/10
1.1+0.043%
240.53
N/A
10/10
60.8.3%
12
300
100
80
114443656
0/10
1.140.072%
3.1+1
N/A
10/10
58+119
7
Conclusion
In this study, we contribute to the theoretical analyses of evolutionary multi-objective optimization in the context of non-trivial combinatorial problems. We give the first run-time analysis of the MOEA/D algorithm for a broad problem class that multi-objective minimum weight base problem. In particular, we show a -aremmeereeter polynomial expected run-time for approximating the non- dominated front, simultaneously extending existing arbitrary number of objectives and broader combinatorial structures. Our experiments in random bi-objective minimum spanning tree instances indicate that MOEA/D significantly outperforms GSEMO in the computing extreme points under appropriate decomposition. Along the way, prove properties that give further insight into the problem of interest.
bounds for GSEMO to
Acknowledgements
This work was supported by Australian Research Council grants DP190103894 and FT200100536, and by National Science Foundation grant 2144080.
References
[1] C. Bazgan, S. Ruzika, C. Thielen, and D. Vanderpooten, "The power of the weighted sum scalarization for approximating multiobjective optimization problems," Theory of Computing Systems, vol. 66, no. 1, pp. 395-415, Nov. 2021.
[2] C. Bian, C. Qian, and K. Tang, "A general approach running time analysis of multi-objective evolutionary algorithms," " in Proceedings of the T International Joint Confer- Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, Jul. 2018, pp. 1405-1411.
[3] R. A. Brualdi, "Comments bases in dependence structures," Bulletin of the Australian Mathematical Society, vol. 1, no. 2, pp. 161-167, Aug. 1969.
[4] Cerf, B. Doerr, B. Hebras, Y. Kahane, and S. Wietheger, "The first proven performance guarantees for the non-dominated sorting genetic algorithm II (NSGA-II) combinatorial optimization problem," in Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. International Joint Conferences Artificial Intelligence Organization, Aug. 2023.
[5] A. V. Do and F. Neumano, "Maximizing submodular monotone functions under partition matroid constraints by multi-objective evolutionary algorithms," Parullel Problem Solving from Nature PPSN XVI. Springer International Publishing, 2020, pp. 588-603.
10

---

[6] B. DoeIT and Z. Qu "A first runtime analysis of the NSGA-II on a multimodal problem," IEEE Transactions on Evolutionary Computation, pp. 1-1, 2023.
[7] B. Doerr and W. Zheng, "Theoretical analyses of multi objeetvv evolutionary algorithms on multi-modal objectives." Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 14. pp. 12 293-12 301, May 2021.
[8] Edmonds, "Matroids and the greedy algorithm," Mathematical Programming, vol. no. 1, pp. 127-136, Dec. 1971.
[9] D. Gale, "Optimal assignments in an ordered set: An application of matroid theory," Journal of Combinatorial Theory, vol. 4, no. 2, pp. 176-180, Mar. 1968.
[10] H. W. Hamacher and G. Ruhe, "On spanning tree problems with multiple objectives," Annals of Operations Research, vol. 52, no. 4, pp. 209-230, Dec. 1994.
[11] P. Helman, B. M. E. Moret, and H. D. Shapiro, "An exact characterization of greedy structures," SIAM Journal on Discrete Mathematics, vol. 6, no. 2, pp. 274 283,, May 1993.
[12] Z. Huang, Y. Zhou, Z. Chen, and X. He, "Running time analysis of MOEA/D with crossover on discrete optimization problem," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, pp. 2296-2303, Jul. 2019.
[13] Z. Huang, Y. Zhou, Z. Chen, He, X. Lai, and X. Xia, "Running time analysis of MOEA/D on functions," IEEE Transactions on Cybernetics, vol. 51, no. 10. pp. $130-5141,
Oct. 2021.
[14] Z. Huang, Zhou, C. Luo, and Q. Lin, "A runtime analysis of typical decomposition ap- proaches in MOEA/D framework for many -bjjectee optimization problems," " in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, Aug. 2021, pp. 1682-1688.
[15] H. Ishibuchi and T. Murata, "A multi-objective genetic local search algorithm and its applica- tion to flowshop scheduling," " IEEE Transactions on Systems, Man and Cybernetics, Part (Applications and Reviews), vol. 28, no. 3, pp. 392-403, 1998.
[16] H. Ishibuchi, H. Masuda, Y. Tanigaki, and Y. Nojima, "Modified distance calculation in genera- tional distance and inverted generational distance," Evolutionary Multi-Criterion Optimization. Cham: Springer International Publishing, 2015, pp. 110-125.
[17] M. G. Kendall, "A new measure of rank correlation," Biometrika, vol. 30, no. 1/2, pp. 81-93, Jun. 1938.
[18] Neumann, "Expected runtimes simple evolutionary algorithm for the multi-objective minimum spanning tree problem," Europeun Journal of Operational Research, vol. 181, no. 3, pp. 1620-1629, Sep. 2007.
[19] Neumann and I. Wegener, "Randomized local search, evolutionary algorithms, and the minimum spanning tree problem," Theoretical Computer Science, vol. 378, no. 1, pp. 32-40, Jun. 2007.
[20] J. Oxley, Matroid Theory. Oxford University Press, Feb. 2011.
[21] C. Qian, Y. Yu, and Z.-H. Zhou, "Subset selection by pareto optimization." in Advances in Neural Information Processing Systems, vol. 28. Curran Associates, Inc., 2015.
[22] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou, "Subset selection under noise," in Advances Neural Information Processing Systems, vol. 30. Curran Associates, Inc., 2017.
[23] C. Qian, Bian, and Feng, "Subset selection by pareto optimization with recombination." Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 03, pp. 2408-2415, Apr. 2020.
[24] R. Rado, "Note on independence functions," Proceedings of the London Mathematical Society, vol. s3-7, no. 1. pp. 300-320, 1957.

---

[25] G. R. Raidl, "An efficient evolutionary algorithm for the degree- cogtte--onstrained minimum spanning tree problem." " in Proceedings of the 2000 Congress on Evolutionarr Computation. CEC 2000, vol. 1. IEEE, 2000, pp. 104-111.
[26] J. Reichel and M. Skutella, "Evolutionary algorithms and matroid optimization problems," Algorithmica, vol. 57, no. 1, pp. 187-206, Dec. 2008.
[27]
"On the size of weights in randomized search heuristics," in Foundations of Genetic Algorithms,, 10th ACM SIGEVO International Workshop. FOGA 2009, Proceedings. ACM, Jan. 2009, pp. 21-28.
[28] V. Roostapour, J. Bossek, and F. Neumann, "Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problem." " in Proceedings of the 2020 Genetic and Evolutionary Computation Conference. New York, NY, USA: ACM, Jun. 2020, p. 551-559
[29] A. Trivedi, D. Srinivasan, K. Sanyal, and A. Ghosh, "A survey of multiobjective evolutionary algorithms based on decomposition." IEEE Transactions Evolutionary Computation, vol. 21, no. 3, pp. 440-462, 2016.
[30] Z. Wang, Y. Pei, and J. Li, "A survey on search strategy of evolutionary multi-objective optimization algorithms," Applied Sciences, vol. 13, no. 7, p. 4643, Apr. 2023.
[31] Q Xu, Z. Xu, and T. Ma, "A survey of multiobjective evolutionary algorithms based decomposition: Variants, challenges and future directions," JEEE Access, vol. 8, pp. 41 588- 41 614, 2020.
[32] T. Zaslavsky, "Facing up arrangements: face-count formulas for partitions of space by hyperplanes," Memoirs of the Americun Mathematical Society, vol. 1, no. 154, pp. 0-0, 1975.
[33] Q Zhang and H. Li, "MOEA/D: A multiobjective evolutionary algorithm based decompo- sition," " IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, Dec. 2007.
[34] W. Zheng, Y. Liu, and B. Doerr, "A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II)." Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. pp. 10408-10416, Jun. 2022.
[35] A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, N. Suganthan, and Q Zhang, "Multiobjective evolu- tionary algorithms: A survey of the state of the art," Swarm and Evolutionary Computation, vol. 1, no. pp. 32 49, Mar. 2011.
12

---

A Omitted proofs
Proof of Theorem 1 Let f == (f) be the objective function vector, Z be any solution, Z = ( fi(z) = 0). if |Z| k then z is an extreme solution, so P 1-approximates z. Assume otherwise, define À E (0, 1] where 2 == e/d; if Z. and A; e/l(k [2)) otherwise for some sufficiently small é > O. By definition of sufficient solution set and Observation I there is x E P minimizing f. i.c AT f(x f() = e. If fi(x) > 0 for some E Z or fi(x) (k (z)) for some Z, then since f(x) E R we have T f(x) e, a contradiction. Therefore, and by extension P. (k aappoooooxss z. Since z can assume positive values in all objective factor simplifies to k.
@ this
We show tightness by construction. Let c (0,k), m == k2 Σ en- for i = I,...,k k where ej is the jth unit vector in R", we define a non non-negative k-objective instance over {0, r)m mi,x(f(x) == (0 x e /0
k-1 j=0 Xi- 1 : |x] k). We see that the set of all supported solutions
is precisely S == {0,) Let 2 = En= exxll be solution, for all i = l,....k k, f((0,) = k c N
(k c)((2) (equality T
if k > 1). This means S fails to (k c- e) ->aaproxie z for any e >
and can be arbitrarily small. Since S is complete solution set, the claim follows.
Proof Lemma I
Let e be any point in Int(Q), by definition of A, w/ w/ ww) (()) iff S, 0, and (())
admits multiple minima iff they contain different elements among those sharing weights in w()) while sharing all other elements. Indeed, let x and y be a pair of minima violating this condition, they must contain different sets of weights so for all bijection y between \ y and y x, there is x y(u)* this leads to a contradiction when combined with the base exchange property. This means these optima share image under w, and bases not having the same image do not minimize (())
where wa # (c)
Let b be any point on the boundary of Q and L be the set of points between b and excluding endpoints, we show that xe also sorts (b)) Let i.j E E where w/() < <wj then wi(") w/(/ implies
wi(d) w (d) for some d I., meaning I. meets hyperplane in A, contradiction as I. Int((). For all pairs j.j E. where w(()) w/ 6 = 0 w/ w With this, every pair is accounted for, so T. sorts wh)) Therefore, since Greedy guarantees optimality, any base minimizing (e) also minimizes (()), yielding the claim.
Proof of Corollary / We see that |A'|= |Hal, which is upper bounded by the number of half-space
intersections from hyperplanes in A. Since these are (k - -dimmeiimii hyperplanes, applying the formula in (2) gives [HAl >* ([A)) which is increasing in [A], the claim follows from |A| s
m(m- - 1)/2. We have A' is a sufficient trade-off set following from Lemma I and UQEHA Q QUU. o
Proof of Lemma 2 Let 0 < de. < Ad 1 such that b := (1 b)a + ba' A' and for all à [de, Ap). (1 - 1)a + da & A", and let c == (1 A,)a+ + Aod', then elements sharing weight in wibb must be mapped to consecutive positions in sTc. Indeed, let p.q E E (Fe(P) < (q)) where w/)
(b) w (b)
if there is (c) ww (c),,, we have wo connecting and с which implies d E A", a contradiction. Each such consecutive sequence of I positions contains 1(1 1)/2 pairs. From here, we consider two cases:
E where (o) (T), (T (q)) and w (b) w then since the former implies (d) wp or w Wq
w/ (wo)a)
(d) for some in the open line segment
If such a sequence contains no pair (i.j) where 5,, = O, then the aforementioned pairs correspond to [(I - 1)/2 duplicates of b in A", Furthermore, since the weights are transformed lincarly w.r.t. trade-off, for all sufficiently small e > O, these sequences are reversed between Te and (b-c) whereas positions not in these sequences are stationary. Reversing I consecutive positions requires 1(1 - 1)/2 adjacent swaps, so the Kendall distance between π, and Tb+e(b-c) equals the multiplicity of b A".
'If [Z] 2 k' for all solutions z, the instance is reducible to - -'))-bbjeettivee instances, and the guarantee factor is likewise tight.
13

---

If such a sequence contains h > 1 elements with the same weight at all trade-off, then these must occupy consecutive positions in Zg. As we assumed, the relative ordering among these elements is fixed, so exactly h(h - 1)/2 swaps are saved. Furthermore, any pair (i, j) among these elements is such that A., & A, meaning these h(h - 1)/2 pairs are already subtracted from A".
In any case, we can assign to each duplicate of in A' permutation sorting w(b) so that these form a sequence of adjacent swap from Ite to Tb+e(b-e) including (b+e(b-e) and not Tt. This directly yields the claim if a and a' are not in A"
Assume otherwise, then for all hyperplanes Ar containing a, w/ = w so for every such pair (i, D) we arrange Ta so that their pairwise ordering in Ta is the reverse of that in Ta' We likewise give a' the same treatment" With this, the Kendall distance between Ta and Ta is maximized and equal to IA%
Proof of Lemma 3 Let E, == {a e E: r(a) < <(()) be the set of elements Greedy considers adding to before o E when run on we have n Eu, =x n Eu. If E x or u $ or u E x' then x = x', as can be seen from how Greedy selects elements:
If o E x, then o E x' since Greedy observes before u when run on r'. Whether Greedy adds u to only depends on whether there is circuit in (x n Ey) U {u) (x' n Eu) U {u), so it makes the same decision when run on r'. Afterwards, it proceeds identically on both permutations, leading to the same outcome, so x = x'. By symmetry, the same follows from E x
If u & x, then there is a circuit in (x n Ex) U [u] (x' n E2) U (u), so u $ x'. By the same argument, Greedy makes the same decision regarding both permutations, leading to x x'. By symmetry, the same follows from 0 x'.
Assume otherwise, it is known property of bases 20 that U {u} contains a unique circuit C and that a E C. Greedy not adding a to x implies that C s (xn F.y) U (u) (x' F,) U x). Let o' be the first element after u that and x' differ at and assume w.l.og. o' E \x we have (x' n E U {u} = (x n E {n} and since o' is not added into x' before Greedy terminates, there must be another circuit in (x' n EE) U (o') U {o} containing v', which is distinct from the unique circuit C. The contradiction implies that x and x' do not differ after u, so x @ x' = =u,
We define 4. (1 e)a + cb for c [0, 1], let 0 s 0 S 0' where ni and Hhe are an adjacent swap apar and the Greedy solutions them, and x', are such that [x x'1 2. Let u, E E where x n {u, 0J = {u} and x' n ou = {o). Lemma 3 implies ni, (u) < (b) and Tip (u) > Tie (v), so Ta(4) < (u)... This means the trade-off moves from a to b, the Greedy solution minimizing the scalarized weight changes incrementally by having exactly one element shifted to the right on na (to a position not occupied by the current solution). Since at most hm hm-h(h- h 1)/2 such changes can be done sequentially, Greedy produces at most hm - h(h+ 1)/2+1 1 distinct solutions in total across all trade-offs between and b.
Proof of Theorem 2
To show this upper bound, we keep track of the following variables as the trade-off moves from to b. Since each solution contains elements, let pt be the ith leftmost position na among those occupied by the current Greedy solution for 1= n. we see that upon each change, there is at least a j E {1,...,n) n) where py increases. Furthermore, for all Pt can increase by at most m since it cannot be outside of [i, + i]. so the quantity p := Σ Pt can increase by at most n(m - n)) We see that p increases by when the change is incurred by swap in the Greedy solution such that the added element is positioned / to the right of the removed element on πa. we call this a I-move. Furthermore, each element pair participates in at most one swap, so p can be increased by at most m I /-moves for every / = 1 I..., m 1. Therefore, to upper bound the number of moves, we can assume smallest possible distance in each move, and the increase in p from using all possible I-moves for all 1 1,..., Σト j(m - j) 2 n(m - n). This means no more than Σ/ (m J) hm h(h++ 1)/2 moves can be used to increase p by at most n(m n).
Thii also done for any Ar, containing both and a'. if 0 0', we assume 2I, is closer in Kendall distance.
14

---

Proof of Lemma 4 First, we observe that a set supersets base iff its rank is n. We see that for all À E [0, and x, E {0, 1)m r(x) r(y) implies (x) < fy).. Thus, for each 2 A. MOEA/D performs (I+1)-EA search toward base's superset with fitness fi, which concludes in O(m log n) expected steps 266 The claim follows from the fact that MOEA/D produces |A] search points in each step.
Proof of Theurem 3) We assume each solution Pa supersets base for E A; this oceurs within expected time O[A[mm log n),, according Lemma 4 Since for each E A, the best improvement in fi is retained in each step, the expected number of steps MOEA/D needs to minimizes fi is at most the expected time (1+1)-EA needs to minimizes fa. We thus fix a trade-off A and assume the behaviors of (1+1)-EA. Note that we use da w(2) in the analysis instead for integral weights; scale fa and OPT, accordingly.
We call the bit flips described in Lemma good flips. Let be the current search point, if good 1-bit flips incur larger total weight reduction than good 2-bit flips on s, we call 1-step, and step otherwise. If at least half the steps from s to the MWB z are 1-steps, Lemma [ implies the optimality gap of s multiplied by at most 1/2(m n) on average after each good 1-bit flip. Therefore, from (s) & d2(m= nmxx + OPT,, the expected difference Dj after I. good 1-bit flips E[Dr]= & d2 (m n) Wmax (1 1/2(m =. At I. = [(2 In 2m n) log(2d)
n1) W) + 1)], E[D,] & 1/2 and by Markov's inequality and the fact that Dj O, Pr[D; 1] 2 1/2. Since weights are integral, Dr. < implies that z reached. The probability of making good 1-bit flip is @((m m)) so the expected number of steps before L good I-bit flips occur is O(Lm/ /m n))
O(m(log(m rt) + log Wmax + log d;)). Since I-steps take up most steps between s and z, the bound holds.
If least half the steps from s to are 2-steps, Lemma ilmmliess the optimality gap s multiplied by at most 1 - 1/2n on average after each good 2-brt flip. Repeating the argument with L = [(2 2)n log (2gg (m- wax + 1)] and the probability of making a good 2-bit flip being O(n m²), we get the bound O(m Omm2(lo(mm (m nt) + log Wmax + log d,)). Summing this over all à E A gives the total bound.
Proof of Theorem 4 From Corollary to collect new point in C, it is sufficient to perform a 2-bit flip on some supported solution. In worst-case, there can be only one trade-off 2 E A such that all non-extreme supported solutions minimize w (A), so the correct solution mutated with probability at least 1/1 in each iteration, where is the number of already collected points. Since |A] search points are generated in each iteration, the expected number of search points required to enumerate O(AAmm² |/11 !) = O(IA]IC?2²²)
15


Reviews:
[{"review_id": "0Dtt8kYwTz", "reviewer": "Reviewer_8vmn", "summary": "This paper provides a run-time analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem. It focuses on approximating the non-dominated front and shows that MOEA/D obtains a factor 2-approximation for two objectives in expected polynomial time. Empirical studies are conducted to verify the theoretical results.", "questions": "1. In the experiments, why not consider more state-of-the-art algorithms on bi-objective minimum spanning tree instances?\n2. According to the definition of dominance relation in Section 2, solutions with objectives taking the same value will dominate each other, which can cause a contradiction. How is this situation handled in the algorithm?\nIt says that “Such a set is known to guarantee a 2-approximation of the non-dominated set for k= 2”. Nevertheless, this conclusion was obtained on the multi-objective minimum spanning tree problem; does it still hold on to the more general multi-objective minimum weight base problem?", "limitations": "It is suggested to analyze the front shape of the tested problems, e.g., if problems with irregular Pareto fronts have been examined.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. A run-time analysis is presented on the MOEA/D algorithm, a classical multi-objective evolutionary algorithm that has rarely been analyzed theoretically.\n2. It is shown that MOEA/D obtains a factor 2-approximation for two objectives in expected polynomial time, compared with a pseudo-polynomial run-time of an existing method.", "weaknesses": "1. The definition of the multi-objective minimum weight base problem is unclear, e.g., the range of the decision variables and what the objectives are.\n2. The empirical study is performed by comparing with GSEMO, an algorithm published in 2007. This might be inefficient in verifying the superiority of the analyzed MOEA/D.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">In the experiments, why not consider more state-of-the-art algorithms on bi-objective minimum spanning tree instances?\n\nGSEMO is a state of the art algorithm in the theoretical analysis of evolutionary multi-objective algorithms and a wide range of rigorous runtime results have been obtained for GSEMO. For GSEMO, previous theoretical runtime results showing a pseudo-polynomial time to compute a 2-approximation have been obtained. Other popular evolutionary multi-objective algorithms such as NSGA-II, IBEA, or SPEAS2 do not provide such good approximation guarantees, or have even higher computational cost than GSEMO to achieve a 2-approximation.\nTherefore, we think that the comparison to GSEMO is valid and important and clearly show the strength of the MOEA/D approach.\n\n>According to the definition of dominance relation in Section 2, solutions with objectives taking the same value will dominate each other, which can cause a contradiction. How is this situation handled in the algorithm?\n\nWe use the classical definition of dominance in the multi-objective optimization literature. In MOEA/D, duplicate objective values are handled at line 11: the algorithm arbitrarily chooses one solution to keep, discarding the rest.\n\n>It says that “Such a set is known to guarantee a 2-approximation of the non-dominated set for k= 2”. Nevertheless, this conclusion was obtained on the multi-objective minimum spanning tree problem; does it still hold on to the more general multi-objective minimum weight base problem?\n\nYes. We proved in Theorem 1 that it gives a k-approximation for any k-objective instance. This applies to all multi-objective minimization problems, not just multi-objective minimum weight base. Note the cited 2-approximation result here also applies to all bi-objective problems, despite the original author's claim being restricted to spanning trees."}, {"review_id": "rbDa9bs4j0", "reviewer": "Reviewer_rEPr", "summary": "This paper presents the first run-time analysis of the MOEA/D for the multi-objective minimum weight base problem, e.g., multi-objective minimum spanning tree (MST). The theoretical results show the MOEA/D can find all extreme points within expected fixed-parameter polynomial time given an appropriate decomposition setting. Experiments on minimum spanning tree instances agree with the theoretical results. ", "questions": "Why do you claim “multi-objective minimum weight base problem is a significant generalization of the previously studied bi-objective minimum spanning tree problem”? Please give more disccusions.", "limitations": "No, this paper does not include the limitations. ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1/ This paper gives the first analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem.\n", "weaknesses": "1.  **Lack of novelty and originality**: Although the paper presents the first analysis of the MOEA/D algorithm for the multi-objective minimum weight base problem, it does not offer significant novelty in the context of multi-objective combinatorial optimization. Recent studies, such as the analysis of NSGA-II for similar problems, have already explored this area.\n\n2. **Insufficient innovation in analysis techniques**: The technical approach used in this paper is similar to previous work, focusing on enumerating the convex hull Conv($𝐹$) of the non-dominated front. The paper does not introduce substantial innovations or improvements to the existing techniques, which limits its contribution to the field.\n\n3. **Limited insights from the results**: The results obtained in the paper do not provide new insights or implications for algorithm design. Although the MOEA/D algorithm is shown to be faster than the GSEMO algorithm for the given problem, this alone is not enough to warrant a significant contribution to the research community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We believe we have included the answer to this question in Section 2 of our paper as it was submitted. Nevertheless, we will address it here, and try to make the paper clearer to unfamiliar readers:\n\n>Why do you claim “multi-objective minimum weight base problem is a significant generalization of the previously studied bi-objective minimum spanning tree problem”?\n\nSpanning forests in an undirected graph are equivalent to bases in a graphic matroid, whose indepedent sets correspond to edge sets of acyclic subgraphs in said graph. This fact, which we mentioned in Section 2 citing examples of matroid types, has long been known in combinatorics. Note that we cited past runtime analyses on matroid optimization in our paper (e.g. Reichel et. al., 2008), so this has also been known within the runtime analyses literature.\n\nOn the other hand, \"multi-objective\" generalizes \"bi-objective\". To our knowledge, all previous theoretical runtime analyses (including ones for NSGA-II) did not consider more than two objectives, so our findings are the first attempt at a formal generalization in this direction.\n\nFor these reasons, the problem we study subsumes bi-objective MST, the latter of which represents a tiny fraction of the former. Consequently, our results also hold for matroids not equivalent to any graphic matroid, thus strictly generalize runtime analyses on spanning trees.\n\n>The paper does not introduce substantial innovations or improvements to the existing techniques.\n\nWe analyzed the convex hull of the non-dominated front via looking at actions on permutations over the ground set, bypassing the objective space altogether and allowing easy generalization to more objectives, while leading to smaller upper bounds (e.g. Theorem 2). We have not seen existing studies on the problem (or any of its special cases for that matter) employing similar techniques."}, {"review_id": "BCfzVIqlg2", "reviewer": "Reviewer_vbRF", "summary": "The result is for the cross product of a problem class and algorithm. The problem is the multi-objective weight base problem and the algorithm is Multi-objective, evolutionary algorithm with decomposition (MOEA/D). This algorithm effectively optimizes by decomposing the objectives into single-objectives. With an appropriate decomposition, the algorithm can find all extreme points with expected fixed-parameter polynomial time.  The problem has the appropriate decomposition. Experiments agree with the theory and show the algorithm is faster than another EA called GSEMO", "questions": "Why are there no figures!?\nHow does this problem --  the multi-objective weight base problem relate to common MOO problems? What are the properties of a harder problem that we would use the algorithm for? \nHow is the first generation population of GSEMO initialized, and does this give the MOEA/D an unfair advantage?\n", "limitations": "None", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem is in the matroid optimization category and generalizes wrt a previously studied bi-objective minimum spanning tree problem.\n\nDecomposition into single-objective problems is one of two well-used approaches to Multi-objective optimization (MOO) so the MOEA/D is relevant.\n\nPrior state of art is for a different (simplified) algorithm (GSEMO) which shows a pseudo-polynomial run-time for 2 not k objectives.\nTogether with recent analyses of NSGA-II, the paper represents significant progress in developing runtime analysis of practically relevant multi-objective evolutionary algorithms.\n\nThe paper develops insight into the local structure (Hamming neighborhoods) of matroid optimization problems. This structural\ninsights will be helpful to analyse the runtime of other evolutionary algorithms on such problems.\n\nThis is the first rigorous runtime analysis of MOEA/D. The authors provide upper bounds on the expected\ntime to enumerate the convex hull of the Pareto front of the bi- and k-objective minimum weight base (MWB) problem. The assumption is that the algorithm is provided with optima for complete trade-off sets (e.g.,via the Greedy algorithm).", "weaknesses": "One problem with the paper is readability. Algorithm and problem names  are stated early as are comparisons but they are poorly described until the preliminaries.  There are a lack of clear intuitive descriptions of the problem, the algorithm (and those it is compared with) within the preliminaries. The reader has to jump across statements to figure out the analytic approach and to understand how/why it works. Granted it's challenging to describe a matroidal problem and one that is multi-objective, but the writing does not offer sufficient help with this.  The problem definition is inline on line 83 for example. \n\nThe objectives arise from the problem's matroidal properties and in a sense, the problem formulation makes it easy for each objective to be solved for extrema.  The challenge with MOEA/D in practice is the decomposition and this is neither noted nor related to the matroidal problem analyzed here.  Are there real world problems that are as ideally decomposable?  The analysis depends on a property of the problem (linear independence), the convex hull of its non-dominated front, and the ability to compute extrema for more than two objectives.\nIt is not explained why the MOEA/D is a good algorithm to use vs a dominance-based one. \nThe stochastic behavior of the MOEA/D algorithm has not been accounted for. \nIt would be helpful to additionally provide an analysis for standard multi-objective benchmark functions to allow for a comparison with analyses of other MOEAs.  \nThe description of the experimental setting lacks detail.\n\n\n\n\n\n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the broader perspective on our work and would like to address the concerns from a high-level view:\n\n>How does the multi-objective weight base problem relate to common MOO problems?\n\nThe problem is a generalization of the well-known classical minimum weight base problem. We believe this alone makes the problem worth studying.\n\n>What are the properties of a harder problem that we would use the algorithm for?\n\nOn a basic level, the algorithm is suitable for problems whose objectives are decomposable. Furthermore, the decomposition scheme based on linear scalarization is effective on any problem where the non-dominated front is close to being convex. More generally, however, wider application of MOEA/D is beyond the scope of this work, and we would refer to other works on MOEA/D. \n\nNote that we do not claim MOEA/D is the best algorithm for this problem or any related problem. Here, we study the base variant of MOEA/D, which is not tailored to any specific problem. On the other hand, establishing connections between the multi-objective weight base problem and harder problems is an interesting topic in its own right.\n\n>How is the first generation population of GSEMO initialized, and does this give the MOEA/D an unfair advantage?\n\nGSEMO starts with a single solution drawn uniformly at random from the set of all bit-strings. We do not see any unfair advantage from this, as MOEA/D also starts with uniformly random bit-string solutions."}, {"review_id": "gWJvULtxMF", "reviewer": "Reviewer_EzWR", "summary": "This paper presents a comprehensive theoretical and empirical analysis of the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) for the Multi-Objective Minimum Weight Base problem. The authors provide a detailed explanation of the algorithm, including its fitness functions and decomposition scheme. They also propose a series of algorithms for finding extreme points and a complete trade-off set. The paper includes a rigorous theoretical analysis, providing expected time bounds for the algorithm to minimize scalarized weights and enumerate the convex hull of the feasible region. The authors also conduct an experimental investigation on various bi-objective minimum spanning tree instances, comparing the performance of MOEA/D against GSEMO. The results demonstrate that MOEA/D significantly outperforms GSEMO in computing extreme points under an appropriate decomposition.", "questions": "1.     How would the theory guides the application of MOEA/D?\n2.\tCould the authors elaborate on the rationale behind the assumption that distinct supported solutions have distinct images under the weight function.? Are there any scenarios where this assumption might not hold, and if so, how would this affect the results?\n3.\tCould the authors provide more insights into how these parameters should be selected?\n", "limitations": "Societal impact of the work is not discussed in this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe paper provides a thorough theoretical analysis of the MOEA/D algorithm, including expected time bounds for key operations, which contributes to the understanding of the algorithm's performance and efficiency.\n2.\tThe authors apply their theoretical findings to a real-world problem demonstrating the practical relevance of their research.\n3.\tThe paper includes a comparative analysis of MOEA/D and GSEMO, and provides valuable insights into the strengths and weaknesses of these algorithms.\n4.\tThe authors provide a detailed explanation that helps understand the MOEA/D algorithm.\n", "weaknesses": "1.\tThe paper makes several assumptions, such as distinct supported solutions having distinct images under the weight function, which might not be applicable in all scenarios. How would the theory guides the application of MOEA/D?\n2.\tThe paper does not provide a detailed discussion on how to choose the parameters for the MOEA/D algorithm. \n3.     This paper may only be interested by the evolutionary computation community. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to address the in-depth questions here, and try to work the dicussions into our revision to improve the paper:\n\n>How would the theory guides the application of MOEA/D?\n\nOur analysis of the multi-objective min weight base problem gives guidance on how to choose scalarization weights for MOEA/D for the problem. We have demonstrated this to some degree in the experiments.\n\n>Could the authors elaborate on the rationale behind the assumption that distinct supported solutions have distinct images under the weight function.? Are there any scenarios where this assumption might not hold, and if so, how would this affect the results?\n\nDuplicate images among points on the convex hull only occur if there are at least two ground set elements having the same weight across all weight functions, i.e., at least two columns in the weight matrix w that are identical (this is a consequence of the fact that Greedy can compute all min weight bases). We elaborated in Section 3 that the existence of such elements does not affect the results since these are not concerned with enumerating all solutions, only those whose images are distinct, i.e., enumerating points in the objective space. To be specific, such elements might spawn additional min weight bases for some scalarized weight, whose pairwise xor are contained within these elements (thus sharing images). By fixing the relative ordering among these elements on the sorting permutations, such differences effectively vanish, i.e., these additional bases disappear. Since fixing these orderings is always valid for all scalarized weights, we can assume such elements do not exist.\n\nWe further note that there can be multiple such \"classes\" of elements (elements in the same class share weights while those in different classes do not). The presence of multiple such classes does not affect things either, because swapping the relative ordering between two classes on a permutation can always be done via a sequence of adjacent swaps, all while preserving elements' ordering within each class at every step (thus fixing orderings as mentioned). This process can be generalized to more than two classes using only adjacent swaps, e.g., by swapping one pair of classes at a time. All this means, again, that we can w.l.o.g. fix the orderings among same-weight elements.\n\nRegarding the additional min weight bases we mentioned, the permutations that lead to Greedy producing these bases only differ in the orderings among same-weight elements. As we mentioned in Section 3, we can always transform one into the other via a adjacent swap sequence such that every intermediate step returns a sorting permutation. As such, even in the presence of such elements, the set of convex hull solutions is still 2-Hamming connected as a consequence of our Lemma 3 (hence Corollary 2).\n\n>Could the authors provide more insights into how these parameters should be selected?\n\nWe can only comment on the task of finding points on the convex hull of the PF. For the scalarization trade-offs, we note that it is optimal to have exactly one trade-off per extreme point (if we only care about extreme points), as this would not incur redundant function evaluations (aside from those arising from randomization). We included a discussion on how to find these trade-offs in Section 5, e.g., processing the output of the schemes in Section 4. If we want to find all convex hull points rather than just extreme points, we need not process this output, and each trade-off would be normal to a distinct facet of the convex hull.\n\nAs for the neighborhood size, we remark that greater collaborations among solutions help reduce the number of iterations needed, at the cost of making each iteration more costly, e.g., from more comparisons. We do not have a meaningful theoretical result on the impact of this parameter on MOEA/D's runtime."}, {"review_id": "0ZDNoqI80k", "reviewer": "Reviewer_RGyY", "summary": "This paper studies the \"multi-objective minimum weight base\" problem in the MOEA/D framework and proposed several useful properties. \n\n", "questions": "1. This paper mainly considers the weighted sum scalarization. It is known that this method can only recover the convex part of a PF. Will the proposed method find the whole Pareto solution?\n\n2. When the objectives are all non-convex. It is impossible to use the supportive set to approximate the whole PS. So is there any assumption for your supportive set?\n\n3. Line 102, a support set is extreme if ..... This statement is not clear. \n\n4. line 250, ontrade off -> on trade off? ", "limitations": "NO. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives the running time analysis for a special kind of MOEAD problem. This is an important contribution for the MOO field since MOEAD is a very basic idea. \nThe strength of this paper is that, the studied algorithm is very meaningful since it take cooperation into consideration. (Line 8-9 in Algorithm 3). \n \n\n", "weaknesses": "1. This paper take multi-objective minimum weight base problems as an example. This is not general however. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the suggestions which help us revise our work. Below, we address the questions raised:\n\n>This paper mainly considers the weighted sum scalarization. It is known that this method can only recover the convex part of a PF. Will the proposed method find the whole Pareto solution?\n\nMOEA/D can achieve this with elitism and randomization, i.e., there is always a non-zero chance of generating a non-dominated solution every time mutation operation occurs, and this solution is kept in the returned set S. However, we do not yet have sufficient insight into the underlying structures of the PF to determine how many iterations it would need.\n\n>When the objectives are all non-convex. It is impossible to use the supportive set to approximate the whole PS. So is there any assumption for your supportive set?\n\nOur Theorem 1 asserts the extreme points on the convex hull are sufficient for approximating all solutions, including the entire PF (within a factor equal the number of objectives k). This holds for all non-negative multi-objective minimization problems (i.e. no other assumption needed), and under the definition of approximation we considered. To our knowledge, this is the only published formal notion of approximation ratio in multi-objective optimization. Additive error notions like epsilon-dominance are not conducive to meaningful worst-case analyses without strong assumptions on the objectives.\n\n>Line 102, a support set is extreme if ..... This statement is not clear.\n\nFirstly, the statement implies a supported solution can be an extreme solution. Secondly, we regard operators argmin and argmax to return a set rather than an element to account for multiple minima and maxima, respectively. Finally, we use f(z)=f(x) literally: all objective values are equal. This statement excludes any solution whose image is in the interior of some facet of the convex hull, as there are always vertices on the same facet distinct from said image. Note these vertices are images of solutions minimizing the weight that is scalarized by the trade-off normal to this facet, so the condition is violated."}]

Author rebuttal:
We thank the reviewers for their reviews and comments. We address the specific comments and questions raised by each reviewer in individual responses.

We see some confusion regarding approximating the non-dominated front, specifically our Theorem 1. We have prefaced the theorem by stating that the result is not restricted to multi-objective minimum weight base, and we have minimized the assumptions used in the theorem itself to emphasize this. Nevertheless, we will try to clarify it further in our revision.

Meta-review: The paper provides a thorough theoretical analysis of MOEA/D and applies it to Multi-Objective Minimum Weight Base problem. The reviewers generally agree that the paper is technically solid, though some have raised concerns about the assumptions made in the paper and the limitations of the approach. The authors have provided rebuttals to address most of the concerns, meanwhile there are still concerns that are not fully addressed, including the similarity between the studied problem and the previously studied minimum spanning tree problem.
Decision: Accept (poster)