Compute Crunch

Act 1: Route the world

The cities and data centers are real places. Demand, power prices, and carbon intensities are examples chosen for the puzzles. Latency estimates use the great-circle distance between locations, multiplied by 1.4 to allow for bends in the fiber route, with signals traveling at two thirds the speed of light.

The linear program

The solver assigns compute from data centers to cities, measured in megawatts. Each site has a capacity limit, and routes over the latency limit are ruled out. Any city demand left unserved costs $1,400 per megawatt-hour. Training can go to any site, with a $500 per megawatt-hour penalty for leaving it until later.

minimize

• Σ price · x + 1400 · unserved + 500 · unserved training

subject to

• Σ x into each city + unserved = demand
• Σ x out of each site ≤ capacity
• Σ carbon · x ≤ cap chapter 2
• x ≥ 0, only on routes within the latency limit

The solver

A Python service runs GLOP, the linear solver in Google’s OR-Tools, to find the cheapest allocation. GLOP also returns dual values: the rate at which the cost changes when a limit is relaxed. The savings shown here come from solving the problem again with one extra megawatt at a site or one extra tonne under the carbon cap, then comparing the two costs.

Adding capacity

Chapter 3 lets you build capacity in 25 MW blocks. SCIP solves the integer program that decides where to build, then GLOP assigns the compute. The cost of each block counts toward the score, so a new block needs to save more than it costs.

All compute is interchangeable in this model. GPU types, network capacity, queueing, and fairness aren’t included.

Act 2: Data Center Alley

The network comes from OpenStreetMap’s 230 kV and 500 kV lines in Loudoun County, simplified to two 500 kV hubs and seven substations. The locations and line lengths come from the map. Line limits, loads, prices, and land costs are made up for the puzzles; the map doesn’t tell us how much spare capacity a substation has.

Power flow uses the DC approximation. Flow on a line is the difference in voltage angle between its ends, divided by its reactance. Here, reactance is proportional to line length. Power splits across the available paths, so you can’t choose a single route for it to take. A line at its limit can prevent you from supplying more power elsewhere.

minimize

• Σ price · supply + 1400 · dark + Σ land · campus + Σ cost · new line

subject to

• supply − load + dark = flow out − flow in, at every bus
• flow = (θa − θb) / km, on every line in service
• −limit ≤ flow ≤ limit
• each campus on exactly one substation chapter 1
• each line in or out of service, at most one new chapter 2

The solvers

SCIP chooses where to place campuses and which lines to build or take out of service. Both are mixed-integer problems. A big-M constraint lets the model drop a line’s flow equation when it is out of service. Once those choices are fixed, GLOP solves the power flow again. To measure how much a particular choice helped, the solver runs again with the alternative forced in, or with the opened breaker closed.

Chapter 2 shows Braess’s paradox. A new line can create a loop that pushes more power onto an already full line, making the result worse. Taking a line out can help for the same reason. Choosing which lines to keep in service is called optimal transmission switching.

The search replay

SCIP uses branch and bound for the integer decisions. To make the replay, the service repeats the same deterministic search, stopping after one solution, then two, then three, and so on. It records each plan, the lower bound on cost at that point, and SCIP’s elapsed time.

Act 3: Campuses keep coming

This uses the same grid as Act 2, with all four years from 2027 to 2030 planned together in one mixed-integer program. You choose when each project starts, but it only adds capacity after construction finishes. One crew can start one project each year. Turbine rentals are chosen year by year; in the last chapter, breaker settings are too. The score is the average hourly cost across the four years. Lead times, costs, and campus sizes are examples for the puzzles.

Act 4: Who signs?

You order turbines before knowing which customers will sign. Once the signings are known, you can place a limited number of rush orders. These two rounds of decisions make this a two-stage stochastic program. The initial order and its cost are the same in every scenario; rush orders depend on what happens.

Chapter 1 compares a plan made for average demand with one that accounts for each possible outcome and its probability. The difference in expected cost is the value of the stochastic solution. Chapter 2 minimizes the cost of the worst outcome, using robust optimization. Chapter 3 asks how much you could save if you knew who would sign before ordering. It compares the best advance order with separate plans for each outcome, weighted by their probabilities. That saving is the expected value of perfect information.

Sources

• Dietrich Braess, “Über ein Paradoxon aus der Verkehrsplanung,” Unternehmensforschung 12 (1968): 258–268. The original statement of Braess’s paradox, for road traffic.
• Dirk Witthaut and Marc Timme, “Braess’s paradox in oscillator networks, desynchronization and power outage,” New Journal of Physics 14 (2012): 083036. Braess’s paradox in power grids.
• Emily B. Fisher, Richard P. O’Neill, and Michael C. Ferris, “Optimal transmission switching,” IEEE Transactions on Power Systems 23, no. 3 (2008): 1346–1355.
• John R. Birge, “The value of the stochastic solution in stochastic linear programs with fixed recourse,” Mathematical Programming 24 (1982): 314–325.
• John R. Birge and François Louveaux, Introduction to Stochastic Programming, 2nd ed. (Springer, 2011).
• Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski, Robust Optimization (Princeton University Press, 2009).
• Map data © OpenStreetMap contributors, available under the ODbL.