Divide & Learn: Multiobjective Combinatorial Optimization at Scale

Esha Singh1, Dongxia Wu2, Chien-Yi Yang1, Tajana Rosing1, Rose Yu1,3, Yi-An Ma1,3
1Department of Computer Science and Engineering, University of California, San Diego · 2Stanford University · 3Halıcıoğlu Data Science Institute, University of California, San Diego
Accepted at ICML 2026
arXiv ICML Code Poster BibTeX
We reformulate multiobjective combinatorial optimization as an online learning problem over a decomposed decision space. The result: 80–98% of specialized solvers' performance at two to three orders of magnitude lower sample and compute cost.
D&L learning to construct Pareto optimal solutions in real time

D&L learns Pareto optimal solutions over exponential combinatorial spaces, one position at a time. No offline training, no surrogate models.

Overview

Multiobjective combinatorial optimization (MOCO) seeks Pareto optimal solutions over exponentially large discrete spaces. These problems appear in hardware design, drug discovery, LLM routing, and protein engineering. Existing methods sacrifice one of: generality, scalability, or theoretical guarantees.

D&L reframes MOCO as an online learning problem over a decomposed decision space: instead of searching the exponential global space, we decompose it into overlapping per position subproblems and solve each with a multi expert bandit. The result is sublinear regret depending only on the subproblem size $d \ll n$, an exponential to polynomial reduction over standard combinatorial bandits.

80–98%
of specialized solver performance
90%
less compute than Bayesian optimization
$10^{60}$
search space size we validate on

Key idea: decompose, learn, coordinate

D&L turns one intractable bandit problem into many tractable ones, with explicit coordination across overlapping positions.

D&L framework: Problem scalarization, Overlapping subproblem decomposition, Online combinatorial multi expert learning, Final Pareto front

How decomposition scales

Combinatorial bandits face one fundamental obstacle: the action space grows as $\{2^n, n!\}$ in the problem dimension $n$, so any no regret algorithm tracking per arm statistics is dead on arrival once $n$ leaves single digits. D&L sidesteps this by partitioning the $n$ variables into $K$ overlapping subproblems $S_1, \dots, S_K$, each containing roughly $d = n/K$ variables. Each subproblem becomes its own small bandit over $2^d$ arms, a number that stays polynomial in $n$ as long as $K$ scales sublinearly. The overlap regions $\mathcal{O}_{pq} = S_p \cap S_q$ are the real trick: shared variables accumulate statistics across multiple subproblems, so an observation made while optimizing one subproblem informs every other subproblem the variable appears in. Overlapping subproblems will occasionally disagree on their shared variables, and we resolve those conflicts via Lagrangian relaxation, a soft penalty $\xi_i^{(t)}$ added to the reward that grows when value estimates have high variance and shrinks as estimates converge. The dual variables $\lambda_i$ are updated by accelerated mirror descent, and the cumulative coupling cost provably scales as $\mathcal{O}(\sqrt{T})$. The net effect: what was one intractable bandit over an exponential action space becomes $K$ tractable bandits sharing information through overlap, with a coordination overhead that is sublinear in $T$ and therefore vanishes against the leading regret term.

A  ·  Problem

Combine $m$ objectives via a scalarization $g_w(x) = \sum_i w_i f_i(x)$ on a discrete decision space (permutations, binary vectors, or categorical configurations).

B  ·  Decompose

Partition the $n$ decision variables into $K$ overlapping subproblems $\{S_1, \dots, S_K\}$ of size $d = O(n/K)$. Shared variables let information flow between subproblems.

C  ·  Learn online

Each iteration: pick a weight $w_t$, optimize each subproblem with a multi expert bandit, update Lagrange multipliers $\lambda_i$ to resolve overlap conflicts.

D  ·  Collect

Solutions found across weights $w_1, \dots, w_T$ are stitched into the final Pareto front. Sublinear regret per subproblem yields an $\mathcal{O}(d\sqrt{T \log T})$ global bound.

What you can do with D&L

Any problem where you make many discrete decisions and care about multiple competing criteria fits the same template: pick decision variables, define your objectives, let D&L handle exploration.

