OEvent Course Helper

A low-level solver for the NP-hard real-world logistics problem of test-running orienteering courses before an event ensuring all control points are visited with the minimum amount of volunteer effort.

Performance and Statistics

This project is an exercise in falling down the performance rabbit hole while writing C#. Once the core engine reached a satisfactory state, I benchmarked its performance on a synthetic dataset of 100,032 nodes and 5,000 paths. The evaluation used a heuristic-guided beam search algorithm with a beam width set to 10. Under these conditions, the engine solved the NP-hard problem in an average time of 4.6 seconds across 16 runs on an AMD Ryzen 9 9900X3D processor (Windows, NativeAOT). Interestingly, compiling to standard IL and running under the runtime JIT is roughly 0.8 to 0.9 seconds faster (total ~3.7 seconds) because JIT PGO can perform dark magic on long-running loops.

I chose to report the NativeAOT metric since that’s how the application will be shipped. It is shipped as NativeAOT because a typical real-world dataset often only includes around 80 nodes with 30 paths and with that dataset size NativeAOT wins and executes the core engine in an average of 0.237 milliseconds.

The profiling is only done on the core engine (OEventCourseHelper.Core) and does not include file read, XML parsing, or terminal I/O latency.

Building the Core Engine

The core engine originated as a single-day prototype to solve a pressing logistics problem: calculating the optimal set of orienteering courses to test-run before an event so volunteers visit every control point with minimal running distance. The initial version relied on naive HashSet and Dictionary lookups, but once the domain logic was validated, the focus pivoted toward a systems engineering challenge: proving that managed C# on .NET 10 can deliver bare-metal efficiency without sacrificing clean architecture.

To keep the codebase lean, robust, and deterministic, the core engine is governed by seven strict design principles prioritized in exact order:

1. Algorithmic Elegance over Brute Force: No multithreading or parallel compute hacks. Problems are solved through intelligent domain heuristics and search-space reduction rather than raw hardware saturation.
2. Strict Immutability: State outside the active working set is strictly read-only.
3. Absolute Determinism: Identical input datasets will always produce identical execution paths and results.
4. Minimal Memory Footprint: Highly compact, cache-friendly data structures keep allocations to a minimum.
5. Maintainability by Design: A modular architecture keeps the domain logic readable and extensible.
6. High Testability: Heavy reliance on pure functions makes core algorithms straightforward to unit-test and verify.
7. Maximized Performance: Throughput and execution speed are pushed as far as possible without violating principles 1 through 6.

Solving Set Cover via Beam Search

Finding the minimum number of courses required to cover all controls is a variation of the NP-hard Set Cover problem. Instead of an exhaustive search space traversal, the core engine isolates solutions using three targeted techniques:

• Dominated Course Pruning: Before search evaluation begins, any course whose control coverage is fully subsumed by another equal-or-better course is discarded, instantly shrinking the problem graph.
• Rarity-Score Heuristic: Controls that appear on very few courses are given higher evaluation weights. The solver prioritizes paths that resolve these hard-to-reach controls early.
• Beam Search Trimming: At each layer of the search tree, only the top candidate states bounded by the beam width (configured via -w/--beam-width) are preserved, preventing state-space explosion while maintaining near-optimal accuracy.

By combining structural immutability with aggressive pruning, OEventCourseHelper.Core executes entirely within low-memory bounds, making it ideal for high-throughput batch processing and CLI utility runs.

Why Beam Search?

Set Cover is NP-hard, meaning finding a guaranteed optimal solution through exhaustive search requires exploring an exponentially growing decision tree. Standard approaches fall into two extremes:

• Greedy Search: Extremely fast, but easily trapped in local minima. A purely greedy approach selects courses with the highest immediate control count. This often leaves isolated controls behind, forcing the algorithm to append many redundant, single-control courses late in the search.
• Exhaustive Search / $A^{\ast }$: Guarantees absolute optimality, but memory usage scales exponentially ($O(b^d)$). On large datasets like the 100,000-node benchmark, state-space expansion causes out-of-memory crashes, violating Commandment #4 (Minimal Memory Footprint).

Beam Search provides the necessary balance. By evaluating and maintaining $B$ active candidate trajectories simultaneously, memory usage scales predictably and linearly ($O(B\cdot d)$) relative to search depth.

On a personal note, I also thought the name ‘Beam Search’ sounded cool, and having never implemented it before, this was the perfect excuse to give it a try.

Execution & Greedy Exit Mechanics

The custom beam search implementation combines candidate expansion with a greedy exit condition:

1. Parallel Track Evaluation: At every depth level, the engine expands and scores candidate choices across $B$ distinct paths using the control-rarity heuristic.
2. First-Completion Exit: The search terminates immediately as soon as the first active beam path fully satisfies all control requirements.
3. Escaping Local Minima: Keeping $B$ paths alive prevents the solver from getting tricked by high immediate yields. A path that looks fantastic on step one might stall out and require 10 additional courses to clean up leftover controls. Meanwhile, a beam that starts with a seemingly “worse” initial course might find a clean trajectory that reaches 100% coverage in only 9 total levels.

Exposing the beam width parameter (-w) puts the trade-off directly in the user’s hands: small beam widths offer sub-millisecond execution for standard local events, while larger widths allow deeper path exploration on massive synthetic datasets.