What Is an Optimality Certificate in Scheduling?

An optimality certificate is what a scheduling optimizer can actually prove about the plan it returns: the solve status, whether a mathematical gap is available, the objective lower bound if one was computed, and the resulting gap percentage. It is the honesty layer on top of an optimization run. EDGEBIC by User Solutions attaches one to every optimizer result so a planner can tell the difference between a plan that was simply the best one tried and a plan that is provably close to the theoretical best.

How it works

Optimization produces a schedule. The certificate describes the strength of the claim attached to that schedule, and there are two very different levels.

The multi-run engine works by generating many complete candidate schedules, each from a different global job ordering, scoring every one against the chosen objective, and returning the best. This is a heuristic search: it explores a large number of real, valid plans, but it says nothing about the plans it never generated. Its certificate reflects that. No gap is available, and the honest badge is that this was the best of a number of schedules tried within the time budget.

The exact solver works differently. Alongside searching for good plans, it computes a lower bound on the objective, a value that no schedule can possibly beat. When it returns a plan, it can subtract that bound from the plan's own objective value and quote the difference as a percentage. That is the gap: the maximum amount by which any conceivable schedule could improve on the one you are holding. Its certificate carries a real bound and a real gap.

A gap of zero is the strongest result available. It means the bound and the found plan met at the same value, so the plan is proven optimal for the objective selected. There is nothing left to find.

Two limits are worth stating clearly. First, the gap is always scoped to one objective. A plan proven within three percent on weighted tardiness makes no claim at all about total setup time or schedule stability. Second, the certificate is about provability, not about goodness in a general sense. A heuristic plan with no gap can be an excellent schedule; the certificate is simply declining to overstate what is known about it.

Both layers sit on the same floor. Whatever the certificate says, the optimizer's result is compared against the baseline plan before it is offered, and if it is not better under the requested objective the baseline is returned instead.

A concrete example

Think of the difference between two consultants reviewing your delivery routes.

The first spends a day trying forty different route plans and hands you the best one. It saves ninety minutes a day, which is real money. Ask them "could a better plan exist" and the honest answer is yes, probably, they only tried forty. That is a heuristic result with no gap.

The second builds a mathematical model, works out that no possible route plan can do the job in under six hours, and then hands you a plan that takes six hours and ten minutes. Ask them the same question and they can answer precisely: any better plan saves you at most ten minutes, under three percent. That is a certificate with a bound and a gap.

The second answer is not automatically the better plan. If the first consultant's ninety-minute saving happened to land near the theoretical floor, both plans are close. What the second answer gives you is the ability to stop looking, and to say so to somebody who has to sign off on it.

In a plant, that translates directly. "Best of 40 schedules tried in 12 seconds" is a useful, quick improvement. "Proven within 3% of optimal" is something a plant manager can take to a customer meeting.

How EDGEBIC uses it

Every optimizer proposal carries its certificate, and the badge shown alongside the proposed plan reads back exactly what the run could prove rather than a generic claim. The gap figure itself is the companion glossary term optimality gap, and what that proof is worth in practice is discussed in how a proven optimality gap builds trust.

Which certificate you get depends on the engine selected, which is covered in choosing the optimizer engine, multi-run or CP-SAT and in how the multi-run optimizer searches schedules. The floor underneath every result, regardless of certificate, is the never-worse clamp, and the objective the gap is measured against is an objective preset.

An optimality certificate is the optimizer refusing to claim more than it knows. For the wider vocabulary, see the manufacturing glossary, and to see optimization run against a live plan, explore EDGEBIC.