ML Infrastructure

LLM Routing

Route incoming queries across a heterogeneous pool of LLM endpoints (GPT class, Claude class, open weights, fine tuned in house) to balance response quality, cost per token, and latency.

PositionsQuery slots in a batch
ActionsChoice of model / route
ObjectivesQuality, cost, p95 latency
Agentic AI

Agentic Tool Selection

At each step of an autonomous agent's trajectory (web search, code execution, retrieval, subagent dispatch), pick which tool to invoke. Feedback arrives only at task completion, every rollout is expensive, and the action space is combinatorial.

PositionsSteps in agent trajectory
ActionsTool / skill / subagent
ObjectivesTask success, token cost, wall clock
Reasoning Agents

Test time Compute Scheduling

For reasoning agents (chain of thought, self consistency, tree search), decide how much compute to spend at each step (number of samples, branching factor, verifier on/off, retry budget) to hit a target accuracy without burning the inference budget.

PositionsReasoning steps
ActionsSamples, branches, verifier toggle
ObjectivesAccuracy, total tokens, wall clock
LLM Applications

RAG Pipeline Configuration

Configure the discrete knobs of a retrieval augmented generation system: chunk size, top-$k$, reranker on/off, hybrid weights, embedding model, generator. Each end to end eval is an expensive offline benchmark run.

PositionsPipeline stages
ActionsComponent / hyperparameter bucket
ObjectivesAnswer quality, recall, latency, cost
Systems

Hardware and Software Codesign

Codesign AI accelerators with their software stacks (memory hierarchy, quantization, kernel layout) under expensive cycle accurate simulations. Featured in the paper.

PositionsHW + SW knobs (e.g. ReRAM size, kernel size)
ActionsDiscrete config values
ObjectivesAccuracy, latency, energy, area
AutoML

Neural Architecture Search

Search over discrete architecture choices (block type, depth, width, attention heads) for models that must hit a target accuracy and deployment budget.

PositionsLayers / blocks
ActionsOperator type, size, activation
ObjectivesAccuracy, FLOPs, memory, latency
Scientific Discovery

Molecule & Protein Design

Edit candidate molecules or protein sequences at the residue level, balancing binding affinity, synthesizability, and toxicity. Each evaluation is an expensive docking or assay simulation.

PositionsResidues / atomic edit sites
ActionsAmino acid / substituent
ObjectivesAffinity, SA score, ADMET

The pattern: pick decision variables and their domains, define your objectives, and D&L gives you regret bounded online optimization without training a surrogate or running offline pretraining.

Three coordinated mechanisms

1 Decomposition

Partition the $n$ variables into $K$ overlapping subproblems of size $d = O(n/K)$. Action space drops from $O(2^n)$ to $O(K \cdot 2^{n/K})$. Overlap regions $\mathcal{O}_{pq} = \mathcal{S}_p \cap \mathcal{S}_q$ let learning transfer across partitions.

2 Lagrangian coordination

Hard consistency $x_i^{(p)} = x_i^{(q)}$ is relaxed into a soft penalty that vanishes as estimates converge:

$$\mathcal{L}(x, \lambda) = r_t(x) - \sum_{i \in \mathcal{O}} \lambda_i \, \xi_i^{(t)}, \qquad \xi_i^{(t)} = (k_i - 1)\,\text{Var}(\hat V_{i,\cdot}^{(t)})\,\big(1 - \tfrac{N_{i,x_i^{(t)}}}{\sum_a N_{i,a}}\big).$$

Dual variables $\lambda_i$ are updated by accelerated mirror descent, yielding $O(\sqrt{T})$ cumulative coupling error.

3 Multi expert learning

Each subproblem is solved by an ensemble of no regret experts (UCB, EXP3, FTRL) sharing global statistics. One expert is sampled to select at each position; all experts update on the observed reward. Selection is decoupled from learning, giving robustness across reward structures.

Regret Bound

Total regret decomposes across subproblems and a coordination cost:

