Halgoworks

Drag to orbit. Click, then scroll to zoom.

Halgoworks: six optimization problems, solved step by step

Six classic optimization problems, solved in your browser by real algorithms written in C#. Pick one and watch every decision as it's made, with the reasoning spelled out.

Simulated annealing searching for the lowest valley. Uphill steps are accepted less often as it cools; red dots are rejected steps. The pin marks the deepest valley found so far.

Six problems, one question: what's the best choice?

Each asks for the best option among more possibilities than anyone could ever check. Four of them have no known fast exact method, so the labs show both exact algorithms and the shortcuts used in practice. The last two are the exceptions, and one is the other in disguise.

  • Vehicle routing

    Plan routes for a fleet of trucks delivering to many customers, within truck capacity and delivery deadlines, at the lowest fuel cost.

    Complexity
    NP-hard
    Used for
    Parcel delivery, Logistics, Fleet management
    Algorithms
    Clarke–Wright savings, sweep, nearest neighbor, 2-opt, simulated annealing, genetic algorithm
    Open the lab

  • Knapsack

    Choose the most valuable combination of items without going over a weight or budget limit.

    Complexity
    NP-hard
    Used for
    Budget allocation, Cargo loading, Investment selection
    Algorithms
    Dynamic programming, branch and bound, integer programming, greedy by density
    Open the lab

  • Job-shop scheduling

    Order operations on shared machines so every job finishes as early as possible, respecting each job's sequence.

    Complexity
    NP-hard
    Used for
    Manufacturing, Employee scheduling, Timetabling
    Algorithms
    Giffler–Thompson with six dispatch rules, tabu search
    Open the lab

  • Bin packing

    Fit items of different sizes into as few fixed-size containers as possible.

    Complexity
    NP-hard
    Used for
    Cloud server allocation, Warehouse packing, Memory management
    Algorithms
    Next, first, best and worst fit, sorted variants, integer programming
    Open the lab

  • Maximum flow

    Push as much as possible from a source to a sink through a network whose links have limited capacity.

    Complexity
    Polynomial time
    Used for
    Network bandwidth, Water distribution, Supply chains
    Algorithms
    Edmonds–Karp, Ford–Fulkerson, Dinic, push–relabel
    Open the lab

  • Bipartite matching

    Pair up as many members of two groups as possible, using only allowed pairs and nobody twice. Solved by turning it into a maximum flow.

    Complexity
    Polynomial time
    Used for
    Job assignment, Scheduling shifts, Reviewer assignment
    Algorithms
    Reduction to max flow: Edmonds–Karp, Ford–Fulkerson, Dinic; greedy for comparison
    Open the lab

Why checking everything is hopeless

Work needed to guarantee the best answer by brute force, as the problem grows: subsets for knapsack, groupings for bin packing, visiting orders for routing, machine orders for a 5-machine job shop. Max flow is plotted with Edmonds–Karp's polynomial bound instead, and it barely leaves the floor.

  • Vehicle routing
  • Knapsack
  • Job shop, 5 machines
  • Bin packing
  • Max flow (Edmonds–Karp)
10⁰ 10²⁵ 10⁵⁰ 10⁷⁵ 10¹⁰⁰ 14710131619Items, customers or jobs: One second at a billion checks per second The age of the universe at that speed

How to read a lab

Every lab works the same way, so once you've used one you can read them all.

  1. Pick an example

    Each lab opens on a hand-picked example. Switch to another one or generate a random instance.

  2. Choose an algorithm

    Exact methods, greedy rules and local search side by side, on the same instance.

  3. Play or step through

    Space plays and pauses, the arrow keys step one decision at a time. Drag the timeline to jump.

  4. Follow the amber

    Amber always marks what the algorithm is looking at right now: in the picture, in the narration and in the pseudo-code.