Reducibility
Glossary Contents
← Ch IX
Chapter X Undirected Hamilton Circuit
Ch XI →
  1. 28 — Tours without arrows
  2. 29 — Concurrent search in Elixir
  3. 30 — PCB drilling and 3D printing
30

PCB drilling and 3D printing

Anything where a tool head visits every spot once and returns home is a Hamilton circuit — usually with edge weights, making it the traveling salesman problem.

A printed circuit board has thousands of vias to drill. The drill bit has to visit each one and come home (to swap to the next bit, often). The tour length determines machine time, which is the dominant cost on a PCB line. The same shape — visit every point once, minimize travel — controls 3D printer head paths, CNC milling, semiconductor wafer probing, warehouse pick-paths, and chemistry-lab autosamplers. Concorde, the flagship academic traveling salesman solver, has solved instances with 85,900 cities (the design of a custom VLSI chip in 2006); commercial solvers like FICO Xpress and Gurobi handle 100K-point routing with branch-and-cut and Lin-Kernighan heuristics.

In plain terms

A 3D printer's nozzle has to lay down ink at every point in a layer. The faster it gets between points, the faster you finish. Picking the order to visit every point exactly once and return is the classic Hamilton circuit problem.

Scan to come back to page 30

End of Chapter X
Chapter XI 3-Satisfiability →
← 29 Concurrent search in Elixir
3/3 · 30/63
31 Three is enough →