Multi-Objective Optimization

Pareto Frontiers & Trade-off Analysis

Optimization problems with multiple conflicting objectives where no single solution is optimal for all criteria simultaneously. These methods compute Pareto-optimal solution sets, enabling decision-makers to visualize and navigate trade-offs between competing objectives.

Problems

Tests

Algorithms

View on GitHub

Problem Collection

Three multi-objective formulations of classic OR problems

Bi-Objective Knapsack

2 Algorithms — 12 Tests

The 0-1 knapsack problem extended with two value functions to optimize simultaneously. Each item has a weight and two distinct values. The goal is to find the complete Pareto front of non-dominated solutions, revealing the trade-off between the two objectives under the capacity constraint.

max (v1^T x, v2^T x)
s.t. w^T x ≤ W
x ∈ {0, 1}^n

Goal: Find all Pareto-optimal solutions.

Algorithm	Type	Complexity	Reference
Epsilon-Constraint	Exact	O(K · nW)	Haimes et al. (1971); sub-problems solved via DP
NSGA-II	Metaheuristic	O(M · N²) / gen	Deb et al. (2002); non-dominated sorting + crowding distance

Portfolio Optimization Resource Allocation Sustainability

View Source Code

Multi-Objective TSP

2 Algorithms — 11 Tests

The Traveling Salesman Problem with multiple distance/cost matrices representing different objectives (e.g., travel time, fuel cost, road quality). Generates approximate Pareto fronts by solving weighted combinations of objectives using the nearest neighbor heuristic across varied weight vectors.

min (f₁(π), f₂(π), …, f_K(π)) where f_k(π) = ∑ d^k_{π(i),π(i+1)}
s.t. π is a Hamiltonian cycle, π(n+1) = π(1)
Scalarize: min ∑_k w_k · f_k(π), w_k ≥ 0, ∑ w_k = 1

Algorithm	Type	Complexity	Reference
Weighted Sum NN	Heuristic	O(W · n²)	NN on scalarized distance matrix per weight vector
NSGA-II	Metaheuristic	O(M · N²) / gen	Deb et al. (2002); OX crossover + swap mutation for tours

Logistics Route Planning Network Design

View Source Code

Multi-Objective Shortest Path

2 Algorithms — 12 Tests

Given a directed graph where each edge carries a vector of costs (e.g., travel time and monetary cost), find all Pareto-optimal paths from source to target. The number of Pareto-optimal paths can be exponential in the worst case, making this problem NP-hard in general.

min (c₁(P), c₂(P), …, c_K(P)) where c_k(P) = ∑_(i,j)∈P c^k_ij
s.t. P is an s–t path in G = (V, E)

Algorithm	Type	Complexity	Reference
Label-Setting	Exact	O(\|P\| · E · log(\|P\| · V))	Martins (1984); multi-objective Dijkstra with dominance pruning
NSGA-II	Metaheuristic	O(M · N²) / gen	Deb et al. (2002); path-based encoding for graph problems

Transportation Telecommunications Emergency Routing

View Source Code

Key Concepts

Foundational ideas in multi-objective optimization

Pareto Optimality

A solution is Pareto-optimal if no objective can be improved without worsening another. The set of all such solutions forms the Pareto front, representing the fundamental trade-off surface.

Dominance

Solution A dominates B if A is at least as good in all objectives and strictly better in at least one. Non-dominated solutions constitute the Pareto set.

Epsilon-Constraint

Converts a multi-objective problem to a series of single-objective problems by optimizing one objective while constraining others. When sub-problems are solved exactly, guaranteed to find both supported and unsupported Pareto-optimal points.

Weighted Sum

Scalarizes multiple objectives into one via convex combination. Simple and efficient but can only find solutions on the convex hull of the Pareto front (supported solutions).

Trade-off Analysis

The Pareto front reveals the marginal rate of substitution between objectives, enabling informed decision-making about acceptable compromises in real-world applications.

