Divide and Learn: Multi-Objective Combinatorial Optimization at Scale

Multi-objective combinatorial optimization seeks Pareto-optimal solutions over exponentially large discrete spaces, yet existing methods sacrifice generality, scalability, or theoretical guarantees. We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems via adaptive expert-guided sequential construction. This formulation admits regret bounds of $O(d\sqrt{T \log T})$ depending on subproblem dimensionality \(d\) rather than combinatorial space size. On standard benchmarks, our method achieves 80--98\% of specialized solvers performance while achieving two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods. On real-world hardware-software co-design for AI accelerators with expensive simulations, we outperform competing methods under fixed evaluation budgets. The advantage grows with problem scale and objective count, establishing bandit optimization over decomposed decision spaces as a principled alternative to surrogate modeling or offline training for multi-objective optimization.

Many real world design problems require balancing several goals at once. For example, making a computer chip that is fast, cheap, energy efficient, and reliable, where the choices are discrete (which parts to use, in what order) and testing each option is slow and expensive. The number of possible designs is astronomically large, so trying them all is impossible. We built a method called Divide and Learn that breaks a huge problem into smaller, overlapping pieces and learns which choices work well by trial and error, improving as it goes. Unlike approaches that need a hand-built model of the problem or pre-training on similar tasks, our method learns from scratch on each new problem, directly from each result it sees, while a lightweight coordinator keeps the pieces consistent. Across classic routing and packing problems and a real chip design task, our method matches specialized solvers while using far less computation. We also prove mathematically that its average performance converges toward that of the best fixed design, no matter how complex the problem.