Problem Decomposition for Scalable Combinatorial Optimization

33 concepts31 papers2 proposals

When facing large-scale combinatorial optimization problems—such as vehicle routing, resource allocation, or multi-model fitting—algorithms frequently hit a scalability wall. Because these problems are often NP-hard or highly non-linear, their search spaces grow exponentially with the number of variables or constraints. A single global solver attempting to find an optimal solution over the entire dataset quickly becomes computationally intractable.

The core intuition behind problem decomposition is to fundamentally alter this complexity math. Instead of navigating a massive, high-dimensional search space all at once, the global problem is broken down into smaller, isolated, or loosely coupled subproblems. Solving multiple well-conditioned subproblems sequentially or in parallel drastically reduces the active search space, lowers computational overhead, and bypasses physical hardware limitations.


The most direct way to decompose a large-scale optimization problem is to partition its input space or variable set into localized clusters. By isolating variables that interact strongly and separating those that do not, solvers can focus their computational budget where it matters most.

In routing and scheduling, for instance, global optimization is notoriously expensive. To scale up solutions, Viet The Bui et al. introduced a "Clockwise Clustering" method in Imitation Improvement Learning for Large-Scale Capacitated Vehicle Routing Problems to divide massive routing instances into manageable subproblems, allowing reinforcement learning agents to scale efficiently. Similarly, Zubin Zheng et al. leverage a decomposition strategy in Hybrid Memetic Search for Electric Vehicle Routing With Time Windows, Simultaneous Pickup-Delivery, and Partial Recharges to split complex multi-constraint routing into smaller, independent parts for efficient memetic local search.

This partitioning approach yields two distinct advantages:

  1. Deeper Exploration: As demonstrated by Thibault Falque et al. in Check-In Desk Scheduling Optimisation at CDG International Airport, reducing the search space allows constraint programming solvers to explore deeper within fixed time limits, ultimately yielding higher objective rewards than global solving approaches.
  2. Solver Specialization: Instead of forcing a single configuration to generalize poorly across a diverse dataset, Ke Tang et al. show in Automatic Construction of Parallel Portfolios via Explicit Instance Grouping that breaking a large configuration task into specialized subproblems allows automated optimization tools to design highly complementary, cluster-specific solver portfolios.

When local structures are highly predictable, such as in urban commuting, Mohd. Hafiz Hasan et al. demonstrate in Community-Based Trip Sharing for Urban Commuting that solving independent subproblems within predefined neighborhood clusters achieves near-optimal global performance at a fraction of the computational cost.


Iterative Refinement and Local Reformulation

When subproblems cannot be completely decoupled, optimization proceeds iteratively. The global problem is reformulated into a sequence of simpler, local optimization steps that gradually converge toward a global optimum.

+-------------------------------------------------------+
|               Global Optimization Problem             |
+-------------------------------------------------------+
                               |
                 Decompose via Reformulation
                               v
+-------------------------------------------------------+
|  Subproblem 1  -->  Subproblem 2  -->  Subproblem 3  |  (Iterative Loop)
+-------------------------------------------------------+
                               |
                           Converges
                               v
+-------------------------------------------------------+
|                 Near-Optimal Solution                 |
+-------------------------------------------------------+

For continuous and engineering control systems, this iterative sequence makes real-time optimization viable. Marta A. Zagorowska et al. apply this in Efficient safe learning for controller tuning with experimental validation by transforming a global controller tuning search into a sequence of local optimization problems, enabling standard numerical solvers to find safe parameters rapidly. Similarly, in wireless networks, Kezhi Wang demonstrates in Energy Efficient Resource Allocation in UAV-Enabled Mobile Edge Computing Networks that joint optimization of power, location, and capacity becomes computationally tractable when broken down into a series of smaller, component-wise subproblems solved iteratively. This pattern of joint optimization through iterative subproblem solving is also mirrored by Geng Sun et al. in J$\text{C}^{5}$A: Service Delay Minimization for Aerial MEC-Assisted Industrial Cyber-Physical Systems.

