Benchmarking is how you earn trust in optimization work. Without a fair comparison, it is hard for a reader to tell whether your results come from a good idea, a lucky seed, hidden tuning, or just an easy dataset.
This page helps you pick an evaluation strategy that matches what you want your thesis to contribute, and then report it in a way that is reviewable.
If you are still deciding which algorithm class to implement, start with Choosing Optimization Methods.
Contribution Types (What Your Thesis Can Contribute)
Not every good thesis needs an algorithm that beats the state of the art. What matters is that your contribution is clear, defensible, and aligned with your evaluation.
Common contribution types in optimization theses:
- Applied impact (company baseline): you beat the company status quo and explain why it matters (cost/service/robustness), with a realistic model and a reproducible pipeline.
- Algorithmic contribution (research benchmark): you match or beat SOTA on shared benchmarks (ideally with gaps to BKS), and you can justify why your mechanism works.
- Modeling contribution (new game): you define a more realistic variant (objective/constraints/uncertainty) and show how methods behave under the new rules.
- Experimental contribution: you provide a fair benchmark, strong baselines, and clean reporting (including negative results and ablations) that others can reuse.
- Data/benchmark contribution: you curate a dataset or an instance generator that represents a real operational setting, and you document it well enough that others can compare.
Pick one primary contribution (and maybe one secondary). Then make your evaluation match that claim.
The Horse Race (SOTA and BKS Benchmarks)
In optimization research, you are rarely the first person to face “your” problem. You are entering a horse race: an existing literature with established baselines, benchmark instances, and often best-known solutions. That is not a bad thing. It is what makes your evaluation credible.
Two terms you will see a lot:
- SOTA (state of the art): the strongest methods currently reported (or publicly available) under comparable settings.
- BKS (best-known solutions): the best objective values reported so far for a benchmark set. BKS is not automatically optimal, but it is the reference point the community uses.
If you cannot compute exact optima for realistic instance sizes, it is normal (and often expected) to benchmark against SOTA and to report how far you are from the BKS on standard instances.
Practical guidance:
- Match the protocol: instance set, time limits, machine, and number of runs (many heuristics are stochastic).
- Include strong baselines: if a benchmark has BKS and a known SOTA approach, use them; otherwise, be explicit about what you used as the best available comparison.
- Report gaps transparently: show objective values, relative gaps to BKS (when available), and runtime (not only “best run”).
- Be careful with “new best” claims: if you beat a BKS, double-check the instance definition, confirm the BKS source is up to date, and run multiple seeds/settings. Retracting a “new best” claim is embarrassing.
Two Benchmarking Leagues (Basic vs Advanced)
Most thesis projects end up playing in one of two “leagues.” Both can be excellent; they just make different claims.
Goal: show measurable improvement over the status quo (the way the company currently plans, decides, or schedules), using solid methods from the literature.
- Your main benchmark is the company baseline (and a clean “before/after” comparison).
- You can (and should) use SOTA ideas as your toolbox: you implement or adapt a well-established approach and show it works in this context.
- This is often feasible because real systems have plenty of low-hanging fruit (missing constraints, unclear objectives, weak baselines, no tuning, no sensitivity checks).
This league typically leads to a strong thesis when the work is well scoped, well evaluated, and clearly communicated. It is also the most common path in industry-connected projects.
Goal: demonstrate an algorithmic contribution by outperforming (or matching with clear advantages) the best published/known methods on standard instance sets.
- Your benchmark is SOTA on shared instances (and ideally gaps to BKS).
- You must be disciplined about fair comparisons: same instances, time limits, hardware reporting, multiple runs, and transparent parameter settings.
This is the “adults league” because it is genuinely hard: SOTA methods are strong, tuned, and tested. If you can credibly claim consistent improvements, the contribution is closer to publishable research. (Grading still depends on your examiner and the official rubric, but this kind of result is usually exceptional.)
How to Escape the Race (Create Your Own Game)
Sometimes the smartest move is not to sprint on an old track, but to explain why the track is wrong for your problem.
This also happens in industry-connected projects where the “company problem” is not a standard problem from the literature yet. The company may have a real planning process, but no public benchmark set, no established evaluation protocol, and no agreed-upon SOTA. In that case you are not only solving a problem; you are also defining it in a way that others can review and reproduce.
You “escape the horse race” by proposing a novel model (i.e., finding your niche) or novel evaluation setting that better matches reality, for example:
- A missing constraint that changes feasibility (e.g., labor rules, charging, service guarantees).
- A different objective that stakeholders actually care about (e.g., robustness, fairness, emissions, risk).
- A new uncertainty structure (e.g., demand volatility, travel-time distributions, cancellations).
- A new dataset/instance generator that reflects the operational context.
The key is to keep it scientific: define the new setting precisely, justify why it matters, and still include strong baselines (often by adapting SOTA to your new rules). In other words: even when you invent the game, you still need opponents.
Benchmarking when there is no public benchmark (typical in company work)
You can still benchmark rigorously, but you need to make your comparisons explicit and layered:
- Compare against reality (company baseline). Run your method on historical periods and compare against what the company actually did (cost, service level, emissions, robustness). Use the same information the company had at decision time (avoid “peeking into the future”).
- Use a simulator when reality is hard to replay. If the evaluation needs counterfactuals (what would have happened?) or many scenarios, build a simulation or scenario generator from company data and validate it against basic statistics and baseline performance.
- Create a “gold” reference when you can. Solve simplified/downscaled instances exactly (or compute tight bounds) to sanity-check the model and quantify optimality gaps for heuristics.
- Include “silver” baselines. Implement a reasonable heuristic baseline (even a simple constructive + local search) and/or adapt the closest SOTA method from the literature to your setting. Be explicit about adaptations and tune fairly (Barr, Golden, Kelly, Resende, & Stewart, 1995; Hooker, 1995).
- Tell a coherent story. A common structure is: Bronze (company status quo) -> Silver (strong heuristic/adapted SOTA) -> Your method, with Gold (exact/near-exact) wherever it is tractable.
Empirical Testing (How to Benchmark Without Drowning)
If your claim is performance (especially “we beat SOTA”), you need empirical evidence. The trick is to design experiments that are small enough to run, but strong enough to convince a critical reader.
Good computational experiments are a skill. They have well-known failure modes (unfair comparisons, hidden tuning on the test set), so be explicit about your protocol and report conditions transparently (Barr et al., 1995; Hooker, 1995).
A thesis-friendly testing workflow
Pilot (cheap screening)
- Pick a small, representative instance subset.
- Give each candidate the same time budget.
- Eliminate obvious losers and implementation mistakes early.
Tuning (training set only)
- Tune parameters on a training set.
- Decide your stopping rule and compute budget now (not later).
Final evaluation (frozen, held-out test set)
- Freeze the best configuration.
- Evaluate on instances that were not used for tuning.
- Report variability (multiple seeds/runs), not only the single best run.
What to report so results are reviewable
- Instances: where they come from, what they represent, and how many.
- Budgets: time limit, iterations, evaluations, and hardware.
- Randomness: number of runs, seeds, and summary statistics (median/mean + spread).
- Baselines: company baseline, literature baseline, and/or SOTA (depending on your league).
- Ablations (if you claim a new idea): show what happens when you remove the new component.
Freeze your algorithm and parameters before running the final test set. If you keep tuning while looking at test results, you are (accidentally) p-hacking (i.e., overfitting to the test set; “p” stands for “probability”). This invalidates your evaluation.
Negative Results (The Edison Principle)
Optimization research is full of negative results: ideas that sounded promising but do not survive fair benchmarking. That is normal.
“I have not failed. I’ve just found 10,000 ways that won’t work.” (often attributed to Thomas Edison)
The scientific value is not “I tried and it didn’t work.” The value is: under these conditions, this approach does not work, and here is the evidence and the boundary.
Negative results are also systematically underreported (the “file drawer” problem) (Rosenthal, 1979). In a thesis, you can counter that bias by writing negative results clearly and honestly.
One honest reason they are underreported: negative results are less glamorous (less “sexy”) than a new best result, so they are harder to publish and easier to leave out. A thesis has a fixed timeframe, so it is perfectly reasonable to report negative results if they meet the same standards of rigor and usefulness as any other result. (Talk to your supervisor if you are unsure.)
This is especially common in theses that apply learning methods (e.g., ML/RL combined with optimization): tuning can be slow, brittle, and data-hungry, and it is easy to spend weeks on hyperparameters without getting a stable improvement. If you hit that wall, document it and pivot strategically rather than hiding it.
When a negative result is a real contribution
A negative result is credible when:
- You compare against strong baselines with a fair protocol (see Empirical Testing above).
- You can explain the conditions (instance type, constraints, noise, scale) where it fails.
- You include at least one alternative that does work better (even if it is just a SOTA baseline).
A negative result is not credible when the failure is actually:
- An implementation bug,
- A weak baseline,
- A missing constraint that makes the comparison meaningless,
- Or tuning on the test set until something looks good.
How to write negative results (so they help the reader)
- State the hypothesis (“we expected SA to help because…”).
- Describe what you tested (instances, budgets, tuned parameters, baselines).
- Show the evidence (gaps, runtime, robustness; include variability).
- Diagnose the likely cause (search landscape, penalties, neighborhood strength, noise).
- Extract a design lesson (“this neighborhood needs X” / “penalties dominate” / “the bottleneck is evaluation cost”).