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 × 10¹⁸), 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.

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:

Beyond hand-designed heuristics, a large body of research applies metaheuristics — genetic algorithms, ant colony optimization, bee colony optimization — to push closer to optimal on large instances. One example: Choong, Wong, Low & Chong, “A Bee Colony Optimization Algorithm with a Sequential-Pattern-Mining-based Pruning Strategy for the Traveling Salesman Problem,” International Journal of Bio-Inspired Computation, 15(4), 239–253 (2020), which uses sequential pattern mining to prune the search space a bee colony algorithm explores, improving both solution quality and runtime over earlier bee colony variants on standard TSP benchmarks. Section 7 below lists the full line of TSP research this paper builds on.

Most of the field trades a provable worst-case guarantee away for speed, accepting “probably close to optimal, verified empirically on benchmark instances” instead — which is exactly the trade-off metaheuristic approaches like the one above are built around.

3  ·  Job Shop Scheduling

A set of jobs, each made of an ordered sequence of operations, must run on a shared set of machines. Each machine can only process one operation at a time, and each job’s operations must run in their specified order. The goal is usually to minimize makespan — the total time until every job finishes. This is the workhorse problem behind semiconductor fab scheduling, shipyard and manufacturing floor planning, and container terminal crane assignment — anywhere shared, expensive resources have to be sequenced across competing demands.

Even the deceptively small “3 jobs × 3 machines” instance can take meaningful compute time to solve exactly, and general Job Shop Scheduling is NP-hard — confirmed by Garey, Johnson, and Sethi in 1976. The search space is every valid interleaving of operations across machines respecting precedence constraints, which grows combinatorially with both job count and machine count simultaneously, faster than TSP’s single-dimension city count.

Unlike TSP, there’s no single dominant heuristic with a well-known worst-case bound — the field leans heavily on metaheuristics, learned dispatching policies, and problem-specific rules tuned empirically to the shop floor in question.

4  ·  The Knight’s Tour — the Odd One Out

A knight on a chessboard must visit every square exactly once using only legal knight moves. As covered in the Codex CLI walkthrough, this is a special case of the Hamiltonian path problem: model each square as a graph node, connect two nodes if a knight can move between them in one hop, and a Knight’s Tour is exactly a Hamiltonian path through that graph.

Finding a Hamiltonian path in an arbitrary graph is NP-complete — it belongs in the same hardness class as TSP’s decision version. But the knight’s-move graph on a chessboard isn’t arbitrary; it has enough regular structure that a simple greedy rule, Warnsdorff’s rule (always move to the unvisited square with the fewest onward moves), finds a complete tour almost every time on boards 5×5 and larger, in linear time, with no backtracking needed in the overwhelming majority of cases.

The general Hamiltonian-circuit problem — not restricted to a knight’s-move graph — is itself a live research target for the same metaheuristic techniques used on TSP: Wong, Low & Chong, “Finding the Shortest Hamiltonian Circuit of Selected Places in Penang Using a Generic Bee Colony Optimization Framework,” BIC-TA 2011, 51–57 applies a bee colony framework to find the shortest Hamiltonian circuit connecting real-world locations — the same underlying graph-theory object the Knight’s Tour is a highly structured special case of.

5  ·  What the Three Have in Common

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).
• Wong, L.P., Low, M.Y.H., Chong, C.S. (2009). “An Efficient Bee Colony Optimization Algorithm for Traveling Salesman Problem using Frequency-based Pruning.” 7th IEEE International Conference on Industrial Informatics (INDIN09), 775–782, Cardiff, UK.
• Wong, L.P., Low, M.Y.H., Chong, C.S. (2010). “Bee Colony Optimization with Local Search for Traveling Salesman Problem.” International Journal on Artificial Intelligence Tools, 19(3), 305–334.
• Wong, L.P., Low, M.Y.H., Chong, C.S. (2011). “Finding the Shortest Hamiltonian Circuit of Selected Places in Penang Using a Generic Bee Colony Optimization Framework.” International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2011), 51–57, Penang, Malaysia.
• Choong, S.S., Wong, L.P., Low, M.Y.H., Chong, C.S. (2020). “A Bee Colony Optimization Algorithm with a Sequential-Pattern-Mining-based Pruning Strategy for the Traveling Salesman Problem.” International Journal of Bio-Inspired Computation, 15(4), 239–253.

Job Shop Scheduling

• Chong, C.S., Low, M.Y.H., Sivakumar, A.I., Gay, K.L. (2006). “A Bee Colony Optimization Algorithm to Job Shop Scheduling.” 2006 Winter Simulation Conference, 1954–1961, Monterey, CA.
• Chong, C.S., Low, M.Y.H., Sivakumar, A.I., Gay, K.L. (2007). “Using a Bee Colony Algorithm for Neighbourhood Search in Job Shop Scheduling Problems.” 2007 European Conference on Modelling and Simulation, 459–465, Prague, Czech Republic.
• Wong, L.P., Puan, C.Y., Low, M.Y.H., Chong, C.S. (2008). “Bee Colony Optimization Algorithm with Big Valley Landscape Exploitation for Job Shop Scheduling Problems.” 2008 Winter Simulation Conference, 2050–2058, Miami, FL.
• Wong, L.P., Puan, C.Y., Low, M.Y.H., Chong, C.S., Wong, Y.W. (2010). “Bee Colony Optimisation Algorithm with Big Valley Landscape Exploitation for Job Shop Scheduling Problems.” International Journal of Bio-Inspired Computing, 2(2), 85–99.
• Sim, M.H., Low, M.Y.H., Chong, C.S., Shakeri, M. (2020). “Job Shop Scheduling Problem Neural Network Solver with Dispatching Rules.” 2020 International Conference on Industrial Engineering and Engineering Management (IEEM2020), Singapore.
• Yang, Z., Liu, F., Zhang, W., Lou, X., Low, M.Y.H., Gan, B.P. (2026). “LLM-Upgraded Graph Reinforcement Learning for Carbon-Aware Job Scheduling in Smart Manufacturing.” 41st ACM/SIGAPP Symposium On Applied Computing, 831–838, Thessaloniki, Greece.

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.