How a Proven Optimality Gap Builds Trust in a Schedule

A proven optimality gap is the percentage between the schedule EDGEBIC found and the best schedule that could theoretically exist for your goal. When that gap is zero, the plan is proven optimal: no better schedule exists, and the math says so. When the gap is small, you know the ceiling on any further improvement without having to search forever. This single number turns "could we do better?" from an argument into a bounded fact, which is why it does more for planner trust than any amount of marketing language.

EDGEBIC by User Solutions computes this gap with its CP-SAT mathematical solver, one of the two optimizer layers the platform ships. The multi-run search does an honest thorough search but cannot prove a gap; the solver can. This post explains what the gap is, how it is computed, and why it matters more than a bigger claim would.

What the gap actually measures

Most scheduling tools that call themselves optimizers do a search: they try a lot of arrangements and keep the best one they saw. That is genuinely useful, but it leaves a question hanging. You found the best of the ones you tried. Was there a better one you did not try? A pure search cannot answer that.

A mathematical solver answers it differently. Alongside the best plan it finds, it computes a lower bound: a proven floor that no schedule can drop below on your objective. The gap is the distance between the plan you have and that floor:

gap % = (objective of found plan − proven lower bound) / objective × 100

If the plan's objective equals the bound, the gap is zero and the plan is proven optimal. If the plan comes in at 40 and the bound is 38.5, the gap is under four percent, and you know the very best plan imaginable saves at most a percentage and a half of the objective. There is nothing left to wonder about.

Learn the concept in plain terms in what is an optimality gap in production scheduling.

Why "proven" beats "best" for trust

Trust in a schedule is not built by asserting the schedule is good. It is built by ruling out the doubt that a better one is hiding. Compare the two honest badges EDGEBIC can show:

The multi-run badge is honest and useful, and for a daily pass it is often all you need. But when a manager, a customer, or an auditor asks whether the plan could be tighter, the proven badge answers with a bounded number instead of a shrug. That is the difference between confidence and hope.

How EDGEBIC keeps the claim honest

A proven gap is only trustworthy if the product never overstates it. EDGEBIC enforces several rules that keep the badge honest:

• The multi-run search never borrows the solver's language. Its badge is always "best of N tried," never "optimal." Layer one is a heuristic search and says so.
• When a job uses a routing feature the solver does not yet model natively, that job is locked (reproduced exactly as scheduled) and no optimality claim is made for it. If every job is locked, the badge reads "nothing to optimize" rather than pretending to prove anything.
• The proven plan is still clamped never-worse against your current plan. The proof is about optimality; the clamp is about safety. Both hold at once.

This honesty is the whole point. A gap you cannot trust is worse than no gap, because it invites exactly the doubt it was supposed to remove.

A worked example: reading the gap

Take a small finishing cell with one shared shift and two machines, planning five jobs for the week. Your current plan finishes the workload in a weighted-lateness objective of 12.0 hours. You run the CP-SAT solver with the on-time-first goal and a 30-second budget.

Result A, gap 0%. The solver returns a plan with an objective of 6.0 and a proven lower bound of 6.0. The badge reads "Proven optimal in 4 seconds." You now know two things: the plan halved your weighted lateness, and no schedule on earth does better for this goal. There is no room left to argue, and none to chase.

Result B, gap 4%. On a harder week the solver returns an objective of 6.5 with a lower bound of 6.24. The badge reads "Proven within 4% of optimal." The best conceivable schedule would improve the objective by at most about a quarter of an hour. You accept the plan knowing precisely what you are leaving on the table, which is almost nothing.

The manager conversation. In both cases, when someone asks "could we do better?", you point at the badge. In case A the answer is a flat no. In case B the answer is "by at most four percent, which is fifteen minutes of weighted lateness across five jobs." Either answer closes the discussion in seconds. That is trust, and it comes from the gap, not from a slogan.

To read the whole comparison screen the gap lives on, see how to run and read an optimization in EDGEBIC.

When the gap is worth chasing, and when it is not

A proven gap is information, not a command. Use it to decide, not to obsess:

• Gap is zero: accept and move on. There is provably nothing better.
• Gap is small (a few percent): the ceiling on any further gain is tiny. Accept the plan. Chasing the last percent on a hard problem burns time for a slice of an hour.
• Gap is larger and the stakes are high: give the solver a longer budget once. If the gap closes, keep the tighter plan; if it barely moves, the problem is genuinely hard and you now know the realistic best is out of easy reach.

The gap frees you from perfectionism precisely because it quantifies imperfection. You stop searching not because you gave up, but because the number told you further search is not worth it.

Why a search cannot give you the gap

It is worth being precise about why only the mathematical solver can report a proven gap, because the distinction is the whole reason two engines exist. A search, however thorough, only knows about the arrangements it evaluated. If it tries a thousand plans and the best scores 8.0, it can honestly say "the best of a thousand I tried scores 8.0." It cannot say whether a plan it never tried scores 7.0, because it has no way to reason about plans outside its sample.

A solver reasons differently. By modeling the problem with variables and constraints, it can derive a bound that holds over every possible plan at once, not just the ones it looked at. That bound is a mathematical consequence of the constraints, so it applies to the plans the solver never explicitly built. The gap between the best plan found and that universal bound is the proven gap. This is why the multi-run search reports "best of N tried" and only the CP-SAT solver reports "proven within X% of optimal": the search has a sample, the solver has a proof. Both are the two optimizer layers, and each is honest about which kind of statement it can make. The proof itself is checked rather than assumed: the optimizer is verified against published benchmark problems whose optimal answers are already known, so a wrong result fails a test before it reaches a plant.

Where this fits in EDGEBIC

The proven gap is produced by the CP-SAT solver, selected in Options, Schedule, Optimizer Engine. It appears as the badge on the Optimizer tab after a run, alongside the verdict, the key performance indicator deltas, and the changes-only move list. It is also written into the audit record when you Accept, so months later the "why" of a plan carries the proof it was accepted under.

For the broader picture of how mathematical optimization improves a plan, see how mathematical optimization improves a schedule, the EDGEBIC optimizer guide, and the wider view of production schedule optimization. To explore the platform, visit EDGEBIC.

The bottom line

The proven optimality gap is the honest number that turns a good schedule into a trusted one. It rules out the alternatives you never tried, names the ceiling on any further gain, and ends the "could we do better" debate with mathematics. EDGEBIC computes it without asking you to understand the solver behind it: pick the mathematical engine, run, and read the badge. Zero means best possible; a small number means nearly so; either way, you know exactly where you stand.