Integer Solutions from Continuous Relaxations via Total Unimodularity

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2177 papers248 conceptsfrozen 2026-10-04

In combinatorial optimization, we often face a frustrating trade-off. We want to make discrete "either-or" decisions—assigning a flight to a route, a user to a base station, or a candidate to a committee—but these problems are frequently NP-hard. To solve them, we usually turn to Linear Programming (LP) relaxations, where we allow variables to be fractional (e.g., assigning 0.5 of a flight). The problem is that a fractional solution is often useless in the real world; you cannot fly half an airplane.

However, a recurring theme across logistics, social choice, and network design is the discovery of "perfect" formulations. In these cases, the continuous relaxation isn't just an approximation—it is guaranteed to return an integer solution. This phenomenon is driven by a mathematical property called Total Unimodularity (TU).

The Geometry of Integrality

To understand why this works, we have to look at the geometry of the feasible region. A Linear Program defines a polytope (a high-dimensional shape with flat faces). The optimal solution to an LP always sits at one of the "corners" or vertices of this polytope.

In a typical integer program, the vertices of the continuous relaxation have fractional coordinates. But if the matrix of constraints is totally unimodular, every single vertex of that polytope is guaranteed to have integer coordinates. As Dominik Peters demonstrates in the context of multi-winner elections, this means a standard LP solver will naturally "fall" into an integer solution without any extra effort. By proving a constraint matrix is TU, researchers like Peters and Martin Lackner have shown that complex voting rules, which are generally hard to compute, become solvable in polynomial time under specific preference structures like Single-Peaked on a Circle.

Network Flows as the Gold Standard

The most intuitive examples of TU come from network flow problems. In a network flow, the constraints usually involve "flow in equals flow out" at each node. This structure creates a node-arc incidence matrix, which is a classic example of a totally unimodular matrix.

Johannes C. Müller and Alexander Martín leveraged this in financial market design. By mapping the "futures opening auction problem" to a network flow, they ensured that the market-clearing prices and trade quantities could be found using simple linear programming. Because the matrix is TU, the trades are guaranteed to be discrete contracts rather than fractional shares, allowing for 100x speedups over traditional integer programming.

Similarly, in transportation, Axel Parmentier and Frédéric Meunier use TU to solve aircraft routing. By constructing bipartite graphs for flight schedules, they ensure that fractional flow models naturally collapse into discrete, periodic resource assignments.

Engineering TU into Complex Systems

Often, a problem isn't TU by default, but can be made TU through clever modeling. This "engineering" of integrality is a powerful tool for real-time systems:

  • Wireless Networks: Shiwen Mao proved that the constraint matrices for user association in Massive MIMO networks are TU. This allows 5G base stations to optimally assign thousands of users to antennas in milliseconds using continuous optimization.
  • Smart Cities: Ioannis Paschalidis and colleagues transformed the NP-hard problem of optimizing road lane directions into a tractable LP. By using piecewise linear approximations that preserve TU, they achieved optimal configurations for large-scale networks that would otherwise be computationally unreachable.
  • Fairness in AI: Ian Davidson and S. S. Ravi demonstrated that fairness constraints in clustering can be formulated as an ILP with a TU matrix. This allows "fairifying" datasets with hundreds of thousands of points in polynomial time.

When TU is Not Enough: Half-Integrality and Persistence

Sometimes, we cannot achieve full total unimodularity, but we can get close. Takuro Fukunaga explored the generalized terminal backup problem and found that while the LP relaxation isn't always integer, it is half-integral—meaning every variable is either 0, 1, or 1/2. This still provides a massive head start for rounding algorithms.

In computer vision, Alexander Shekhovtsov uses a related concept called partial optimality or persistency. In energy minimization tasks, even if the entire problem isn't TU, specific sub-problems might be. By solving a tight LP relaxation, we can identify a subset of variables that are guaranteed to be part of the global integer optimum, effectively "fixing" those labels and reducing the remaining search space.

Why It Matters

The shift toward TU-based modeling represents a move away from "black-box" integer solvers toward structural understanding. As Tobias Brunsch and Heiko Röglin show, TU LPs can even be solved using specialized algorithms like Shadow Vertex in strongly polynomial time.

By identifying the "hidden" unimodular structure in a problem—whether it's bike-sharing repositioning by Supriyo Ghosh or optical network scheduling by Tansu Alpcan—researchers are turning theoretically "impossible" discrete challenges into efficient, real-time continuous ones.

Papers in this version

Showing 60 of 177 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 102 papers
  2. Version 1 · 2026-10-04 · 177 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_integrality_preserving_linear_relaxation_75c2ed2a,
  title = {integrality-preserving linear relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/integrality-preserving-linear-relaxation/rdr_75c2ed2a73b643868eba085b1fd2a4bb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_integer_solutions_from_continuous_relaxa_75c2ed2a_v1,
  title = {Integer Solutions from Continuous Relaxations via Total Unimodularity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/integer-solutions-from-continuous-relaxations-via-total-unimodularity/rdr_75c2ed2a73b643868eba085b1fd2a4bb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}