Source-linked AI summary
Parallelizable Gradient-Based Optimization For Multi-Objective MaxCut
Jingjuan Huang, Alvaro Velasquez, Jia Liu, Ismail Alkhouri
TL;DR
The paper addresses the difficulty of scalable multi-objective MaxCut, where objectives and trade-offs are computationally hard. It proposes MO-QUCO, which combines adjacency-based quadratic optimization with linear scalarization and preference-conditioned PGA analysis. Across varied graphs and settings, the CPU and GPU variants outperform state-of-the-art exact, heuristic, and quantum methods in the reported evaluations.
Problem
Multi-objective MaxCut requires optimizing conflicting NP-hard objectives while handling exponentially many cuts and trade-off relations.
Method
MO-QUCO combines an adjacency-based quadratic MaxCut formulation with linear scalarization and gradient-based optimization over a continuous relaxation.
Results
MO-QUCO and pMO-QUCO outperform state-of-the-art exact, heuristic, and quantum methods across different objective counts, graph sizes, and conflicting-objective instances.
Takeaways & Limitations
Preference-conditioned fixed-point analysis connects the differentiable optimization procedure to Pareto properties, while batching makes the approach GPU-parallelizable.
Takeaways & Limitations
Unlike exact weighted-sum optimization, the method does not solve each scalarized problem to global optimality and can generate candidates beyond supported cuts.
Abstract
from arXiv · showhide
Multi-objective combinatorial optimization arises in a wide range of problems and applications, including the canonical multi-objective MaxCut problem. Differentiable single-instance quadratic methods have recently achieved remarkable performance in single-objective combinatorial optimization. In this paper, we develop a differentiable framework for multi-objective MaxCut by combining an adjacency-based quadratic formulation with linear scalarization, thereby reducing the problem to a preference-conditioned single-objective signed-weight MaxCut problem. Theoretically, we characterize the stationary points of the resulting signed-weight formulation and show how they induce preference-conditioned fixed points on the Pareto front. Computationally, unlike conventional heuristics and branch-and-bound methods, our approach is GPU-parallelizable and can therefore benefit from substantial performance speedups. We term our algorithm Multi-objective QUadratic Combinatorial Optimization (MO-QUCO) and its parallelized variant pMO-QUCO. Empirically, across different multi-layered (and weight distributions) graphs, we show that both our CPU-only and GPU-based algorithms outperform SOTA exact and heuristic methods in terms of wall-clock runtime and objective quality. Despite operating under different computational settings, MO-QUCO also outperforms the SOTA quantum method.
1. Introduction
Multi-objective MaxCut combines NP-hard optimization with exponentially many trade-offs, motivating MO-QUCO, a differentiable scalarized solver with GPU-parallelizable search. The proposed methods are reported to outperform exact, heuristic, and quantum approaches across broad evaluations.
- Motivation: Multi-objective combinatorial optimization balances conflicting criteria, making it at least as hard as single-objective combinatorial optimization.The paper illustrates this with delivery routing that trades travel cost against workload balance.
- Problem setting: MO-MaxCut seeks Pareto-efficient cuts for shared-node graphs whose edges carry multiple weight sets.The paper adopts a hardware-native benchmark previously used for quantum sampling.
- Challenges: Two challenges are NP-hard objectives with exponentially many cuts and exponentially growing trade-off relations as objectives increase.These difficulties limit classical methods to heuristics or approximations with sub-optimality-gap guarantees.
- Approach: MO-QUCO combines the adjacency formulation of MaxCut with linear scalarization, enabling gradient-based optimization over a continuous relaxation.This converts preference-conditioned multi-objective optimization into a differentiable scalarized problem.
- Theory: The theory characterizes PGA fixed points under signed edge weights and connects preference-conditioned fixed points with Pareto properties.For a fixed preference vector, binary fixed points are cuts where no 1-bit flip improves the scalarized objective.
- Evaluation: MO-QUCO and pMO-QUCO outperform state-of-the-art exact, heuristic, and quantum methods across varied objective counts and graph sizes.The algorithms simultaneously use batched preference vectors and random initializations, accumulating nondominated cuts in a Pareto archive.
2. Preliminaries
The preliminaries encode cuts as binary or spin vectors, represent signed-weight MaxCut quadratically, and define multi-objective evaluation through Pareto dominance. Exact Pareto-front computation is NP-hard, so experiments assess finite archives as approximations.
- Notation: A weighted undirected graph is represented by vertices, edges, and a symmetric weight matrix that may contain negative edge weights.The notation uses n for nodes and m for edges.
- Cut representation: A cut partitions the vertices and is encoded by z ∈ {0, 1}^n, with an edge cut when its endpoints receive different binary values.The indicator of separation equals (z_u − z_v)^2.
- Single-objective formulation: Signed-weight SO-MaxCut maximizes the cut value over binary vectors even when edge weights are positive or negative.The same cut can equivalently be represented by a spin vector s = 2z − e_n.
- Multi-objective formulation: In the multi-objective setting, each cut receives a vector of K objective values from shared-edge weighted graphs.The objectives are denoted f_1(z), ..., f_K(z).
- Pareto concepts: A cut is Pareto-optimal when no other cut dominates it across all objectives, and the Pareto front is the image of all Pareto-optimal cuts.Dominance requires weakly better values for every objective and a different objective vector.
- Problem definition: MO-MaxCut asks for Pareto-optimal cuts whose objective-space image covers the entire Pareto front.Because exact computation is NP-hard even for K = 1, practical solvers retain finite archives of mutually nondominated cuts.
- Practical approximation: Archive images approximate the Pareto front, and the experiments quantify their approximation quality.This makes archive quality an explicit evaluation target rather than assuming exact front coverage.
3. A Differentiable Approach For MO-MaxCut
The paper reduces multi-objective MaxCut to preference-conditioned signed-weight single-objective problems and optimizes their continuous relaxations with projected gradient ascent. It characterizes the resulting fixed points and explains how batching, preference sampling, and refinement expand Pareto-cut discovery.
- Scalarized formulation: Linear scalarization aggregates the objective layers into a signed-weight graph, whose cut objective equals the scalarized multi-objective objective.The aggregated graph can retain negative edge weights, so the reduced problem remains signed-weight MaxCut.
- Continuous optimization: The method relaxes binary cuts to x ∈ [−1, 1]^n and applies projected gradient ascent to quadratic MaxCut formulations, especially the adjacency formulation.The adjacency, perturbed Laplacian, and perturbed biased formulations are defined on the aggregated graph.
- Signed-weight fixed points: Under signed weights, Laplacian PGA fixed points are characterized by nonnegative total signed weight on every cut edge incident to each vertex.Negative crossing edges can make this condition fail, moving a binary point toward the box interior; signed weights also mean the Laplacian need not be positive semidefinite or convex.
- Adjacency fixed points: For the adjacency formulation, a binary cut is a PGA fixed point exactly when no 1-bit flip improves its scalarized objective.This extends the fixed-point analysis from unweighted graphs to arbitrary signed edge weights and motivates the adjacency formulation.
- Preference-conditioned discovery: Supported cuts are Pareto-optimal, while approximate PGA can generate candidates beyond supported cuts and refinement can explore their 1-bit-flip neighbors.Preference sampling gives a cut with preference-region fraction p_s probability 1 − (1 − p_s)^J of being encountered by at least one of J sampled preferences.
4. Experimental Results
MO-QUCO and pMO-QUCO achieve near-optimal hypervolume rapidly and outperform exact, heuristic, and quantum baselines in runtime and objective quality across benchmark instances.
- Benchmark and metrics: The benchmark evaluates K = 3 and K = 4 objective instances on a shared 42-node, 46-edge graph with normally distributed layer weights.
- Benchmark and metrics: The study compares exact integer-programming solvers, randomized heuristics, weighted-sum optimization, and QAOA using nondominated-point counts and hypervolume.For fixed reference points, larger hypervolume indicates dominance over a larger objective-space region.
- Main results: 118.0 versus 117.7 s: MO-QUCO runtime is independent of objective count while reaching 99.9999% and 99.9954% of HVmax for K = 3 and K = 4.pMO-QUCO requires 0.9 s on both instances and reaches 99.9999% and 99.9963% of HVmax, while refinement reaches 100% on both.
- Main results: 57× and 101×: CPU and GPU methods are faster than DPA-a on K = 4, while also outperforming randomized heuristics and the quantum baseline.The reported QAOA timing is an idealized hardware sampling estimate that excludes circuit compilation.
- Anytime convergence: 99% of HVmax arrives within 0.3 s for K = 3 and 1.4 s for K = 4, with MO-QUCO ahead of all baselines from 0.1 s onward.pMO-QUCO exceeds 99.99% of HVmax in about 0.9 s on both instances.
- Archive diversity and ablations: Approximate scalarized optimization and bit-flip refinement generate candidates beyond exact WSM’s supported solutions, while ablations identify PGA and refinement as important components.Sensitivity analysis links more sampled points to better solution quality and requires balancing PGA steps and step size against archive diversity.
5. Conclusions
The paper presents a differentiable scalarization-based approach for multi-objective MaxCut and characterizes its preference-conditioned fixed points. Experiments report state-of-the-art performance against exact and heuristic methods across varied settings.
- Contributions: Linear scalarization converts multi-objective MaxCut into a single-objective signed-weight MaxCut problem suitable for gradient-based optimization.
- Theory: For fixed preferences, the analysis characterizes adjacency-based optimization fixed points and connects preference regions for binary solutions to Pareto properties.
- Experiments: Across objective counts, graph sizes, and conflicting-objective instances, the algorithms achieve state-of-the-art performance against exact and heuristic methods.
A.1. Proof of Lemma 1
The proof derives coordinate-wise conditions for projected gradient ascent fixed points and then shows that binary fixed points correspond exactly to cuts with no improving one-bit flip.
- Coordinate-wise fixed points: Projection onto [−1, 1]n acts coordinate-wise, so a vector is fixed precisely when every coordinate remains unchanged.
- Coordinate-wise fixed points: A zero coordinate update leaves any coordinate unchanged, whereas a positive or negative update preserves a fixed point only at the matching boundary, 1 or −1.
- Binary characterization: For a binary cut, the coordinate condition is equivalent to Cv(s) ≥0 for every vertex, excluding stationary points under the stated assumption.
- One-bit flips: Flipping one vertex changes only incident edges, and the resulting objective change identity holds without restrictions on edge-weight signs.
- One-bit flips: The projected update leaves a binary coordinate unchanged exactly when its one-bit flip change satisfies ∆v(s) ≤0.
A.4. Proof of Lemma 2
The proof establishes that supported cuts are Pareto-optimal and that three conditions equivalently characterize preference vectors making a cut an adjacency-based PGA fixed point.
- Supported cuts: A supported cut cannot be dominated because a dominating cut would strictly improve at least one objective while preserving the scalarized optimum.
- Preference-conditioned fixed points: The equivalence proof links adjacency fixed-point condition (i), the inequalities λ⊤γv(s) ≤0 for all vertices, and membership in ΛA(s).
A.6. Proof of Proposition 1
The proof establishes how the GPU-parallelizable implementation processes preferences and batches through projected-gradient updates, binarization, nondominance filtering, and optional refinement.
- A.6. Proof of Proposition 1: pMO-QUCO is the GPU-parallelizable implementation of the proposed method.
- A.6. Proof of Proposition 1: The algorithm samples preferences, partitions them into blocks, and initializes batched continuous points for each block.
- A.6. Proof of Proposition 1: Projected updates run on the GPU, after which points are binarized and accumulated into the candidate set.
- A.6. Proof of Proposition 1: After preference processing, nondominated cuts are retained and one-bit-flip neighbors are iteratively refined until convergence or the pass limit.
C. Implementation Details
The implementation fixes common defaults and evaluates CPU and GPU variants under explicitly controlled hardware, seeds, stopping rules, and baseline procedures.
- C. Implementation Details: MO-QUCO uses 100,000 uniformly sampled preferences, batch size 64, 150 PGA steps, and step size 0.05 by default.
- C. Implementation Details: The refinement uses at most five passes and stops early when a pass adds no new nondominated cut.
- C. Implementation Details: CPU experiments use one AMD EPYC 9555 core with one-thread linear algebra, enabling direct runtime comparisons.
- C. Implementation Details: pMO-QUCO uses the same parameters and seeds, runs preference sweeps on one NVIDIA H200 NVL GPU, and performs refinement on one CPU core.
- C. Implementation Details: Baseline evaluation includes exact, heuristic, weighted-sum, and quantum methods under stated coefficient scaling, stopping, and simulation choices.
D. Ablation and Sensitivity Study
Ablations identify projected-gradient sampling as the main quality driver and bit-flip refinement as necessary for closing the remaining gap; sensitivity and formulation studies guide defaults.
- D. Ablation and Sensitivity Study: 99.9999% for K = 3 and 99.9954% for K = 4: projected-gradient sampling raises random-baseline hypervolume under the ablation budget.
- D. Ablation and Sensitivity Study: The bit-flip refinement closes the remaining gap to the reference optimum, but alone reaches only about 97% on random cuts.
- D. Ablation and Sensitivity Study: Increasing preferences or batch size generally reduces the HV gap, while PGA steps and step size have substantial nonmonotonic effects.
- E. Choice of the Quadratic Formulation: The adjacency formulation offers the best balance of solution quality and computational cost and is selected as MO-QUCO’s default objective.
- E. Choice of the Quadratic Formulation: Figure 3 compares formulation trajectories and pre/post-refinement HV gaps using CPU time, means, and variability across three seeds.
F. Data and Instance Availability
The study combines public benchmark instances with newly generated synthetic and strongly conflicting graphs, using exact fronts at small size and method comparisons at larger sizes.
- F. Data and Instance Availability: The main experiments use Kotil et al.’s public QAMOO benchmark, while supplementary experiments use an adapted conflict-instance generator.
- F. Data and Instance Availability: The novel dataset contains synthetic K = 3 instances with 20, 100, or 200 vertices on complete and Erdős–Rényi graphs.
- F. Data and Instance Availability: Strongly conflicting instances use negatively correlated objectives, including f3(z) = −0.5f1(z)−5f2(z), with empirical correlation approximately −0.915.
- F. Data and Instance Availability: At n = 20, exact WSM recovers negligible Pareto-front coverage, whereas MO-QUCO recovers more than 99.9% and nearly 100% hypervolume.
- F. Data and Instance Availability: Exact enumeration is infeasible for n ∈{100, 200}, so pMO-QUCO is compared with NI-dSB on the larger instances under a 10-second GPU stopping rule.
H. Limitations
MO-QUCO does not guarantee recovery of the global Pareto front because each scalarized problem is optimized approximately. Its performance and refinement cost depend on sampling choices and archive size.
- MO-QUCO does not guarantee recovery of the global Pareto front because its scalarized problems are optimized approximately.
- Performance depends on the numbers of sampled preferences and initial points.
- The 1-bit-flip refinement can become expensive for large archives because it evaluates every archive vector's neighborhood.