Stop searching for the exact tour

You are about to hire another analyst, or slip the launch another week, so the field-visit route, the mentor assignment, or the constraint-heavy calendar can come out exact.

Do not. Some problems have no known efficient exact algorithm. The engineer move is an approximation or a tractable special case, not a longer search.

Twenty-two agro-dealers across Mukono, Jinja and Iganga. One van. Back to the Kampala depot before dark. That is a tour. Joining those same sites so every shop can raise a WhatsApp flag to a hub is a tree. They look alike on a whiteboard. They are not the same problem.

Why these three models

The decision is whether to keep hiring, or keep delaying, until the exact routing, mentor assignment, or launch week appears. The search space outgrows the week. Many peaks look locally finished. The launch date burns while you search. The class has a written history.

Three lenses, three outcome types. Rugged-landscape search is the complex answer: interacting choices produce many local peaks, and cheapest connect-all is not visit-and-return. An annealing schedule is the random answer: once hardness is accepted, the policy is noise that cools. Base rates are the cycle answer: this class runs a fruitless exact search, then a late heuristic. That span is the point.

The computational bound is not a fourth card. It is held as an identity, so it is stated in prose and cited. The instinct that this launch is special sits inside the base-rate card. Who may declare a route good enough sits in the adoption line. LOOP is folded: the districts have a next period, but the lever is the stop rule.

1. The terrain: connecting is not visiting

Name the object first. Most teams optimise the wrong one.

Cormen, Leiserson, Rivest and Stein define the cheap connect-all as a minimum spanning tree: an acyclic subset of the edges that connects every vertex at minimum total weight. Because it is acyclic and connects everyone, it must form a tree.³ Wiring pins, laying the cheapest radio mesh, standing up a partner hub so every district can report: those are trees. Kruskal and Prim solve them. The greedy step is legal.

Needham and Hodler write a looser when-box. Quote it as they wrote it. This is the sentence operators actually read:

Use Minimum Spanning Tree when you need the best route to visit all nodes. Because the route is chosen based on the cost of each next step, it’s useful when you must visit all nodes in a single walk. It’s also employed to approximate some problems with unknown compute times, such as the Traveling Salesman Problem. Although it may not always find the absolute optimal solution, this algorithm makes potentially complicated and compute-intensive analysis much more approachable.⁴

The first sentence is the trap. The tree is not the tour. A spanning tree lets you drop an edge you will still have to drive twice, or it skips the return to the depot. Needham’s later clause is the honest use: MST approximates a tour. It does not produce one.

Sriraman Sridharan and R. Balakrishnan state the tour. A salesman starts at city 1, visits each city exactly once, and returns, at minimum total cost. That is a cheapest Hamiltonian cycle. The number of such tours, counting a route and its reverse as one, is (n minus 1) factorial, divided by two.⁵ At 8 sites that is 2,520. At 12 it is about twenty million. At 22 agro-dealers it is not a spreadsheet.

That is why the terrain is rugged. Rivkin and Siggelkow, on NK-style organisational search: when components interact richly in determining fitness, local peaks are numerous.⁹ Swap Iganga and Jinja and the kilometres fall. Swap the depot return and they rise. You can walk uphill for days and never be on the global tour. A hierarchy can also freeze off a peak, at a sticking point created by delegated choices and mismatched local incentives.⁹ The district lead, the van owner, and the mentor each protect their own day. The calendar locks.

Read the live work against that split before you hire. Join sites so every one can report: MST, ship Prim. A van that visits and returns: the travelling-salesman problem, NP-complete, no known efficient exact algorithm.¹ One mentor to one cohort on a qualification list: bipartite matching, tractable. Add “each mentor visits four sites in five days and sleeps in Gulu on Wednesday” and you have written vehicle routing. The extra sentence changed the class.

Rugged-landscape, the complex lens

