<ahref="#TSPIntroduction">What is the Travelling Salesman Problem?</a>
</li>
<liclass="level1">
<ahref="#TSPWalkthrough">Concrete Walkthrough</a>
</li>
<liclass="level1">
<ahref="#TSPImplementation">Implementation</a>
</li>
<liclass="level1">
<ahref="#TSPDesignPoints">Design Points</a>
</li>
</ul>
</div>
<divclass="textblock"><p>We implement a parallel branch-and-bound solver for the Travelling Salesman Problem (TSP) using <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> for recursive task parallelism. This example demonstrates how a combinatorial search algorithm with a dynamically growing task tree maps naturally onto Taskflow's cooperative task group model.</p>
<h1><aclass="anchor" id="TSPIntroduction"></a>
What is the Travelling Salesman Problem?</h1>
<p>The Travelling Salesman Problem asks: given a set of cities and the distance between every pair of cities, what is the shortest route that visits every city exactly once and returns to the starting city?</p>
<divclass="image">
<imgsrc="tsp_example.png" alt=""/>
</div>
<p>It is one of the most studied problems in computer science and operations research. Despite its simple statement, TSP is NP-hard: no known algorithm solves it in polynomial time for arbitrary inputs. The only way to guarantee an optimal solution is exhaustive search, which explores all possible tours. For <code>N</code> cities there are <code></code>(N-1)!/2 distinct tours, which grows astronomically: 10 cities have 181,440 tours, 15 cities have over 43 billion.</p>
<p>This is precisely why parallelism matters. Each branch of the search tree is independent of every other branch and can be explored on a separate CPU core simultaneously. Branch and bound makes the search tractable by pruning branches that cannot possibly improve the best solution found so far, but the remaining work is still substantial and benefits greatly from parallel execution.</p>
<h1><aclass="anchor" id="TSPWalkthrough"></a>
Concrete Walkthrough</h1>
<p>Consider four cities A, B, C, D with the following symmetric distance matrix:</p>
<divclass="fragment"><divclass="line"> A B C D</div>
<divclass="line">A [ 0 10 15 20 ]</div>
<divclass="line">B [ 10 0 35 25 ]</div>
<divclass="line">C [ 15 35 0 30 ]</div>
<divclass="line">D [ 20 25 30 0 ]</div>
</div><!-- fragment --><p>Starting from city A, the algorithm builds partial tours by choosing which city to visit next at each step. At each node it computes a lower bound on the best possible completion of the current partial tour. If the lower bound is greater than or equal to the best complete tour found so far, the entire subtree rooted at that node is pruned — there is no point exploring it further. The lower bound used here is:</p>
<divclass="line"> + min outgoing edge from current city to any unvisited city</div>
<divclass="line"> + sum of min outgoing edge from each remaining unvisited city</div>
</div><!-- fragment --><p>This is a valid lower bound because any completion of the tour must include at least one edge out of the current city and at least one edge incident to each unvisited city. The figure below shows the full search tree for this 4-city instance. Peach nodes are explored, red nodes are pruned (their lower bound already exceeds the best known cost), and the green node is the optimal tour:</p>
<divclass="dotgraph">
<iframescrolling="no" frameborder="0" src="dot_tsp_tree.svg" width="906" height="428"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>The algorithm finds <code>A->B->C->D->A</code> with cost 95 first, then improves to <code>A->B->D->C->A</code> with cost 80 (the optimum). With <code>best_cost</code> equal to 80 established, all four remaining branches are pruned because their lower bounds of 80 or 95 cannot improve on 80. Only 5 of the 9 possible interior nodes are actually evaluated.</p>
<h1><aclass="anchor" id="TSPImplementation"></a>
Implementation</h1>
<p>We represent the distance matrix as a flat vector and implement the branch-and-bound search as a recursive function. Each recursive call creates a <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> to spawn one async task per unvisited city (the "include this city next" branch) while computing one branch directly on the current worker. After spawning, <code>tg.corun()</code> cooperatively waits for all spawned branches to complete without blocking the worker thread.</p>
<p>A global <code>std::atomic<int></code> tracks the best tour cost found so far. Any branch whose lower bound is at or above this value is pruned immediately by returning without spawning children. When a better complete tour is found, the atomic is updated with <code>compare_exchange_weak</code> so that all workers immediately see the tighter bound on their next pruning check.</p>
<divclass="line"><spanclass="keywordflow">if</span>(min_curr == INF) <spanclass="keywordflow">return</span> bound; <spanclass="comment">// no unvisited cities: tour is complete</span></div>
<divclass="line"> bound += min_curr;</div>
<divclass="line"></div>
<divclass="line"><spanclass="comment">// (2) for each unvisited city, add the cost of its cheapest outgoing edge</span></div>
<divclass="line"><spanclass="comment">// to any other city (visited or not, as long as it is not the city itself).</span></div>
<divclass="line"><spanclass="comment">// This accounts for the fact that we must enter or leave each unvisited city</span></div>
<divclass="line"><spanclass="comment">// at some point, and the cheapest way to do so is via its minimum edge.</span></div>
<divclass="line"><spanclass="keywordflow">for</span>(<spanclass="keywordtype">int</span> u = 0; u < N; u++) {</div>
<divclass="ttc" id="aclasstf_1_1Executor_html"><divclass="ttname"><ahref="classtf_1_1Executor.html">tf::Executor</a></div><divclass="ttdoc">class to create an executor</div><divclass="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_a8858a119b9ad697748293c4bb1408853"><divclass="ttname"><ahref="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">tf::Executor::task_group</a></div><divclass="ttdeci">TaskGroup task_group()</div><divclass="ttdoc">creates a task group that executes a collection of asynchronous tasks</div><divclass="ttdef"><b>Definition</b> task_group.hpp:863</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_af960048056f7c6b5bc71f4f526f05df7"><divclass="ttname"><ahref="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">tf::Executor::async</a></div><divclass="ttdeci">auto async(P &&params, F &&func)</div><divclass="ttdoc">creates a parameterized asynchronous task to run the given function</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html_a1f481dc466e3107a08346d1a124677bc"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">tf::TaskGroup::corun</a></div><divclass="ttdeci">void corun()</div><divclass="ttdoc">corun all tasks spawned by this task group with other workers</div><divclass="ttdef"><b>Definition</b> task_group.hpp:721</div></div>
</div><!-- fragment --><p>The program output is:</p>
<divclass="fragment"><divclass="line">Optimal tour cost: 80</div>
</div><!-- fragment --><p>which corresponds to the tour <code>A->B->D->C->A</code>.</p>
<h1><aclass="anchor" id="TSPDesignPoints"></a>
Design Points</h1>
<p>There are a few important design points worth noting for this example, which also apply generally to parallel search algorithms:</p>
<ul>
<li>TaskGroup per recursive call: Each invocation of <code>branch_and_bound</code> creates its own <code>tg</code> via <code>executor.task_group()</code>. This is valid because every invocation runs inside a worker thread of the executor — either as the root <code>executor.async</code> task or as a <code>tg.silent_async</code> task spawned by a parent invocation. Attempting to call <code>executor.task_group()</code> from outside a worker thread throws an exception.</li>
<li>First branch on the current worker: Rather than spawning all branches as async tasks, the first unvisited city is explored directly on the current worker. This avoids task creation overhead for at least one branch per node and keeps the worker busy without yielding back to the scheduler. The remaining branches are spawned via <code>tg.silent_async</code>.</li>
<li>Atomic <code>best_cost</code> for pruning: All workers share a single <code>std::atomic<int></code><code>best_cost</code>. When any worker finds a better complete tour, it updates <code>best_cost</code> with <code>compare_exchange_weak</code> so that all other workers immediately see the tighter bound on their next pruning check. This is the key mechanism that makes parallel branch and bound more efficient than running independent serial searches: workers continuously share information about the best solution found so far, tightening the pruning bound for the entire parallel search.</li>
<li>Cooperative execution via corun: <code>tg.corun()</code> does not block the calling worker thread. Instead, the worker participates in the executor's work-stealing loop, executing other tasks while waiting for its spawned branches to complete. This prevents worker starvation when the search tree is deep and avoids the deadlock that would result from a blocking wait inside an executor worker.</li>
</ul>
<dlclass="section note"><dt>Note</dt><dd>For larger instances, the <code>visited</code> vector copy on each recursive call becomes a bottleneck. A bitmask (<code>uint32_t</code> or <code>uint64_t</code>) is more efficient for up to 32 or 64 cities respectively. For production TSP solvers, more sophisticated bounding functions such as the Held-Karp lower bound or minimum spanning tree bound deliver much tighter pruning and dramatically reduce the search tree size. </dd></dl>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<divid="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<liclass="navelem"><aclass="el" href="Examples.html">Learning from Examples</a></li>
<liclass="footer">
Maintained by <ahref="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <ahref="https://www.doxygen.org/index.html"><imgclass="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1