Solution Quality

Measured by hypervolume indicator (Zitzler & Thiele, 1999), spacing, and coverage metrics. A good approximation set should be close to the true front, well-spread, and cover the full extent of trade-offs.

Ideal & Nadir Points

The ideal point z* has each objective at its individual optimum; the nadir point z^nad has each at its worst among Pareto-optimal solutions. Together they bound the Pareto front and enable objective normalization before applying scalarization methods.

Evolutionary MOO

Population-based algorithms (NSGA-II, MOEA/D, SPEA2) evolve a set of solutions simultaneously, using non-dominated sorting and diversity preservation to approximate the entire Pareto front in a single run.

Method Comparison

Scalarization and evolutionary approaches at a glance

Aspect	Epsilon-Constraint	Weighted Sum	Evolutionary (NSGA-II)
Approach	Constrain secondary objectives	Linear combination of objectives	Population-based Pareto search
Pareto Coverage	Supported + unsupported points	Supported points only (convex hull)	Approximates full front
Sub-problem Type	Constrained single-objective	Original constraints only (no objective bounds)	Direct multi-objective
Best For	Exact discrete fronts, unsupported points	Quick supported-solution sweeps	Large complex spaces, many objectives
Key Reference	Haimes et al. (1971)	Zadeh (1963)	Deb et al. (2002)

Benchmarks & References

Standard test suites and foundational literature

Discrete MOO Benchmarks

Benchmark	Problem	Details
Bazgan et al.	Bi-Obj Knapsack	Instances with 50–500 items, correlated/uncorrelated
Lust & Teghem	Bi-Obj TSP	TSPLIB-derived, 100–300 cities, 2 distance matrices
Hansen (1980)	Bi-Obj SP	Grid/random graphs, 2 edge-cost vectors

Key References

Reference	Contribution
Deb et al. (2002)	NSGA-II: non-dominated sorting + crowding distance
Haimes et al. (1971)	Epsilon-constraint method for multi-objective programming
Ehrgott (2005)	Textbook: Multicriteria Optimization, Springer
Zitzler & Thiele (1999)	Hypervolume indicator & SPEA evolutionary algorithm
Zhang & Li (2007)	MOEA/D: decomposition-based evolutionary algorithm
Mavrotas (2009)	AUGMECON: effective epsilon-constraint implementation

Why Weighted Sum Misses Points

Visualizing supported vs. unsupported Pareto-optimal solutions

The weighted sum method optimizes w₁f₁ + w₂f₂, which geometrically corresponds to moving a line with slope −w₁/w₂ until it touches the feasible region. On a non-convex Pareto front, some solutions lie in "dents" that no tangent line can reach — these are unsupported points. Only epsilon-constraint or evolutionary methods can find them.

▮ Supported (found by weighted sum) ▮ Unsupported (missed by weighted sum, found by ε-constraint)

Try It Yourself

Interactive solvers with Pareto front visualization

Bi-Objective Knapsack Solver

Select items that maximize two conflicting objectives: Profit and Sustainability, subject to a weight capacity constraint. The solver enumerates all 2⁶ = 64 candidate subsets, filters for feasibility under the capacity constraint, and identifies the Pareto front.

Item	Profit	Sustainability	Weight
Solar Panel	120	90	25
Generator	200	30	35
Battery Pack	80	85	15
LED System	60	95	10
AC Unit	150	20	30
Insulation	40	80	8

Capacity

Epsilon-Constraint

Weighted Sum

Multi-Objective TSP Solver

Find tours that balance two conflicting objectives: Distance (travel cost) and Risk (road danger). The solver uses weighted-sum nearest neighbor across 11 weight vectors to trace the Pareto front. Click a point on the front to visualize that tour on the map.

City	X	Y

Cities

Seed

Tour Map — click a Pareto point to visualize

Pareto Front — Distance vs. Risk