Global Consensus and Consistency in Factored Optimization

14 concepts14 papers

To solve massive optimization problems—from routing thousands of delivery trucks to managing global financial portfolios—researchers often turn to decomposition. The core idea is to break a monolithic, intractable problem into smaller, independent subproblems that can be solved in parallel. As Amir et al. demonstrate, this approach can bypass the exponential "state space explosion" of traditional solvers, allowing planning to scale linearly with the number of subdomains.

However, decomposition introduces a fundamental tension: while subproblems are easier to solve in isolation, they often lose sight of the global context. This leads to a failure of local-to-global consistency, where solutions that appear optimal for a local partition cannot be stitched together into a valid global result.

The Problem of Frustrated Subproblems

When a problem is partitioned, the individual components may become "frustrated." This occurs when the optimal choice for one subproblem directly conflicts with the requirements of another. Wainwright et al. describe this as a failure to reach a mutual agreement or consensus. In cyclic or "loopy" systems, subproblems may cycle through various configurations without ever finding a set of values that satisfies everyone.

In the context of Natural Language Processing, Rush et al. frame this as non-tightness in the relaxation. When we decompose a complex decoding problem, we are essentially relaxing the requirement that all parts of the sentence agree perfectly. If the relaxation is not "tight," the subproblems will fail to converge on shared variables, leaving the global solver unable to identify a single optimal solution.

The Visibility Gap and Global Constraints

The primary reason subproblems fail to reach consensus is a lack of global visibility. Many real-world problems involve constraints that span the entire system, such as a total budget, a risk limit, or a specific trajectory.

  • Combinatorial Dependencies: Narayanan et al. found that random partitioning struggles with "all-or-nothing" requirements. If two items must be co-located to satisfy a constraint, but are split into different subproblems, the local solvers lack the context to realize they must be kept together.
  • Trajectory and Path Constraints: Hsu et al. note that constraints spanning the entire execution of a plan break the locality required for independent solving. A locally valid step might violate a global rule that only becomes apparent much later in the sequence.
  • Resource Aggregation: In portfolio optimization, Acharya et al. highlight the risk that local asset selections, while optimal for their specific "community," may collectively violate global risk or budget limits during the aggregation phase.

The Price of Independence

To ensure that local choices don't violate global rules, researchers sometimes impose stricter, more conservative local constraints. Witteveen et al. explain that this often results in a significant loss of "wiggle room" or flexibility. By making local rules overly restrictive to guarantee global feasibility, we may inadvertently block the best global solutions.

This leads to incompleteness. As the authors of Distributed Synthesis of Surveillance Strategies for Mobile Sensors argue, these conservative thresholds can cause a system to fail to find any decentralized strategy at all, even when a viable global solution theoretically exists. Similarly, Doron-Arad shows that in zero-communication models, locally optimal choices on one server can block superior configurations that are only visible when looking across all servers.

Bridging the Gap

Modern research focuses on mechanisms to restore this lost coordination without sacrificing the speed of decomposition.

One approach is the use of message-passing or dual decomposition, where subproblems iteratively update each other on their preferences until they reach an agreement. Another is the introduction of specialized "reunion" or "resolve" steps. For instance, Zhi Zheng et al. utilize a neural framework that includes a specific step to fix errors at subproblem boundaries, ensuring that local optimizations remain compatible with the broader schedule.

Ultimately, the success of factored optimization depends on balancing the efficiency of local solvers with the necessity of global consensus. As Bamas demonstrates, even sophisticated mathematical hierarchies can fail if they cannot bridge the gap between local feasibility and global validity.

Key Foundational Work

Exact MAP Estimates by (Hyper)tree Agreement (2002) — contributed 1 concept elements to this direction.
Factored Planning (2003) — 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_relaxation_non_tightness_b9b6fed7,
  title = {relaxation non-tightness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relaxation-non-tightness/rdr_b9b6fed7bb2c454fb642f0770ea37dbe},
  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_relaxation_non_tightness_b9b6fed7_v1,
  title = {relaxation non-tightness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relaxation-non-tightness/rdr_b9b6fed7bb2c454fb642f0770ea37dbe/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