• Assumes: interacting choices create many local peaks. A tree and a tour are different objects.
• Fits because: routing, mentor weeks, and launch calendars couple stops and constraints.
• Breaks when: the instance is a special case, n is small enough to list, or the job is only to connect sites.
• Evidence: grade B. Geometry is textbook. Founder transfer is analogical.
• Counteracts: treating a locally improved week as the exact tour.
• May reinforce: a long jump when a district split already made the case small.

2. The temperature: keep some bad moves, then cool

Once the class is hard, you still need a search policy. “Try harder” is not one.

Kirkpatrick, Gelatt and Vecchi built that policy from annealing steel. Iterative improvement, the thing your analyst already does, accepts only rearrangements that lower cost. That is a quench. It sticks in a local, not a global, optimum. Simulated annealing melts the system at a high effective temperature, then lowers the temperature by slow stages until it freezes. At nonzero temperature, transitions out of a local optimum remain possible. Gross features appear while it is hot. Fine details appear as it cools. That sequence is an annealing schedule.⁷ Accept a worse neighbour early so you are not buried in Monday’s greedy.

Miller and Page carry the same schedule into a social search. Better mechanisms introduce noise when local preferences are still mixed, and reduce it as people become more alike: the choice mechanisms should cool, anneal, the system. Allowing cheap or early mistakes helps a system leave an inferior outcome.⁸ The transfer is analogical. The shape still holds: noise proportional to remaining uncertainty, then a dated cooling step.

Write it onto the week you have. Hot, first three days: try a different district order. Send the van Mukono-Iganga-Jinja and the reverse. Move the Luganda-speaking mentor onto the school cell she was not supposed to touch. Record kilometres and WhatsApp complaints. Cool, after the skeleton exists: only adjacent swaps. Freeze the region order. You are polishing, not searching.

Too-fast cooling locks the first spreadsheet that covers every site. Too-slow cooling is still exploring the sequence the morning the fellows arrive. Name the cool-down date in the same sitting as the first experiment. If a mentor quits, reheat that region only.

Sridharan then gives you an approximation that can sit under the schedule. Nearest neighbour, under the triangle inequality, stays within one-half of (log2 n plus 1) times the exact tour. The MST-shortcut method (double the tree, walk an Eulerian cycle, take shortcuts) stays under twice the exact cost.⁶ Those are the “good but not best” solutions the textbooks tell an engineer to spend time on.

Annealing-schedule, the random lens

• Assumes: noise should track remaining uncertainty and fall as the sort improves.
• Fits because: hardness is accepted. The missing piece is the policy.
• Breaks when: the terrain shifts faster than you cool, a move can ruin you, or the problem is single-peaked.
• Evidence: grade B+. Kirkpatrick is A on the method. Organisational transfer is analogical.
• Counteracts: freezing Monday’s greedy and calling it the plan.
• May reinforce: a search that never cools, if nobody writes the date.

3. The usual path: the search does not finish

Before you treat this launch as the instance that will yield, look at the class.

CLRS is blunt about what happens when someone is asked for an efficient exact algorithm on an NP-complete problem. You are likely to spend a lot of time in a fruitless search. If you can show the problem is NP-complete, spend the time instead on an efficient method that gives a good, but not the best possible, solution. Their picture is a delivery company: trucks leave a depot, visit addresses, and must return so they can load tomorrow. That is the travelling-salesman problem. It is NP-complete. It has no known efficient algorithm. Under certain assumptions there are efficient methods whose distance is not too far above the smallest possible.¹

Chapter 34 restates it as an engineering rule. Establish the problem as NP-complete and you have good evidence for its intractability. As an engineer you then do better to develop an approximation, or solve a tractable special case, rather than search for a fast exact algorithm. They add the hedge: the possibility that every NP-complete problem is solvable in polynomial time cannot be ruled out.² That hedge is not a licence to keep hunting. It is a reminder that the bound is shared and empirical.

