An Adjacency-Based Algorithm for Computing Extreme-Supported Efficient Spanning Trees

An adjacency-based algorithm for computing extreme-supported efficient spanning trees Oliver Bachtler joint work with Felix Fritz and Stefan Ruzika RPTU Kaiserslauten-Landau International Conference on Operations Research 2025 MIM funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - GRK 2982, 516090167 Mathematics of Interdisciplinary Multiobjective Optimization Outline Basics & Motivation Multi-objective optimisation Adjacency A Generic Adjacency-Based Algorithm For global adjacency For a restricted neighbourhood Application to Spanning Trees Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 1 / 14 Multi-objective optimisation Definition Abi-objective combinatorial optimisation problem Πis of the following form: min f(x)=(f1(x),f2(x))T s.t.x∈X where f1,f2:X→Rare the objective functions and Xis finite. We set Y:=f(X). Definition For λ∈(0,1), the weighted sum scalarisation ΠWS(λ)is min λf1(x)+(1−λ)f2(x) s.t.x∈X. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 2 / 14 Multi-objective optimisation Definition Abi-objective combinatorial optimisation problem Πis of the following form: min f(x)=(f1(x),f2(x))T s.t.x∈X where f1,f2:X→Rare the objective functions and Xis finite. We set Y:=f(X). Definition For λ∈(0,1), the weighted sum scalarisation ΠWS(λ)is min λf1(x)+(1−λ)f2(x) s.t.x∈X. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 2 / 14 A bi-objective minimum spanning tree problem − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 3 / 14 A bi-objective minimum spanning tree problem − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 3 / 14 A bi-objective minimum spanning tree problem − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 3 / 14 A bi-objective minimum spanning tree problem − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 3 / 14 A bi-objective minimum spanning tree problem − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 3 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=1 2 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=1 2 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=1 2 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=1 2 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=4 5 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=2 3 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 λ=2 3 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Supported solutions Definition ▶Xλis the set of optimal solutions of ΠWS(λ). ▶x∈Xλ, for λ∈(0,1), is supported efficient. ▶XSE is the set of supported efficient solutions. ▶YSN :=f(XSE )is the set of supported non-dominated points. ▶The extreme points of conv(Y) + R≥and their preimages are extreme supported. ▶The corresponding sets are YESN and XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 4 / 14 Adjacency for feasible solutions Definition Two spanning trees T,T′of a graph Gare adjacent if they differ in exactly one edge. Adjacency in the literature ▶adjacent basic solutions (parametric simplex) ▶matroid bases differing in one element ▶flows differing by a cycle T1 T2 T3 T4 T7 T5 T8 T6 T9 − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 5 / 14 Adjacency for feasible solutions Definition Two spanning trees T,T′of a graph Gare adjacent if they differ in exactly one edge. Adjacency in the literature ▶adjacent basic solutions (parametric simplex) ▶matroid bases differing in one element ▶flows differing by a cycle T1 T2 T3 T4 T7 T5 T8 T6 T9 − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 5 / 14 Adjacency for feasible solutions Definition Two spanning trees T,T′of a graph Gare adjacent if they differ in exactly one edge. Adjacency in the literature ▶adjacent basic solutions (parametric simplex) ▶matroid bases differing in one element ▶flows differing by a cycle T1 T2 T3 T4 T7 T5 T8 T6 T9 − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 5 / 14 Adjacency for feasible solutions Definition Two spanning trees T,T′of a graph Gare adjacent if they differ in exactly one edge. Adjacency in the literature ▶adjacent basic solutions (parametric simplex) ▶matroid bases differing in one element ▶flows differing by a cycle T1 T2 T3 T4 T7 T5 T8 T6 T9 − 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 5 / 14 Outline Basics & Motivation Multi-objective optimisation Adjacency A Generic Adjacency-Based Algorithm For global adjacency For a restricted neighbourhood Application to Spanning Trees Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 6 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 λ=0 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 λ=1 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 λ=8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 λ=10 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 Extremely-supportive algorithms Goal: Compute YESN. Why? Because YESN . . . ▶is a good representation of YN. ▶is a 2-approximation. ▶contains a solution to ΠWS(λ)for all λ. Definition An algorithm is extemely-supportive if it computes a set S⊆XESE such that f(S) = YESN . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 7 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE . 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 A generic extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Note: By choosing a solution ‘maximally to the left’ in Step 4, we never need to leave XESE .246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 8 / 14 An adjacency-based extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 An adjacency-based extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 An adjacency-based extremely-supportive algorithm Generic algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 An adjacency-based extremely-supportive algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 An adjacency-based extremely-supportive algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. X1 3 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 An adjacency-based extremely-supportive algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Problem: Checking lots of points each time. Solution? Use adjacency and only check neighbouring solutions. Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. X1 3 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 9 / 14 Outline Basics & Motivation Multi-objective optimisation Adjacency A Generic Adjacency-Based Algorithm For global adjacency For a restricted neighbourhood Application to Spanning Trees Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 10 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). Theorem The adjacency-based algorithm is correct if, for all λ∈(0,1)and all x∈Xλ, ▶X<(x)∩Xλ=∅or ▶X<(x)∩Xλcontains a neighbour of x. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). e Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). e e Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Verifying the correctness criterion Theorem Let Gbe a graph and Ta spanning tree such that T∈Xλfor some λ∈(0,1). Then ▶X<(T)∩Xλ=∅or ▶X<(T)∩Xλcontains a neighbour of T. Proof. ▶Let T∈Xλand T′∈X<(T)∩Xλ. ▶Let e∈T\T′and e′∈T′\Tsuch that T−e+e′and T′−e′+eare spanning trees. ▶cλ(e) = cλ(e′). ▶c1(e)>c1(e′)⇒T−e+e′∈X<(T). ▶c1(e)≤c1(e′)⇒T′−e′+e∈X<(T). e e e′ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 11 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in O(I·nm) time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in O(I·nm) time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in O(I·nm) time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in O(I·nm) time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in OI·n2m time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in OI·n2m time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Implementing the algorithm Generic adjacency-based algorithm 1. Start with a lexicographically optimal solution with respect to (f2,f1). 2. Determine the slopes to solutions whose images are ‘to the left’ and that are adjacent. 3. If no such solutions exist, terminate. 4. Transition to a solution with maximal slope. 5. Go to Step 2. Theorem The algorithm can be implemented in O(I·nm) time, where Iis the number of iterations. Implementation 1. Run Kruskal’s algorithm on the lexicographic ordering. 2. Try all possible exchanges of e∈T with e′/∈Tsuch that c1(e)>c1(e′). If it yields a tree, compute the slope. 3. Check if any solution is found. 4. Determine the maximum slope. A small tweak In Step 2, find the cycle in T+e′and swap e′with the edges eon the cycle. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 12 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′). ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′). ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′). ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P. ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if λ≤λ(f,f′) ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ(e,e′) f λ(e,f)λ(f,e′) λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P. ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if λ≤λ(f,f′) ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ(e,e′) f λ(e,f)λ(f,e′) λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P. ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if λ≤λ(f,f′) ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ(e,e′) f λ(e,f)λ(f,e′) λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P. ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if λ≤λ(f,f′) ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ(e,e′) f λ(e,f)λ(f,e′) λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Bounding the number of iterations Theorem The algorithm terminates after Om2iterations. Proof. ▶T→T−e+e′ ▶c1(e)>c1(e′),cλ(e) = cλ(e′)⇝P. ▶|P| ∈ O m2 ▶(f,f′)∈ P feasible if ▶λ<λ(f,f′)or ▶λ=λ(f,f′),f∈T, and f′/∈T. ▶After the transition to T−e+e′there are fewer feasible pairs. 0.2 0.4 0.6 0.8 1 1 2 3 4 e e′ λ(e,e′) f λ(e,f)λ(f,e′) λ cλ Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 13 / 14 Summary We saw how to . . . ▶compute YESN in an adjacency-based fashion. ▶apply the generic algorithm to spanning trees. ▶bound the number of iterations. Future work ▶Apply the algorithm to other combinatorial problems with adjacency concepts. ▶Prove sufficient conditions to obtain connectivity of XSE in general. ▶p>2? Contact: [email protected] 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 14 / 14 Summary We saw how to . . . ▶compute YESN in an adjacency-based fashion. ▶apply the generic algorithm to spanning trees. ▶bound the number of iterations. Future work ▶Apply the algorithm to other combinatorial problems with adjacency concepts. ▶Prove sufficient conditions to obtain connectivity of XSE in general. ▶p>2? Contact: [email protected] 246 2 4 6 8 10 Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 14 / 14 References I Fritz Bökler and Petra Mutzel. Tree-Deletion Pruning in Label-Correcting Algorithms for the Multiobjective Shortest Path Problem, pages 190–203. Springer International Publishing, 2017. Cristina Bazgan, Stefan Ruzika, Clemens Thielen, and Daniel Vanderpooten. The power of the weighted sum scalarization for approximating multiobjective optimization problems. Theory of Computing Systems, 66(1):395–415, November 2021. Matthias Ehrgott. On matroids with multiple objectives. Optimization, 38(1):73–84, January 1996. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 1 / 2 References II Matthias Ehrgott. Multicriteria Optimization. Number 491 in Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, second edition, 2005. David Könen and Michael Stiglmayr. An output-polynomial time algorithm to determine all supported efficient solutions for multi-objective integer network flow problems. Discrete Applied Mathematics, 376:1–14, December 2025. Serpil Sayın. Supported nondominated points as a representation of the nondominated set: An empirical analysis. Journal of Multi-Criteria Decision Analysis, 31(1–2), January 2024. Oliver Bachtler An adjacency-based algorithm for computing extreme-supported efficient spanning trees OR 2025 2 / 2