In machine learning contexts, iterative decomposition simplifies complex algebraic projections. Yoram Singer utilizes this mechanism in Efficient Learning of Label Ranking by Soft Projections onto Polyhedra, breaking a complex quadratic ranking problem into a series of simpler, soft projection steps applied to smaller subproblems.


Bypassing Numerical and Hardware Constraints

Decomposition is not merely a tool for acceleration; it is frequently a requirement for mathematical tractability and hardware compatibility.

Numerical Conditioning

In preference-based optimization, combining multiple objectives into a single unified problem can introduce massive weights, leading to severe numerical instability. To solve this, Josep Argelich et al. developed the Boolean Multilevel Optimization framework in On Solving Boolean Multilevel Optimization Problemse. The authors demonstrate that the computational overhead of executing a solver multiple times on smaller, well-conditioned subproblems is substantially lower than trying to solve a single, numerically complex unified problem.

Mathematical Simplification

Certain global functions are inherently difficult to optimize directly due to data sparsity or distributed privacy constraints. Akira Imakura et al. address this in New solutions based on the generalized eigenvalue problem for the data collaboration analysis by decomposing collaborative function optimization into column-wise subproblems, simplifying the formulation into a tractable generalized eigenvalue problem. In robust regression, Fumin Shen et al. exploit problem structure in Fast approximate L∞ minimization: Speeding up robust regression, breaking $L_\infty$ norm minimization into fixed-size subproblems because the global optimal solution is inherently determined by a small subset of data points.

Hardware Limitations

Physical computing hardware often has strict capacity or connectivity constraints. Quantum annealers, for example, are limited by their physical qubit layouts. In Outlier-Robust Multi-Model Fitting on Quantum Annealers, Saurabh Pandey et al. overcome this by iteratively decomposing large-scale computer vision tasks into smaller subproblems. By solving these smaller tasks on the restricted hardware and aggregating the results, their system processes significantly larger datasets and more candidate models than the physical quantum hardware could natively support.


Distributed Coordination and Game-Theoretic Decoupling

When subproblems are distributed across networks or represent distinct entities, decomposition requires coordination mechanisms to ensure that local solutions align with global objectives.

One approach is to use mathematical decomposition protocols that explicitly manage shared constraints. In A Distributed Operational Method for Convex Hull Pricing Based on the Alternating Direction Method of Multipliers with Dantzig–Wolfe and Benders Decomposition, Xinhan Lin et al. combine Dantzig-Wolfe and Benders decomposition with the Alternating Direction Method of Multipliers (ADMM). This allows large-scale electricity pricing problems to be broken into coordinated subproblems that optimize locally while preserving data privacy. Similarly, in 5G network slicing, Fei Song et al. show in Dynamic Virtual Resource Allocation for 5G and Beyond Network Slicing that decomposing global resource allocation into per-slice subproblems is what makes dynamic, distributed allocation computationally scalable.

Alternatively, coordination can be framed through a game-theoretic lens. Instead of utilizing centralized top-down decomposition, Melis Ilayda Bal et al. introduce a decentralized perspective in Optimistic Games for Combinatorial Bayesian Optimization with Applications to Protein Design. By framing a complex combinatorial optimization problem as a cooperative game among individual decision variables, they decouple global complexity into smaller decision sets, enabling efficient exploration of massive search spaces.

Key Foundational Work

A Probabilistic Constructive Approach to Optimization Problems (2001) — contributed 2 concept elements to this direction.
Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems (1992) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_divide_and_conquer_optimization_0f7e44c8,
  title = {divide and conquer optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divide-and-conquer-optimization/rdr_0f7e44c8240c40209d58921851973f93},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_divide_and_conquer_optimization_0f7e44c8_v1,
  title = {divide and conquer optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/divide-and-conquer-optimization/rdr_0f7e44c8240c40209d58921851973f93/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake