When Optimal Is the Wrong Answer

In the summer of 2024 I flew to Madrid to work on a scheduling problem. The first real lesson had nothing to do with scheduling. It was that "provably optimal" and "actually usable" are two different goals, and you have to pick which one you are solving before you write a line of the model.

The setting was fog computing. Picture an offshore oil field: real compute sitting on the platform, but the cloud is a satellite hop away and half the time just gone. When a fire starts, a whole chain of work has to run right there, on a deadline. Pre-process the sensor feed. Detect the fire. Localize it, simulate how it spreads, push the alerts. Each step needs the one before it. That structure, tasks wired together by what depends on what, is a Directed Acyclic Graph. A DAG.

One node on the platform usually cannot run all of it in time. So nearby fog nodes federate and split the DAG between them. That was the problem I was handed. Given the graph and a set of nodes with different speeds, decide which task runs where so the whole thing finishes before the deadline. Move a task to a neighbor and you buy compute but pay a communication delay to ship its inputs over. Placement is a trade the whole way down.

01  Writing it down

My part was the Mixed-Integer Linear Program, in Pyomo. A MILP sounds heavy and it is really just three questions a solver can read. What am I deciding. What do I want. What are the rules.

The decisions are a binary "does task i run on node a," plus a fraction per task. The fraction is the part I did not expect to matter. Under a tight deadline you cannot always run everything in full, so a task can run partway, trading some accuracy for time. Run it fully and it scores its full accuracy. Run it half and it scores less. So the objective was not "finish fastest." It was:

Maximize the average accuracy across all tasks, as long as everything still lands before the deadline.

The rules are just physics. One node per task. A task cannot start until every task feeding it has finished and shipped its data over, delay included. Nothing crosses the deadline.

# The core of it, in Pyomo. l[i,a] is the fraction of task i run on node a;
# e[i,a] is 1 if task i is placed on node a. y[i] is task i's finish time.

model.obj = Objective(
    expr=(1 / n) * sum(A[i] * sum(model.l[i, a] for a in F) for i in T),
    sense=maximize,
)

# one node per task
def one_fog(m, i):
    return sum(m.e[i, a] for a in F) == 1
model.one_fog = Constraint(T, rule=one_fog)

# a task cannot start before a predecessor finishes and ships its data over
def start_after_deps(m, i, a, j):
    return m.M[i, a] >= m.y[j] + sum(m.e[j, b] * comm[j, i, b, a] for b in F)
model.deps = Constraint(preds, rule=start_after_deps)

# nothing crosses the deadline
def deadline(m, i):
    return m.y[i] <= t_max
model.deadline = Constraint(T, rule=deadline)

When the solver comes back, the answer is not a good guess. It is the best assignment that exists, and you can prove it. On a small DAG that felt like a cheat code.

02  Then it stopped working

I scaled it up and the cheat code turned into a spinner.

Scheduling dependent tasks across nodes like this is NP-hard. That is not trivia, it is the whole plot. Ten tasks solve instantly. A hundred make the solver sweat. Past that the search space blows up and you sit watching a progress bar, waiting on an optimum that is technically on its way and practically never coming. The real system needed a thousand tasks. My provably correct model could not get near it.

This is where a lot of optimization work quietly dies. The model is right and it does not run at the size that matters.

03  The unglamorous version that shipped

So we built a second scheduler that gives up on optimal on purpose. Sort the tasks, and for each one drop it on whichever node finishes it soonest, keeping the dependencies and delays honest as you go. If the total runs long, shrink every task's duration by one shared factor until it fits under the deadline.

It is a worse scheduler. It leaves accuracy on the table that the MILP would have caught. But it finishes in a blink at a thousand tasks, right where the exact model fell over.

The last stretch of the project was not building either scheduler. It was measuring the distance between them. We varied the deadline slack, the number of nodes, and the size of the graph, and watched:

• —More slack helped both, but the MILP stayed ahead, and greedy's gains flattened once deadlines got loose.
• —More nodes helped the MILP every time. Greedy stopped improving past eight, it just could not use the extra room.
• —Size was the real split. The MILP did not degrade gently, it fell off a cliff, because it stopped finishing. Greedy held its lower line all the way out to a thousand.

That curve is the actual result, not either algorithm on its own. It tells you the one thing you need when you deploy: the point where you stop asking for optimal and start asking for done.

04  What stuck

I showed up thinking the job was the best schedule. I left knowing "best" is not something a schedule has on its own. It only means anything next to a size and a deadline. An optimal plan you cannot compute before the fire spreads is worth less than a rough one already in hand.

The hard part was never the solver. Most optimization problems are not really about finding the best answer, they are about knowing which answer you can afford. The exact model taught me the bound. The greedy one taught me to ship.

This was published at the IEEE Cloud Summit 2025 in Washington, D.C. It exists because the people at IMDEA Networks and the HPCC Lab handed a real formulation to an undergrad and let her own it: Gayani Gupta, Mohsen Amini Salehi, Antonio Fernández Anta, and José Aguilar. The trip ran on an NSF IRES grant. It was the first time I watched something go all the way, from a whiteboard to a solver I was arguing with at 1am to a paper with my name on it. I would do it again tomorrow.

05  FAQ

If greedy is what actually scales, why keep the MILP around at all?

Because without it you have no idea how much accuracy greedy is costing you. The MILP is the ground truth you measure against, and on small and mid-size graphs it is simply better. Plenty of real workflows live at that size.

Isn't "run a task partially" just a nice way of saying you return wrong answers?

Basically, and that is the point. In disaster response a rougher fire-spread estimate you get in time beats a perfect one that lands after the decision is already made. The model puts that tradeoff in the objective instead of pretending full accuracy is always free.

People solve NP-hard problems at scale all the time. Why not throw a stronger solver at it?

A stronger solver buys you a bigger constant, not a different curve. The blow-up is in the shape of the problem, not the tool. That is exactly why the paper pairs the exact model with a heuristic instead of betting on the solver catching up.

Where would this actually run?

Remote, latency-critical places where the cloud is optional: offshore rigs, industrial IoT, anywhere a workflow has to finish locally under a hard deadline. The next step is deploying it in those settings instead of on synthetic graphs.