pMO-QUCO reached more than 99.99% of the study's HVmax comparison score in about 0.9 seconds on a 42-node benchmark, for both three-objective and four-objective versions, according to an arXiv preprint.
The evaluation was broader than that single benchmark. It used two 42-node, 46-edge benchmark instances with three and four objectives, plus Erdos-Renyi graphs with edge probability 0.5 and complete graphs with 100 or 200 nodes. Each synthetic size and topology configuration had five independent instances. On the generated Erdos-Renyi graphs, MO-QUCO and pMO-QUCO exceeded 99% of HVmax without refinement and 99.9% with 1-bit-flip refinement, while classical baselines stayed below 50% on average.
How the algorithm turns preferences into cuts
The paper's central idea is to convert several objectives into one weighted problem for each preference vector. It combines an adjacency-based quadratic formulation with linear scalarization: each objective is multiplied by a preference weight and the results are added to form an aggregated signed-weight graph. That leaves a preference-conditioned signed-weight single-objective MaxCut problem.
MO-QUCO then uses projected gradient ascent, or PGA, an iterative update rule, from sampled preferences and initial points. It binarizes the continuous outputs, keeps non-dominated cuts, and can apply repeated 1-bit-flip refinement. In the default setup, it sampled 100,000 preferences, used batches of 64 initial points, ran 150 PGA steps with a 0.05 step size, and allowed up to five bit-flip passes. pMO-QUCO used one H200 GPU.
What the update rule can settle locally
The theoretical analysis specifies what these updates can settle. For a fixed preference vector, a binary vector is a PGA fixed point exactly when every single-bit flip has nonpositive gain in the scalarized objective. In plain language, the cut is one that the update rule cannot improve with a one-bit move. When all flip gains are strictly negative, the analysis says that starts sufficiently close to the cut converge in a finite number of steps. The stated nonbinary fixed points, by contrast, are not locally asymptotically stable.
Preference choice is also part of the fixed-point condition. For a given cut, the paper characterizes the preference vectors that make it a fixed point through an adjacency fixed-point preference polytope, a set of allowable weights. The paper's set relations put cuts supported by weighted preferences inside the fixed-point set, and fixed-point cuts inside the set with no Pareto-improving one-bit neighbor. Pareto-optimal cuts also lie within that local set. Those relationships do not amount to a guarantee that the algorithm will recover the global Pareto front, the full set of best trade-offs.
Fast results on the reported graphs
On the 42-node benchmark, pMO-QUCO reached the cited level for both objective counts in about 0.9 seconds. Classical and QAOA baselines took longer to attain comparable hypervolume or retained larger gaps, especially in the four-objective case.
Against exact fronts on n=20 graphs, MO-QUCO with five 1-bit-flip passes recovered more than 99.9% of the exact Pareto front and nearly 100% of its hypervolume.
On four larger generated configurations, MO-QUCO and pMO-QUCO exceeded 99.6% of HVmax on average. Before refinement, pMO-QUCO took 19.2 to 50.3 seconds, compared with 262.2 to 1,042.1 seconds for MO-QUCO. The refined runs had mean HV above 99.98%, but used nearly the 10,000-second limit.
The ablation separated the two stages. At three objectives, random configurations reached 78.74% of HVmax versus 99.9999% for PGA configurations; at four objectives, the figures were 72.82% and 99.9954%. Bit-flip refinement alone reached about 97%, and the authors state that both stages are necessary.
Why the percentages need care
The authors say MO-QUCO does not guarantee recovery of the global Pareto front, depends on the number of sampled preferences and initial points, and can make 1-bit-flip refinement expensive for large archives. For larger generated instances, HVmax is the best observed final HV rather than the hypervolume of a known complete front. The reported percentages in those cases therefore show closeness to the study's best observed result, not proof that every possible trade-off was found.
Paper data and sources
Original title: Parallelizable Gradient-Based Optimization For Multi-Objective MaxCut
Authors: Jingjuan Huang, Alvaro Velasquez, Jia Liu, Ismail Alkhouri
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text