Solving Exponential Linear Programs via Separation Oracles

This direction is split into other directions: approximate separation oracle. Its last version stays readable and citable here.

Version 1 of 1134 papers151 conceptsfrozen 2026-10-04

In many areas of computer science—from fair division and game theory to geometric optimal transport—researchers frequently encounter a daunting obstacle: an optimization problem where the number of constraints or variables is exponential in the size of the input. If you are trying to find a fair allocation of items among $n$ agents, there might be $2^n$ possible bundles to consider. If you are routing traffic, there might be an exponential number of paths through a city.

Standard linear programming solvers like the Simplex method fail here because they require explicitly listing every constraint. However, a powerful insight from the theory of the Ellipsoid Method allows us to bypass this "exponential bottleneck." The core idea is that we don't need to see the whole problem at once; we only need a way to identify why a specific candidate solution is wrong.

The Geometry of the Separation Oracle

The Ellipsoid method works by maintaining an "envelope" (an ellipsoid) that contains all possible valid solutions. In each step, the algorithm checks the center of this ellipsoid. If the center is a valid solution, we are done. If it isn't, we need a Separation Oracle: a sub-routine that takes the current point and returns a "cutting plane"—a linear inequality that the point violates but that all valid solutions satisfy.

This mechanism is transformative because the complexity of the optimization shifts from the number of constraints to the efficiency of the oracle. As shown by Julia Chuzhoy and colleagues in their work on Low-Degree CSPs, even if a problem has an exponential number of variables, we can solve its dual formulation if we can efficiently identify violated constraints.

Fairness and Social Choice

In the realm of fair division, Ioannis Caragiannis, Panagiotis Kanellopoulos, and Maria Kyropoulou used this approach to compute Interim Envy-Free allocations. Because the space of all possible random allocations is massive, they modeled the problem as a linear program where the dual is solved via the Ellipsoid method. The separation oracle here acts as a "fairness checker," identifying which agent's envy constraints are being violated without enumerating every possible outcome.

Similarly, Eden Hartman, Erel Segal-Halevi, and Yonatan Aumann demonstrated that Leximin fairness can be reduced to utilitarian optimization. They used a utilitarian solver as an approximate separation oracle, showing that even if the oracle isn't perfect, it can still guide the Ellipsoid method toward a globally fair solution.

Strategic Signaling and Game Theory

The power of this technique is perhaps most evident in Bayesian games. Consider a traffic app trying to minimize congestion. Matteo Castiglioni and Nicola Gatti have explored signaling in congestion games, where the number of possible signals a coordinator could send is astronomical. By dualizing the problem, they turned the search for an optimal signaling strategy into a constraint-checking problem. If the users are symmetric, a polynomial-time separation oracle exists, making the "impossible" task of optimal signaling suddenly tractable.

This extends to private Bayesian persuasion, where Andrea Celli and Stefano Coniglio used the Ellipsoid method to navigate the high-dimensional strategy spaces of sequential games. The oracle's job is to determine if a proposed information-sharing rule is valid or to find a specific scenario where a player would have an incentive to deviate.

Geometric Averages: The Wasserstein Barycenter

Beyond games and fairness, this framework has solved long-standing problems in geometry. Computing the Wasserstein barycenter—the geometric average of probability distributions—was historically plagued by an "exponential bottleneck" because the number of ways to transport mass between multiple distributions grows exponentially with the number of distributions.

Jason Altschuler and Enric Boix-Adserà proved that this can be solved in polynomial time in fixed dimensions. They achieved this by applying the Ellipsoid method to the dual of the multi-marginal optimal transport problem. Their separation oracle uses tools from computational geometry (like power diagrams) to efficiently find violated constraints in the transport plan.

Why It Works: The Duality of Search and Verification

The intuition behind this research direction is a fundamental shift in perspective: optimization is equivalent to separation.

If you can efficiently verify whether a solution is valid and provide a reason (a cut) when it is not, you can efficiently find the optimal solution, even in a space with exponentially many dimensions. This principle allows researchers like Haris Aziz to compute stable payoffs in path coalitional games and Shaojie Tang to solve massive team grouping problems in social networks.

By focusing on the design of clever separation oracles—often using dynamic programming, flow algorithms, or greedy heuristics—the field has turned the "curse of dimensionality" into a manageable algorithmic challenge.

Papers in this version

Showing 60 of 134 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_solving_exponential_linear_programs_via__31787058,
  title = {Solving Exponential Linear Programs via Separation Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-exponential-linear-programs-via-separation-oracles/rdr_31787058948c48e9ab98adcb8ab83b55},
  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_solving_exponential_linear_programs_via__31787058_v1,
  title = {Solving Exponential Linear Programs via Separation Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/solving-exponential-linear-programs-via-separation-oracles/rdr_31787058948c48e9ab98adcb8ab83b55/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}