Kirkpatrick, in 1983, already said the bound in operator language. No method for an exact solution with effort bounded by a power of n had been found for any problem in the class. All exact tour methods then known grew exponentially.⁷ Later solvers have pushed the size a laboratory can finish. They have not given your two-week hire a polynomial algorithm. Match the class, not the industry. Delaying a fellowship week to assign mentors, and delaying dispatch to find the perfect loop, are the same decision in different clothes.

The inside view says this week is different because you know the roads and the fellows. Knowing the instance does not change the class. What usually happens is stable. The exact tour is not delivered. A heuristic is used anyway, after the window has moved. The hire does not fail because the person is weak. The brief asked for a polynomial exact method that the field has not found. Exact search on this class does not finish on a launch calendar. Approximations and special cases do. Sridharan defines an approximation by a bounded ratio against the unknown exact value, then gives two that meet it.⁶ Import that record. Refuse last quarter’s feeling that one more week would have done it.

Base rates, the cycle lens

• Assumes: cases matched on class, not on sector, share an intervention record.
• Fits because: NP-complete planning has a written history of fruitless exact search.
• Breaks when: a rule change puts you in a special case, or n is small enough that listing is the method.
• Evidence: grade A as a method. Class record is textbook. Founder-delay record is directional.
• Counteracts: the inside view that this launch is the instance that yields.
• May reinforce: copying a laboratory solver culture that had months and a machine.

Name the class before you write the job spec

Draw the boundary first. Inside: this week’s routing, assignment, or calendar, and the search time you are about to buy. Outside: whether the product is right, whether the fellows should exist, whether the van should be replaced by bodas paid per drop. Those are a different class. You have agreed to be surprised by them.

The stock you can move is unused launch calendar. You cannot set “a better route.” You can stop the outflow of launch days. The lag is why the hire feels free. The analyst starts on Monday. The missed week is discovered when the venues are already booked.

Cheapest and most reversible first.

1. Write the object in one sentence. Tree, tour, one-to-one assignment, or vehicle routing. If two people disagree, you have a caption, not a problem.
2. If it is a tour, split by district before you search. Eight sites inside Jinja is 2,520 tours. Twenty-two across three districts is not.
3. Pick the approximation in writing. Nearest neighbour inside each district, or MST-shortcut if you already have the tree. Date the cool-down.
4. Do not hire against an exact brief. If the job says “find the optimal route,” you have already chosen the fruitless search. Rewrite it to “ship a district-split nearest-neighbour by Friday.”

RADAR: what to put on the road before the week locks

Do now, by T+3, one afternoon, effect visible the same week. Classify the live problem as tree, tour, matching, or vehicle routing. If it is a tour, run nearest neighbour on each district and write the cool-down date. Reversible: you can throw the first tour away. The effect arrives when the van is booked against that list.

Hedge, by T+14, premium is one spare field day, cover live before the first overnight. Leave one empty afternoon and one unused seat in the van. A bad approximation then costs a rearrangement, not a missed cohort. The cover has to exist before the first night out.

Defer and trigger, size declared when the trigger is set. A new analyst, or a slipped launch, is the irreversible spend. Pre-commit the observable: two consecutive weeks where a district-split heuristic leaves a documented coverage hole that an adjacent swap cannot close, and n in that district is still too large to list. Until both are true, you do not hire and you do not slip. You do not need a better analyst. You need a different problem.

CHAIN: why the next delay will look like the last one

Name the shape before you explain this week. A search with no stop rule is goal-seeking that never arrives. The goal is “exact.” The gap never closes, so the correction never ends.

Has a rule changed, has an actor entered or left, has a measurement become a target? The last one fires. If “every site visited in an optimal order” is now what the board is told, last year’s link between search time and launch quality describes a different process.

If nothing broke, take the class from the textbooks, not from last year’s logistics anecdote. Tour-shaped planning, assignment quietly turned into routing, calendars with interacting constraints. The record is the one CLRS wrote down: fruitless exact search, working approximations, tractable special cases.

