Singapore-based practical guides, tutorials and experiments in AI, computing, modelling, simulation, optimisation and quantum computing, with research notes and hands-on workflows.
Yes, combinatorial search explodes factorially. Relying on brute force crashes solvers on NP-hard jobs. See how greedy heuristics & Warnsdorff rules work →
Optimization Problems Explained: TSP, Job Shop Scheduling, and the Knight’s Tour
Three classic combinatorial problems, one shared story: search spaces that explode faster than brute force can follow, and the greedy heuristics engineers reach for instead.
The Knight’s Tour walkthrough on this blog treats the problem as a coding exercise: implement Warnsdorff’s heuristic, watch a knight visit every square exactly once, move on. But the Knight’s Tour belongs to a much larger family — combinatorial optimization problems, where the challenge isn’t computing an answer, it’s searching an astronomically large space of candidate answers for a good one. The Traveling Salesman Problem and Job Shop Scheduling are the two most-cited members of that family, and putting all three side by side makes clear why certain techniques keep reappearing across logistics, manufacturing, and chessboard puzzles alike.
1 · What Makes a Problem “Combinatorial”
A combinatorial optimization problem asks for the best arrangement, ordering, or assignment out of a finite but enormous set of possibilities. “Finite” is the misleading part — finite doesn’t mean small. The number of ways to order 20 cities is 20! (roughly 2.4 × 1018), and it only grows from there. Checking every possibility, brute force, is correct but useless: even a supercomputer evaluating a trillion arrangements per second would need decades for a 25-city tour.
This is the shared root of all three problems below. Each has a small, easily-stated rule for what counts as a valid solution, and a combinatorial explosion of candidates that satisfy the rule. The interesting work isn’t defining the problem — it’s finding a good answer without enumerating the haystack.
A useful vocabulary distinction: a problem is NP-complete if it’s among the hardest problems whose solutions can at least be verified quickly, and NP-hard if it’s at least as hard as those, whether or not verification is fast. TSP’s decision version (“is there a tour under length L?”) is NP-complete; its optimization version (“find the shortest tour”) is NP-hard. Job Shop Scheduling is NP-hard. The Knight’s Tour is a special case that, unusually, isn’t — more on that in Section 4.
2 · The Traveling Salesman Problem
Given a list of cities and the distances between each pair, find the shortest possible route that visits every city exactly once and returns to the start. First studied formally in the 1930s, TSP is the problem most people picture when they hear “NP-hard” — partly because it maps so cleanly onto real logistics: delivery routing, PCB drilling paths, DNA sequencing fragment assembly, even warehouse pick-path optimization all reduce to some variant of TSP.
The number of distinct tours for n cities is (n−1)!⁄2 — for just 15 cities, that’s over 43 billion routes. Exact solvers exist (branch-and-bound, cutting planes, integer linear programming) and can handle surprisingly large instances — the Concorde TSP solver has certified optimal tours for problems with tens of thousands of cities — but they can take unbounded time in the worst case. In practice, most applications use heuristics instead:
Problem
Complexity & Dominant Heuristic
Real-World Domain
TSP
NP-hard · Nearest neighbor, 2-opt
Logistics, delivery routing, circuit layout
Job Shop Scheduling
NP-hard · Dispatching rules, genetic algorithms
Manufacturing, semiconductor fabs, server tasks
Knight’s Tour
Tractable Hamiltonian path · Warnsdorff’s rule
Puzzle games, path planning, robotic arm trajectories
The pattern across all three: a greedy, locally-informed rule — go to the nearest city, dispatch the shortest job first, move to the most-constrained square — gets surprisingly close to optimal, surprisingly fast, with no guarantee it always will. Exact methods (branch-and-bound, ILP, constraint solvers) remain necessary when the application genuinely needs a certified optimum or a worst-case bound, but for most production systems, a well-tuned greedy heuristic plus local-search refinement is the pragmatic default.
6 · When to Reach for Which Tool
Small instance, need the true optimum: exact solvers — branch-and-bound, integer linear programming, or off-the-shelf constraint solvers (OR-Tools, Gurobi, CPLEX).
Large instance, “good enough” is genuinely good enough: a simple greedy heuristic, ideally with a known worst-case bound if one exists for the problem.
Large instance, need better than greedy but exact is too slow: metaheuristics — simulated annealing, genetic algorithms, tabu search — layered on top of a greedy starting solution.
Your instance has exploitable structure (like the knight’s-move graph’s regularity): look for a problem-specific rule before reaching for general-purpose machinery. The cheapest algorithm is the one that exploits structure the general theory doesn’t assume.
7 · Related Publications from the Author
The full line of the author’s own published research on TSP and Job Shop Scheduling, drawn from the Publications page, spans nearly two decades of bee-colony and neural-network approaches to both problems:
Traveling Salesman Problem
Wong, L.P., Low, M.Y.H., Chong, C.S. (2008). “A Bee Colony Optimization Algorithm for Traveling Salesman Problem.” 2nd Asia Modelling Symposium (AMS 2008), 818–823, Kuala Lumpur, Malaysia.
Wong, L.P., Low, M.Y.H., Chong, C.S. (2008). “Bee Colony Optimization with Local Search for Traveling Salesman Problem.” 6th IEEE International Conference on Industrial Informatics (INDIN08), 1019–1025, Daejeon, Korea.
Wong, L.P., Low, M.Y.H., Chong, C.S. (2009). “A Bee Colony Optimization Algorithm with the Fragmentation State Transition Rule for Traveling Salesman Problem.” 4th Virtual International Conference on Intelligent Production Machines and Systems (IPROMS).
Full author bibliography, including book chapters and the remaining 130+ conference and journal papers spanning simulation, crowd modeling, and manufacturing systems, is available on the Publications page.
None of these three problems has been “solved” in the sense of a fast, exact, general algorithm — and for TSP and Job Shop Scheduling, complexity theory says no such algorithm exists unless P = NP. What they share instead is a body of heuristics, decades deep, that trade a small, usually-acceptable gap from optimal for a massive reduction in compute time. The Knight’s Tour is the outlier that got lucky: enough structure in its specific graph that a two-line greedy rule does the job outright.
Leave a Reply