Scaling Mixed Integer Linear Programming for Large Networks

19 concepts20 papers1 proposal

Many of the most critical infrastructure challenges of the modern world—from routing data through 5G networks to scheduling traffic lights and managing global supply chains—can be framed as network optimization problems. To solve these problems optimally, researchers frequently turn to Mixed-Integer Linear Programming (MILP) and Integer Linear Programming (ILP). These mathematical frameworks are highly powerful because they provide exact, provable guarantees while naturally handling discrete, binary choices, such as whether to open a specific supply route or route a data packet through a given server.

However, this exactness comes at a steep computational cost. As a network grows linearly in the number of nodes, edges, and time horizons, the underlying search space of an MILP expands exponentially. When moving from small-scale pilot studies to massive, real-world topologies with thousands of nodes, standard solvers encounter a severe scalability bottleneck.

To overcome this variable explosion, a major research direction focuses on breaking down this complexity. By leveraging advanced decomposition techniques, mathematical relaxations, and structural reformulations, researchers are making large-scale network optimization computationally tractable.

The Anatomy of the Scalability Bottleneck

To understand why large networks choke standard mathematical solvers, consider the sheer number of decision variables required to model them. In a typical network optimization model, variables must track commodities across every edge, node, and discrete time step.

This combinatorial explosion manifests across diverse domains:

Divide and Conquer via Decomposition

The most prominent strategy for restoring tractability is decomposition. The core intuition behind decomposition is to isolate the variables that "couple" different parts of the problem together. By separating a massive, monolithic optimization matrix into a high-level "master problem" and multiple independent "sub-problems," researchers can solve the sub-problems in parallel and iteratively update the master problem.

For example, in large-scale urban networks, solving complex routing and bike-sharing repositioning problems simultaneously is impossible at scale. However, S. K. Ghosh et al. demonstrate in Robust Repositioning to Counter Unpredictable Demand in Bike Sharing Systems that advanced decomposition techniques make these problems tractable for real-time decision-making by isolating worst-case demand scenarios.

Similarly, hierarchical optimization frameworks often encounter barriers when exact MILPs are embedded within inner loops. To manage power grid maintenance across mid-term, short-term, and real-time horizons, Gal Dalal et al. utilize a distributed scenario-based framework in Distributed Scenario-Based Optimization for Asset Management in a Hierarchical Decision Making Environment to prevent the computational cost of sub-problems from becoming prohibitive.

This push toward decomposition spans across city-wide security games (Waseem Abbas et al. in Detection and mitigation of attacks on transportation networks as a multi-stage security game) and non-linear water network designs (Sakshi Naik et al. in Integrating the Design of Desalination Technologies into Produced Water Network Optimization), proving that breaking the problem's structure is essential to maintaining feasible solve times.

Reformulation and Mathematical Relaxations

Another powerful approach changes how the problem is mathematically represented. If the discrete integer constraints are causing the solver to stall, researchers can either relax those constraints into continuous approximations or reformulate the network graph itself to unlock more efficient algorithms.

A clear example of this is found in dynamic traffic assignment. Finding a user equilibrium across a massive metropolitan network is notoriously difficult. However, Victoria Guseva et al. show in An Equilibrium Dynamic Traffic Assignment Model with Linear Programming Formulation that by utilizing a time-expanded graph and a point-queue model, the problem can be reduced entirely to a linear multicommodity flow framework. This clever structural shift allows the use of off-the-shelf optimization tools like column generation and dual subgradient methods, providing a flexible pathway for scaling traffic simulations when memory or computation time is constrained.

In hardware design, traditional ILP methods for assigning circuit segments to metal layers face similar scaling hurdles. To solve this, Derong Liu et al. introduce a framework in Incremental Layer Assignment for Timing Optimization that combines semidefinite programming (SDP) relaxation with a self-adaptive partitioning strategy, bypassing the traditional limitations of exact integer solvers.

When exact formulations remain too heavy for regional scales—such as calculating the "Price of Anarchy" across entire metropolitan traffic networks—researchers frequently pivot toward iterative optimization and data-driven estimation frameworks to maintain feasibility, as explored by Jing Zhang et al. in The Price of Anarchy in Transportation Networks by Estimating User Cost Functions from Actual Traffic Data and Yong Wang et al. in A Two-Stage Algorithm for Origin-Destination Matrices Estimation Considering Dynamic Dispersion Parameter for Route Choice.

Structural Flexibility: The Power of Anycast

Sometimes, the key to scaling an optimization model is changing the underlying operational assumptions of the network itself. Traditional routing models are often rigid, requiring a specific path to be calculated between a fixed source and a fixed destination. By introducing structural flexibility into the network design, the mathematical constraints can be simplified.

One prominent mechanism is the anycast principle. Instead of routing data or tasks to a single predetermined node, anycast allows the system to route a task to any available node within a functional group based on network conditions.

Traditional Routing (Rigid):
[Task] ----> [Fixed Path] ----> [Data Center A] (Choked if path/node fails)

Anycast Routing (Flexible):
             /---> [Path 1] ---> [Data Center A]
[Task] -----+----> [Path 2] ---> [Data Center B] (Optimized dynamically based
             \---> [Path 3] ---> [Data Center C]  on energy or capacity)

The authors demonstrate the power of this paradigm shift in two distinct ways:

  1. Resilience: In Exploiting relocation to reduce network dimensions of resilient optical grids, Jens Buysse et al. apply anycast to optical grid resilience. Instead of protecting a specific path to a fixed destination, the system protects the job itself, allowing it to be rerouted to an alternative server if a failure occurs. This flexibility reduces the total backup wavelength capacity required by roughly 20%, easing the burden on the underlying ILP solver.
  2. Sustainability: In Calculating the Minimum Bounds of Energy Consumption for Cloud Networks, Jens Buysse et al. leverage anycast to route tasks to whichever data center is currently the most energy-efficient. While joint network and IT optimization models typically face severe scalability challenges as nodes increase into the thousands, utilizing anycast routing helps streamline the decision space, enabling up to 55% energy savings compared to traditional methods.

By combining these structural paradigms with mathematical decompositions, researchers continue to push the boundaries of how large an infrastructure network can be optimized efficiently and exactly.

Key Foundational Work

Exploiting relocation to reduce network dimensions of resilient optical grids (2009) — contributed 1 concept elements to this direction.
Throughput-centric routing algorithm design (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_computational_scalability_in_network_opt_1bb886d0,
  title = {computational scalability in network optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-in-network-optimization/rdr_1bb886d0101c44b09b460a841b098b92},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_scalability_in_network_opt_1bb886d0_v1,
  title = {computational scalability in network optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-in-network-optimization/rdr_1bb886d0101c44b09b460a841b098b92/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake