Divide and Learn: Multi-Objective Combinatorial Optimization at Scale

• URL: http://arxiv.org/abs/2602.11346v1
• Date: Wed, 11 Feb 2026 20:29:35 GMT
• Title: Divide and Learn: Multi-Objective Combinatorial Optimization at Scale
• Authors: Esha Singh, Dongxia Wu, Chien-Yi Yang, Tajana Rosing, Rose Yu, Yi-An Ma,
• Abstract summary: Multi-objective optimization seeks solutions over exponentially large discrete spaces.<n>We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems.<n>On standard benchmarks, our method achieves 80--98% of specialized solvers performance.
• Score: 41.78439888126577
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• BAMBO: Construct Ability and Efficiency LLM Pareto Set via Bayesian Adaptive Multi-objective Block-wise Optimization [4.196004665145396]
  BAMBO (Bayesian Adaptive Multi-objective Block-wise Optimization) is a novel framework that automatically constructs the Large Language Models (LLMs)<n>Formulated as a 1D clustering problem, this strategy leverages a dynamic programming approach to optimally balance intra-blockvolume and inter-block information distribution.
  arXiv  Detail & Related papers  (2025-12-10T15:32:56Z)
• Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation [10.153136816705542]
  POCCO is a novel plug-and-play framework that enables adaptive selection of model structures for subproblems.<n>We propose a preference-driven optimization algorithm that learns pairwise preferences between winning and losing solutions.
  arXiv  Detail & Related papers  (2025-06-10T15:25:06Z)
• High-Dimensional Bayesian Optimization Using Both Random and Supervised Embeddings [0.6291443816903801]
  This paper proposes a high-dimensionnal optimization method incorporating linear embedding subspaces of small dimension.<n>The resulting BO method combines in an adaptive way both random and supervised linear embeddings.<n>The obtained results show the high potential of EGORSE to solve high-dimensional blackbox optimization problems.
  arXiv  Detail & Related papers  (2025-02-02T16:57:05Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Robust expected improvement for Bayesian optimization [1.8130068086063336]
  We propose a surrogate modeling and active learning technique called robust expected improvement (REI) that ports adversarial methodology into the BO/GP framework. We illustrate and draw comparisons to several competitors on benchmark synthetic exercises and real problems of varying complexity.
  arXiv  Detail & Related papers  (2023-02-16T22:34:28Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
  arXiv  Detail & Related papers  (2022-10-20T14:54:37Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.