Optimizing Coupled Systems with Nonseparable Variable Interactions

119 concepts100 papers2 proposals

In classical optimization, the standard strategy is "divide and conquer." If a problem is too large, we decompose it into independent sub-problems, solve each in isolation, and aggregate the results. However, as Neumann et al. observe, real-world challenges—from UAV path planning to software performance engineering—rarely behave this way. Instead, these systems are characterized by interdependency, where a decision made in one component fundamentally alters the constraints and objective landscape of another.

The Failure of Additive Separability

The core difficulty in these problems lies in the lack of additive separability. In a separable problem, the global objective function is simply the sum of independent sub-functions. If you optimize one variable, the others remain unaffected.

However, many modern combinatorial tasks are "non-separable." As Mei et al. and Yao argue, treating interconnected tasks as isolated components leads to significantly inferior global solutions. When variables are coupled, the optimal configuration of one component is contingent on the state of the others. For example, in high-performance software engineering, Curino et al. note that thousands of interacting parameters like buffer sizes and cache policies create non-linear dependencies that prevent local optimizations from reaching a global system-wide optimum.

The Canonical Example: The Traveling Thief Problem

To build intuition for this coupling, researchers often point to the Traveling Thief Problem (TTP). The TTP merges two classic NP-hard problems: the Traveling Salesperson Problem (routing) and the Knapsack Problem (packing).

In isolation, these are well-understood. But as Wu et al. and Wagner explain, the TTP introduces a dynamic coupling: the weight of the items the thief picks up (the packing sub-problem) reduces their travel speed (the routing sub-problem). This creates a non-linear search space where the "best" route depends entirely on the "best" packing plan, and vice versa. Nikfarjam et al. demonstrate that this interaction makes it impossible to solve the components sequentially without losing global quality.

Identifying Variable Linkages

If we cannot assume independence, how do we solve these problems? The first step is often interaction detection.

Methods like Differential Grouping, proposed by Jiao et al., attempt to mathematically identify which variables "talk" to each other. By analyzing mixed second-order partial derivatives, these algorithms can cluster interdependent variables into sub-components that must be optimized together. However, this becomes difficult when "overlapping" variables exist—parameters that act as intermediaries between multiple groups. Tian et al. highlight that if these overlapping variables are not correctly identified, the decomposition fails, and the optimizer may treat the entire system as a single, intractable "black box."

Moving Toward Unified Solvers

Recent research suggests that the most effective way to handle deep interdependency is to move away from decomposition entirely in favor of holistic representations.

  1. Unified Decision Models: Ban et al. show that in recommendation systems, modeling multi-part decisions (like a bundle of items) as a unified system using neural contextual bandits consistently outperforms running multiple independent learners. Independent learners fail to capture the weighted relationships between choices.
  2. Joint Heuristics: In the realm of Mixed Integer Linear Programming (MILP), Li et al. propose frameworks like L2Sep that jointly optimize multiple solver components, such as cut generation and branching rules, to capture their synergistic effects rather than tuning them in isolation.
  3. Co-evolution and Diversity: Because the search space of coupled problems is so complex, finding a single optimum is often less useful than finding a diverse set of high-quality solutions. Nikfarjam et al. use co-evolutionary diversity optimization to explore how different structural configurations trade off against one another in the TTP.

Ultimately, the shift in this research area is from viewing complexity as a matter of scale (more variables) to viewing it as a matter of structure (more interactions). As Tschand et al. note in the context of GPU hardware optimization, modern systems often exhibit "all-or-nothing" performance characteristics where multiple features must be perfectly coordinated to achieve any gain. In such environments, the ability to navigate interdependency is not just an advantage—it is a requirement.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_interdependent_combinatorial_optimizatio_edebf535,
  title = {interdependent combinatorial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interdependent-combinatorial-optimization/rdr_edebf535b66e406dba5df25933a13fd5},
  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_interdependent_combinatorial_optimizatio_edebf535_v1,
  title = {interdependent combinatorial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/interdependent-combinatorial-optimization/rdr_edebf535b66e406dba5df25933a13fd5/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