Bridging the Gap Between Heuristics and Optimal Solvers

This direction is split into other directions: heuristic suboptimality (optimal vs. approximate scheduling). Its last version stays readable and citable here.

Version 1 of 154 papers54 conceptsfrozen 2026-10-04

In industrial systems—from semiconductor fabrication to e-commerce warehouses—decisions must be made in milliseconds. When a new order arrives or a machine fails, a scheduler must decide "what goes where" immediately. This creates a fundamental tension: we can have a solution that is perfect (mathematically optimal) but takes hours to compute, or a solution that is instant (a simple heuristic) but leaves money on the table through wasted resources.

Recent research focuses on bridging this "optimality gap." By using machine learning, evolutionary algorithms, and hybrid mathematical frameworks, researchers are developing methods that offer the speed of a simple rule with the precision of a global optimizer.

The Traditional Trade-off

To understand why this is difficult, consider the Job Shop Scheduling Problem (JSP) or Bin Packing. These are NP-hard, meaning the time required to find the absolute best solution grows exponentially with the number of tasks or items.

Traditionally, engineers choose between two extremes:

  1. Exact Solvers: Tools like Mixed-Integer Programming (MIP) or Constraint Programming (CP) explore the search space systematically. They guarantee the best possible result but, as Yingchen Yu notes, their complexity often makes them fail on real-world factory floors where conditions change rapidly.
  2. Greedy Heuristics: Simple rules like "First-Come, First-Served" or "Best Fit" are nearly instantaneous. However, as Haoyuan Hu and colleagues demonstrate in 3D bin packing, these rules often result in significant material waste because they cannot "see" the global consequences of a local decision.

Learning the Intuition of a Solver

One powerful way to bridge this gap is to treat a slow, optimal solver as a teacher. If an exact solver takes ten minutes to find the perfect schedule for a small problem, we can train a neural network to mimic that decision-making process in a fraction of a second.

Peter K. Campbell and his team pioneered this by training "mask perceptrons" to mimic linear programming for telecommunications. More recently, Charith Mendis applied this to compiler auto-vectorization. Instead of running a slow mathematical search every time a program compiles, they used imitation learning to predict the optimal instruction schedule, achieving high-quality code at standard compilation speeds.

The intuition here is that neural networks are excellent at pattern recognition. While they don't "solve" the math, they learn the features of a good solution—like which items "belong" together in a bin—allowing them to make near-optimal guesses instantly.

Hybridizing Search and Heuristics

Another direction involves embedding fast heuristics directly into the search process of exact solvers. Rather than choosing between a heuristic and a solver, researchers are using heuristics to prune the search space.

Arthur Godet and colleagues proposed a clever inversion: instead of searching for the start times of tasks (the raw solution), they search over the input sequences of a greedy approximation algorithm. By using the heuristic as a "decoder," the solver can navigate a much smaller, more meaningful search space.

Similarly, Tommaso Mannelli Mazzoli and Nysret Musliu combined Large Neighbourhood Search with Column Generation for bus driver scheduling. They use a "destroy and repair" mechanism where a heuristic identifies problematic parts of a schedule and a mathematical solver "repairs" them, achieving new best-known solutions by balancing local speed with global refinement.

Evolving Better Rules with LLMs

Perhaps the most recent shift is the use of Large Language Models (LLMs) to "invent" new heuristics that humans might miss. Traditional dispatching rules (like "Shortest Processing Time") are simple because they were designed to be understood by humans.

Ibrahim Oguz Çetinkaya and Diego Forniés-Tabuenca have shown that LLMs can act as mutation operators in evolutionary pipelines. By reflecting on the performance of different code snippets, these systems evolve complex Python-based heuristics. These "evolved" rules remain as fast as traditional ones but significantly close the optimality gap, often outperforming human-designed rules by 5-10% in real-world environments.

Differentiable Scheduling

A final, more radical approach is to make the discrete, "jumpy" nature of scheduling continuous and smooth. Scheduling is usually hard because deciding to put Task A before Task B is an "all-or-nothing" choice.

Mingju Liu and Yingjie Li use the "Gumbel-Softmax trick" to transform these discrete choices into a differentiable landscape. This allows them to use GPU-accelerated gradient descent—the same engine behind modern AI—to "slide" toward a high-quality schedule. This bypasses the need for training data entirely, finding solutions for massive-scale designs faster than industry-standard solvers like Gurobi.

Why It Works: The Shift to "Good Enough"

The unifying theme across these 43 papers is a pragmatic shift in the definition of success. In many industrial contexts, the "marginal utility of the best possible solution," as Narayan Changder puts it, is often lower than the cost of the delay required to find it.

By prioritizing "near-optimality" (often within 1% of the theoretical best, as seen in Jiangwei Hou's work on power systems), these new methods provide a scalable alternative for real-time applications. Whether through GNNs that generalize across problem sizes (Mukul Gagrani) or self-labeling strategies (Andrea Corsini), the field is moving toward a future where "fast" and "optimal" are no longer mutually exclusive.

Papers in this version

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_bridging_the_gap_between_heuristics_and__ed310597,
  title = {Bridging the Gap Between Heuristics and Optimal Solvers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-the-gap-between-heuristics-and-optimal-solvers/rdr_ed3105974235417697bb6674ae0b599e},
  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_bridging_the_gap_between_heuristics_and__ed310597_v1,
  title = {Bridging the Gap Between Heuristics and Optimal Solvers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-the-gap-between-heuristics-and-optimal-solvers/rdr_ed3105974235417697bb6674ae0b599e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}