Modifiers that actually move the rate: n after a district split, whether kilometres roughly obey the triangle inequality (a ferry can break it), and whether a cool-down date is already written. A washed-out bridge is a new instance, not a reason to reopen the class.

Take off the week you would have spent searching before you credit the new hire. The launch that finally went out after the analyst arrived often went out on the heuristic the team already knew. The counterfactual is that same heuristic, two weeks earlier.

One flag. If a donor, a ministry, or a lead investor writes “optimal routing” into the grant or the term sheet, the measurement has become a target. Satisfy them with the published ratio and the district split. Do not satisfy them with a longer hunt.

The gap these three cannot price

None of these models can tell you the true gap between this week’s tour and the unknown best one, unless you solve the instance exactly, which is the thing you just refused. Take the shape. Do not take a promised number of kilometres saved. Sridharan’s ratios bound a worst case, not Tuesday.

They also cannot see a political order. The permanent secretary wants site X first. The sponsor wants the Kampala photo on day one. Those constraints rewrite the feasible set, not the class. You still approximate, inside the order you were given.

The honest belief that one more week of staring will produce the exact tour adds no lever the base-rate card lacks, so it stayed out. Who may freeze the week was folded into the trigger.

One property no member models: once you publish a “good enough” route, people stop offering the local knowledge that would have improved it. The boda rider who knows the afternoon shortcut. The shop closed on Thursday. That absorption does not appear in a tour length. You notice it when the published list has made it rude to speak.

The one action that survives the ignorance: by T+3, split the live tour by district, run nearest neighbour inside each, and write the date after which only adjacent swaps are legal. If two of the last three slips were “the route was not ready,” the search is the delay.

Who writes good enough

The person who needs this is the one holding budget shaped like a hire, or the one about to move the fellows’ week because the calendar is not yet perfect. The cheapest first test costs an afternoon: name the class, split by district, produce the first tour, and put the cool-down date on the same page. If the object was a tree, that is cheap. If it was a tour, the van can drive on Monday.

