CRT Scheduling

B11: Gurobi/CPLEX patents. CC0.

CRT approach to constraint satisfaction. A scheduling problem over N = 214,414,200 slots becomes 7 independent sub-problems over moduli {8, 9, 25, 49, 11, 13, 17}. Total per-channel checks: 8+9+25+49+11+13+17 = 132 vs 214.4M brute force. Search space reduction when constraints factor independently across channels.

How It Works

CRT Factored Search

Any integer in Z/214,414,200 is uniquely determined by its 7 residues. To find a slot satisfying 7 independent constraints (one per channel), solve each constraint in its own modular space. CRT reconstruction gives the unique solution. No backtracking. No heuristics. The 3+4 split: 3 data channels {mod 8, mod 25, mod 49} carry task data, 4 parity channels {mod 9, mod 11, mod 13, mod 17} carry scheduling metadata.

1,624,350x

Search space reduction

132 checks (sum of moduli) vs 214,414,200 (brute force).

Zero collisions

CRT guarantee

Distinct CRT tuples map to distinct slots. Algebraic, not probabilistic.

3+4 split

Data + metadata

3 data channels schedule tasks. 4 parity channels track constraints.

214.4M capacity

One ring

214,414,200 unique conflict-free slots from 7 small moduli.

Try It

Number of tasks (1-100):

Each task gets a unique CRT address. All pairs checked for collision. Red = data channels. Green = parity channels.

CRT Scheduling vs Constraint Solvers

Search spaceGurobi/CPLEX: N = 214.4M brute force + heuristicsCRT: 132 checks (sum of 7 moduli)GuaranteeBest-effort, may not find optimumAlgebraic: unique solution guaranteed by CRTCollisionsRequires conflict resolutionZero. Coprime moduli = orthogonal channels.ScalingNP-hard in generalLinear in number of moduli. Add primes to grow.Patent statusGurobi/CPLEX proprietaryCC0. Public domain. Forever.

Source code · Public domain (CC0)

Report issue

.ax source compiled to WASM via self-hosting compiler. Zero HTML authored.