Protocol Update 0.0.5 Summary

Protocol Enhancements
1

This update introduces three changes to the TIG protocol:

  1. Tracks are now randomly assigned per benchmark
  2. Addition of a new challenge: Job Shop Scheduling (JSS)
  3. Updates to several existing challenges, including new Knapsack tracks, an upgraded SAT track, and a change in the Neural Net Optimiser challenge.

1. Randomising Tracks

Benchmarkers will no longer choose which track to benchmark. Instead, tracks will be randomly assigned. Per benchmark, benchmarkers will commit to:

  • an algorithm; and
  • track settings: a mapping from track id to hyperparameters, the number of bundles, and the fuel budget for that given track.

For example:
For example, in the VRP challenge, algorithm hgs_v1:

"track_settings": {
        "n_nodes=600": {
                    "num_bundles": 4,
                    "hyperparameters": '{"exploration_level": 3}',
                    "fuel_budget": 123456
                    },
        "n_nodes=700": {
                    "num_bundles": 4,
                    "hyperparameters": '{"exploration_level": 3}',
                    "fuel_budget": 123456
                    },
        ... 
        }
"algorithm_id": "c002_a089"

This change aims to restore benchmarkers signalling the best algorithm per challenge, rather than per track.

Expected Effects on Innovators

As a result of this change, all algorithms submitted to a given challenge will be tested across all tracks. This is expected to incentivise “meta-algorithms”. Either general-purpose algorithms that perform well across tracks, or composite algorithms that identify the track and apply appropriate subroutines.

2. New Challenge: Job Shop Scheduling

This update introduces a new Job Shop Scheduling (JSS) challenge based on the Flexible Job Shop Scheduling Problem (FJSP), a well-studied and practically relevant class of scheduling problems.

In this challenge, a set of jobs must be processed on a set of machines. Each job consists of a sequence of operations that must be completed in order. For each operation, there may be one or more machines capable of processing it, and the processing time can depend on the chosen machine. The objective is to minimize the makespan, i.e. the time at which the last job finishes.

Each track represents a different scheduling environment generated from the same underlying instance generator, spanning from structured flow-shop settings to highly flexible job-shop variants. The different track parameters are: the number of
jobs, n, the number of machines, m, the number of operation types, o, and the flow type.

The tracks available to benchmark will be:

n=50,m=30,o=30,flow=flow_shop
n=50,m=30,o=30,flow=h_flow_shop
n=50,m=30,o=30,flow=job_shop
n=50,m=30,o=30,flow=fjsp_med
n=50,m=30,o=30,flow=fjsp_high

Track summaries

  • Flow Shop: All jobs follow the same stage order; the main challenge is sequencing under a fixed production flow.
  • Hybrid Flow Shop: A flow-shop structure with parallel machine options at stages; emphasizes balancing load while maintaining a fixed flow.
  • Job Shop: Jobs can have different routes through the shop; emphasizes complex sequencing across heterogeneous job pathways.
  • FJSP (Medium): Flexible job shop instances with moderate flexibility; requires jointly deciding machine assignment and operation sequencing.
  • FJSP (High): Highly flexible, highly combinatorial instances; strongly rewards robust assignment + sequencing strategies that generalize across varied structures.

3. Challenge Updates

New Knapsack Tracks

The Knapsack challenge is transitioning from standard QKP instances to Team Formation QKP instances, based on recent work by Hochbaum et al [^1]. This introduces more realistic, structurally rich instances. The following tracks will be featured on the protocol:

n_items = 1000,budget = 5  
n_items = 1000,budget = 10  
n_items = 1000,budget = 25  
n_items = 5000,budget = 10  
n_items = 5000,budget = 25

SAT Challenge Track Update

SAT track n_vars=100000, ratio=410 is being increased in difficulty to ratio=420, moving closer to the phase transition ratio of 4.267 where the hardest instances exist.

Neural Net Challenge Update

The weights in the neural net optimiser challenge are now being made visible to the optimizer step function. This change enables optimizers to adapt updates based on the actual parameter landscape, bringing the challenge closer to real-world training dynamics.