Sources and notes

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, chapter 1, printed p. 10. “If you are called upon to produce an efficient algorithm for an NP-complete problem, you are likely to spend a lot of time in a fruitless search. If you can show that the problem is NP-complete, you can instead spend your time developing an efficient algorithm that gives a good, but not the best possible, solution.” The delivery-truck example on the same page is the travelling-salesman problem: NP-complete, no known efficient algorithm, with efficient approximations “not too far above the smallest possible” under certain assumptions. Printed page equals PDF page minus 21 on the copy consulted (PDF 31 = book p. 10).
2. Cormen, Leiserson, Rivest and Stein, ibid., chapter 34, printed p. 1050. “If you can establish a problem as NP-complete, you provide good evidence for its intractability. As an engineer, you would then do better to spend your time developing an approximation algorithm (see Chapter 35) or solving a tractable special case, rather than searching for a fast algorithm that solves the problem exactly.” The same page states that the possibility the NP-complete problems are solvable in polynomial time cannot be ruled out. Chapter 35 was not read for this piece. No approximation ratio is taken from it. Printed page equals PDF page minus 21 (PDF 1071 = book p. 1050).
3. Cormen, Leiserson, Rivest and Stein, ibid., chapter 23, printed p. 624. A minimum spanning tree is an acyclic subset T of the edges that connects all of the vertices and whose total weight is minimised. “Since T is acyclic and connects all of the vertices, it must form a tree.” The motivating example is wiring pins with the least wire. Printed page equals PDF page minus 21 (PDF 645 = book p. 624).
4. Mark Needham and Amy E. Hodler, Graph Algorithms: Practical Examples in Apache Spark and Neo4j, O’Reilly, 2019, chapter 4, printed p. 71, “When Should I Use Minimum Spanning Tree?” Quoted as written, including the loose “best route to visit all nodes” and “visit all nodes in a single walk,” and the later clause that MST is employed to approximate problems such as the Traveling Salesman Problem. Printed page equals PDF page minus 18 on the copy consulted (PDF 89 = book p. 71). The CLRS tree definition and the Sridharan tour definition are the correction.
5. Sriraman Sridharan and R. Balakrishnan, Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory, and Cryptography, CRC Press, 2019, chapter 1.12, printed pp. 90 to 91. TSP: n cities, symmetric costs, a tour starting at city 1, visiting each city exactly once, and returning, at minimum total cost. Equivalently a minimum-weight Hamiltonian cycle on the complete graph on n vertices. Lemma 1.2: the number of Hamiltonian tours, identifying reverse tours, is (n minus 1) factorial, divided by two. Brute force is exponential because n factorial is. Printed page equals PDF page minus 27 (PDF 117 to 118 = book pp. 90 to 91).
6. Sridharan and Balakrishnan, ibid., chapter 1.12.1, printed pp. 93 to 97. An algorithm is approximate for TSP when its ratio against the exact value is bounded by a constant. Nearest neighbour, assuming the triangle inequality, satisfies NN(I)/E(I) at most one-half of (log2 n plus 1). The MST-shortcut method (MSTEULER: Prim tree, double every tree edge, Eulerian cycle, shortcuts) satisfies MSTEULER(I)/E(I) less than 2. Theorem 1.6 proves the MST-shortcut bound. Printed pages 93 to 97 (PDF 120 to 124).
7. S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science 220(4598), 13 May 1983, pp. 671 to 680. TSP stated as a route through each city once that returns to the start. “No method for exact solution with a computing effort bounded by a power of N has been found” for any NP-complete problem. Exact tour methods then known grow exponentially. Iterative improvement “usually gets stuck in a local but not a global optimum.” Simulated annealing melts at high effective temperature, then lowers temperature by slow stages until the system freezes. The sequence is an annealing schedule. Transitions out of a local optimum remain possible at nonzero temperature. Accessible text-layer copy: faculty.csu.edu.cn (PDF). Verified: body contains “traveling salesman,” “NP-complete,” “annealing schedule,” “local but not a global optimum.” The 1983 remark that exact solutions can be attempted only on a few hundred cities is dated and is not used as a current figure.
8. John H. Miller and Scott E. Page, Complex Adaptive Systems: An Introduction to Computational Models of Social Life, Princeton University Press, 2007, chapter 2.3.1, printed pp. 23 to 25, and chapter 8.3.1, printed p. 128. Best Tiebout-style mechanisms “introduce noise into the system when the local citizens’ preferences are heterogeneous and to reduce this noise as the citizens become more homogeneous.” “The choice mechanisms should ‘cool’ (anneal) the system,” linked by the authors to Kirkpatrick et al. 1983. “Well-structured noise can jolt a system out of inferior equilibria and lead it toward superior ones” (p. 25). “Allowing mistakes (especially if they are not too costly or occur early in the search process) helps systems escape less productive outcomes and converge on more productive ones” (p. 128). Quotes verified against the book in the stack-3 complexity dossier. Founder application is analogical and graded as such.
9. Jan W. Rivkin and Nicolaj Siggelkow, Organizational Sticking Points on NK Landscapes, Complexity 7(5), 2002, pp. 31 to 43. “Particularly when components interact richly in determining system fitness, such local peaks are numerous.” A local peak cannot be improved by changing a single component. A hierarchical firm may rest at a sticking point that is not a local peak, because of delegated choices, interdependencies, and local incentives that differ from global ones. Author copy: faculty.wharton.upenn.edu (PDF). Verified: body contains “local peaks are numerous,” “sticking point,” “delegation of choices to separate decision makers.”

A note on what is deliberately absent. This piece does not give you the kilometres you will save, and it does not promote a computational-class identity that the registry still holds. The bound is in the sentences. The move is the approximation or the special case, dated.

Joshua Agonya Pi’Rwot, Founder.