$$R(T) \;=\; \sum_{k=1}^{K} R^{(k)}(T) \;+\; C(T)$$

Final guarantee:

$$R(T) \;=\; \mathcal{O}\!\left(d\sqrt{T\log T}\right) \;+\; \mathcal{O}\!\left(K^2 Q R_{\max}\sqrt{T}\right)$$
Leading term scales with subproblem dimension $d$, not the global dimension $n$. Optimal $K^\star = \mathcal{O}\!\left(\sqrt{n/(QR_{\max})}\right)$.

Results

We evaluate D&L in two regimes: a real world expensive evaluation setting (hardware and software codesign for AI accelerators) and standard MOCO benchmarks where we stress test scalability.

Real world: Hardware and Software Codesign

A four objective problem over a 20 dimensional mixed integer design space ($\sim 2.2 \times 10^5$ configurations) where each evaluation requires cycle accurate neural accelerator simulation (hours of compute). Budget fixed at 150 evaluations.

The headline

D&L-TS reaches a hypervolume of 0.372 ± 0.006, about +28% over NSGA-II and +30% over MOBO-qNEHVI. The improvement holds despite the four objective structure, where hypervolume based Bayesian acquisition cost scales exponentially with objective count and qNEHVI breaks down.

This is the regime D&L was designed for: many competing objectives, expensive black box evaluations, no offline training.

Method Hypervolume ($\uparrow$)
NSGA-II0.291  ± 0.040
MOBO-qNEHVI0.287  ± 0.015
MOBO-qParEGO0.34  ± 0.012
D&L0.36  ± 0.01
D&L-TS0.372  ± 0.006
 Hardware and Software Codesign. Averaged over 10 seeds, fixed 150 evaluation budget. From Table 2 of the paper.

Scaling on standard MOCO benchmarks

Across Biobjective TSP, Biobjective Knapsack, Triobjective TSP, and Biobjective CVRP at sizes $n \in \{20, 50, 100, 200\}$. D&L-TS holds hypervolume close to the best problem specific solvers and matches their compute cost.

Hypervolume ratio across problem scales on Bi-TSP, Bi-KP, Tri-TSP, Bi-CVRP
Hypervolume ratio (↑ better) across four benchmarks and three problem sizes. D&L-TS (solid green) tracks the specialized WS/PPLS solver (grey dashed) far above all general purpose baselines.
Compute cost in TFLOPs across problem scales
Compute cost in TFLOPs (↓ better, log scale). D&L-TS sits with the cheapest specialized solver while PMOCO* and Best BO are 2–4 orders of magnitude more expensive.
Benchmark $n$ Problem specific General purpose Ours
WS PPLS/D-C PMOCO* NSGA-II Best BO D&L D&L-TS
Bi-TSP 20 .625.626 .360.573.536 .585.600
50 .629.628 .330.347.472 .530.540
100 .690.630 .309.294.104 .400.470
Bi-KP 50 .356.357 .340.219.301 .350.347
100 .440.447 .370.221.314 .338.385
200 .360.362 .186.280.266 .260.300
Tri-TSP 20 .467.388 .430.411.320 .430.420
50 .429.262 .390.173.062 .262.282
100 .488.241 .300.135.030 .210.234
Bi-CVRP 20 NA.480 .360.430.352 .450.460
50 NA.450 .330.310.140 .350.370
100 NA.430 .300.310.110 .253.300
Hypervolume ratio (↑ better, normalized to [0, 1]) across 4 benchmarks × 3 problem sizes, 200 instances each. Green bold = best overall; underline = best among general purpose methods. Full results with NDS and compute cost are in Table 1 of the paper.

Key takeaways

BibTeX

@inproceedings{singh2026dnl,
  title     = {Divide and Learn: Multiobjective Combinatorial Optimization at Scale},
  author    = {Singh, Esha and Wu, Dongxia and Yang, Chien-Yi and
               Rosing, Tajana and Yu, Rose and Ma, Yi-An},
  booktitle = {International Conference on Machine Learning (ICML)},
  year      = {2026},
  url       = {https://openreview.net/forum?id=TK82ECnJzD}
}