Optimal Resource Allocation through Integer Linear Programming

This direction is split into other directions: constrained resource optimization. Its last version stays readable and citable here.

Version 1 of 1270 papers288 conceptsfrozen 2026-10-04

In modern computing and logistics, we rarely face a single, simple choice. Instead, we face a combinatorial explosion of decisions: Which GPU should handle this specific request? How many tokens should we allocate to this video frame? Which patients should receive a limited supply of preventive care?

Traditionally, these problems were solved using heuristics—"common sense" rules of thumb like "send the biggest job to the fastest processor." But as systems grow more heterogeneous and constraints become tighter, heuristics fail. A new wave of research across diverse fields—from LLM serving to public health—is replacing these rules of thumb with Integer Linear Programming (ILP) and its variants. By framing resource management as a formal mathematical optimization, researchers are achieving gains in efficiency that heuristics simply cannot reach.

The Core Intuition: From Rules to Constraints

The fundamental shift in this research direction is treating resource allocation not as a procedure to follow, but as a space to search.

In a typical system, you have objectives (things you want to maximize, like throughput or accuracy) and constraints (limits you cannot break, like memory capacity, latency deadlines, or monetary budgets). Luis Pabon, Bodun Hu, and Saurabh Agarwal demonstrate this in Patchwork, where they model Retrieval-Augmented Generation (RAG) as a concurrent-flow problem. Instead of guessing how to balance retrieval and generation, they use Mixed-Integer Linear Programming (MILP) to mathematically maximize throughput across heterogeneous hardware.

The "Integer" part of ILP is crucial. In many real-world problems, you cannot allocate half a GPU or send 0.7 of a vaccination team to a village. Decisions are binary (yes/no) or discrete (1, 2, 3). ILP solvers excel at finding the best possible combination of these discrete choices within a massive search space.

Balancing Competing Objectives

One of the most powerful applications of this approach is navigating the "Pareto frontier"—the set of choices where you cannot improve one metric (like speed) without hurting another (like cost).

In the realm of edge computing, Umar Ibrahim Minhas and colleagues explore "transprecision computing" in Increased Leverage of Transprecision Computing for Machine Vision Applications at the Edge. Their system uses an ILP solver at runtime to swap between thousands of model configurations. By treating energy and memory as hard constraints, the solver identifies the exact configuration that maximizes accuracy without crashing the device or draining the battery.

Similarly, in HADIS, Qizheng Yang and Hui Guan use MILP to manage text-to-image diffusion models. The system dynamically selects model variants and batch sizes to maintain service-level objectives (SLOs). The intuition here is that the "best" model isn't static; it depends on the current traffic and available GPU cycles.

Managing Heterogeneity and Scavenging

As hardware becomes more specialized, the "one-size-fits-all" approach to scheduling breaks down. We now see clusters containing a mix of high-end A100s and older P100s. Zizhao Mo and Huanle Xu address this in Hetis by using linear programming to dispatch attention heads across different GPUs. The solver balances the computational speed of the card against the communication overhead of moving data between them.

This mathematical rigor also allows for "scavenging" resources that would otherwise go to waste. Feng Yan and Ian T. Foster developed MalleTrain and BFTrainer to harvest idle nodes on supercomputers. Because these nodes can be reclaimed at any time, the system uses MILP to constantly redistribute the remaining "malleable" training jobs, ensuring that the cluster stays at 100% utilization without delaying primary users.

Beyond Computing: Social and Physical Logistics

The beauty of the ILP framework is its domain-agnostic nature. The same logic used to schedule GPUs can be applied to saving lives.

In ADVISER, Vineet Nair and Aparna Taneja optimize vaccination interventions in Nigeria. By modeling transport vouchers and health drives as variables in an integer program, they maximize vaccine uptake under a strict budget. A similar approach is seen in the CC19LP framework by Victoria C. P. Chen and colleagues, which uses linear programming to balance the reopening of communities with the need to minimize COVID-19 fatalities.

Even in creative tasks like video generation, optimization plays a role. Changyao Tian and Mengqi Li show in AdapTok that tokenizing video can be framed as an ILP problem. By dynamically shifting a fixed "token budget" from simple, static scenes to complex, high-motion ones, they achieve higher fidelity with less data.

Why It Works: The Global View

The recurring lesson across these 182 papers is that local heuristics are myopic. A heuristic makes the best decision for the current task, but an ILP solver makes the best decision for the entire system over a period of time.

Whether it is Gohar Irfan Chaudhry orchestrating agentic workflows in Murakkab or Grace Li Zhang securing hardware netlists in TimingCamouflage+, the mechanism remains the same:

  1. Quantify the goals and limits.
  2. Formulate them as linear equations.
  3. Solve for the global optimum.

As our systems grow more complex, the "math-first" approach to orchestration is no longer a luxury—it is the only way to ensure that every cycle, every watt, and every dollar is used to its fullest potential.

Papers in this version

Showing 60 of 270 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_optimal_resource_allocation_through_inte_e89ab95d,
  title = {Optimal Resource Allocation through Integer Linear Programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-resource-allocation-through-integer-linear-programming/rdr_e89ab95d2e8b4eff88431c217db7d03f},
  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_optimal_resource_allocation_through_inte_e89ab95d_v1,
  title = {Optimal Resource Allocation through Integer Linear Programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-resource-allocation-through-integer-linear-programming/rdr_e89ab95d2e8b4eff88431c217db7d03f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}