A RIGOROUS GRAPH-THEORETIC FORMULATION OF HIGH-DIMENSIONAL COMBINATORIAL OPTIMIZATION
Defining the State Space, Feasibility, and Optimal Solutions with Detailed Applications
High-Dimensional Optimization · Graph Theory · Tensor Networks · Quantum-Ready Computation
THE PROBLEM
Some combinatorial problems are difficult for a reason that dimensionality alone does not capture.
The mathematically possible decision space may be enormous, while the set of solutions satisfying the actual physical constraints occupies only a tiny, fractured region within it.
In a power grid, for example, the number of possible generator configurations can be astronomical. Yet almost all randomly selected configurations violate transmission limits, voltage constraints or the nonlinear equations governing power flow. The same structural problem appears in very different forms in satellite tasking, protein packing, data-center allocation, quantum error correction and adversarial drone coordination.
The difficulty is therefore not simply:
How do we search an enormous space?
It is first:
How do we discover where, inside that space, meaningful solutions can exist?
The paper calls the overwhelmingly infeasible region surrounding those solutions the combinatorial void.
THE IDEA
Rather than immediately searching or approximating the complete decision space, the paper proposes extracting its feasible skeleton first.
The underlying physical or logical system is represented as a heterogeneous spatio-temporal graph. Decisions live in a high-dimensional discrete Cartesian space, while feasibility is induced by the nonlinear constraints propagating through the graph.
A deliberately simplified version of the problem is then used—not as an approximation to the final answer, but as a map of where to look.
A cheap convex proxy identifies the approximate structure and stability margins of promising decisions. Sparse regularization isolates a candidate skeleton. Ambiguous regions around that skeleton are hierarchically partitioned and progressively tested against the true nonlinear physics.
The result is a collection of feasible structured fibers: not yet the global solution, but a computationally meaningful representation of where the real problem lives.
FROM THE VOID TO A COMPUTABLE SPACE
This distinction is important for high-dimensional approximation.
Tensor Train methods can compress objects whose nominal dimensionality is enormous. But compression alone does not solve the feasibility problem.
If a tensor approximation samples blindly from a space in which almost every point is physically impossible, its samples repeatedly fall into the combinatorial void. The representation learns essentially nothing about the thin region containing feasible—and potentially optimal—solutions.
The proposed architecture reverses the sequence:
simplify → locate → validate → structure → approximate → optimize
The inexpensive approximation is used to discover structure. The expensive physics is concentrated where it carries information. Only then is the resulting feasible structure presented to the tensor representation.
The paper therefore treats dimensional reduction not merely as a compression problem, but as a problem of discovering the geometry of feasibility before compression begins.
A GENERAL STRUCTURE
An important test of the idea is whether it survives changes of application.
The paper develops the same mathematical architecture in six substantially different domains:
Power Grid Optimization — commitment and dispatch decisions constrained by nonlinear AC power-flow physics.
Satellite Constellation Tasking — sparse assignments constrained by orbital geometry, visibility and resource availability.
Protein Rotamer Packing — combinatorial molecular configurations constrained by physical interactions.
Hierarchical Data-Center Load Balancing — allocation decisions constrained by network topology and capacity.
Quantum Error Correction — decoding within an enormous error space in which the relevant error structures occupy a highly constrained subset.
Adversarial Drone Swarm Teaming — dynamic multi-agent decisions subject to kinematic, resource and adversarial constraints.
The applications are deliberately different. Their commonality is the underlying structure:
an enormous nominal decision universe, a much smaller feasible region generated by interacting constraints, and a need to discover that region before high-dimensional optimization becomes useful.
WHY IT MATTERS
Much of modern computation is concerned with increasing the size of the spaces we can search, simulate or approximate.
This work approaches the problem from the opposite direction.
When feasible solutions occupy an infinitesimal fraction of the nominal space, greater search power alone may not solve the problem. The more important question may be whether the structure of the problem can first tell us where computation is worth spending.
That has implications beyond Tensor Trains. It applies whenever an advanced optimizer—classical, AI-based, quantum-inspired or eventually quantum—operates on a representation whose ambient space is vastly larger than its meaningful subset.
The central proposition is therefore simple:
Before solving a high-dimensional problem, find the structure of the space in which its solutions can exist.
RESEARCH STATUS
Independent research · 2026
Working research paper