Combinatorial_optimization

# Combinatorial optimization ## Microsim (three.js) <div class="microsim-player">  <p class="wt-pending"><strong>Microsim staged, not yet on the CDN.</strong> <code>Combinatorial_optimization.html</code> is built and deploy-ready in <code>Microsims for Dissemination/</code>, but the Netlify project still serves the geometry+spintronics set only. The player is disabled until the deploy lands; the explanatory text below is unchanged.</p>   </div> *Combinatorial optimization is the algorithmic search for the best arrangement inside a finite but explosively large set of discrete choices — the engine behind routing, scheduling, and network design. It leans on [[Dynamic_programming]] to tame otherwise hopeless searches, borrows the geometry of [[Polytope]] relaxations to prove tours optimal, and turns to randomized tools like the [[Monte_Carlo_method]] when instances grow too big to solve exactly.* > Combinatorial optimization is the search for the best configuration among a finite but enormous set of discrete possibilities. Its most famous example is the Traveling Salesman Problem: find the shortest loop that visits every city once and returns home. This microsim lets you build such a loop two ways — quickly, with a greedy rule that always heads to the nearest unvisited city, or exactly, by having the computer check every possible tour. Trying both reveals why a fast, sensible-looking shortcut usually misses the true optimum, and why the guaranteed-best answer gets harder to find as the problem grows. ## About this microsim Before any definitions, press **New Cities** to scatter a handful of points, then **Random Tour** to see one arbitrary route through them — almost certainly not the shortest. Now watch optimization happen: click **Step Greedy** repeatedly to extend the tour one edge at a time, each step jumping to the nearest unvisited city, or click **Auto Greedy** to build the whole nearest-neighbor tour at once. Then press **Brute Force Best** to compute the genuine optimum and compare — the greedy tour is usually close but rarely exactly best. The **Cities (N)** control (5–9) sets how many points there are; raise it and press **Brute Force Best** again to feel how sharply the exact search slows as the tour count explodes. **Reset Tour** clears the route so you can retry on the same cities. ## Related microsims - [[Dynamic_programming]] — the Held–Karp algorithm solves the TSP exactly in $O(n^2 2^n)$, far faster than brute force - [[Monte_Carlo_method]] — randomized search and simulated annealing attack instances too large to enumerate - [[Polytope]] — exact solvers optimize over the TSP polytope using linear-programming relaxations - [[Reinforcement_learning]] — neural policies can be trained to construct good tours, a learned version of the greedy step - Process optimization — the same discrete-optimization mindset applied to industrial routing and scheduling - Bounded set — related ALGORITHM microsim - [[Calculus_of_variations]] — related ALGORITHM microsim - Circuit minimization for Boolean functions — related ALGORITHM microsim - Extreme value theorem — related ALGORITHM microsim - [[Polyhedron]] — related ALGORITHM microsim ## Links (Wikipedia order)  `Active-set_method` · `Affine_scaling` · `Alexander_Schrijver` · [[Algorithm]] · `Applied_mathematics` · `Approximation_algorithm` · [[Artificial_intelligence]] · `Assignment_problem` · `Auction_theory` · `Augmented_Lagrangian_method` · `Barrier_function` · `Bellman–Ford_algorithm` · `Berndt–Hall–Hall–Hausman_algorithm` · `Bin_packing_problem` · `Borůvka's_algorithm` · `Bounded_set` · `Branch_and_bound` · `Branch_and_cut` · `Broyden–Fletcher–Goldfarb–Shanno_algorithm` · `Chinese_postman_problem` · `Clique_problem` · `Closure_problem` · [[Comparison_of_optimization_software]] · `Computational_complexity_theory` · `Constraint_composite_graph` · `Constraint_satisfaction_problem` · `Convex_optimization` · `Criss-cross_algorithm` · `Cutting-plane_method` · `Cutting_stock_problem` · `Davidon–Fletcher–Powell_formula` · `Decision_problem` · `Dijkstra's_algorithm` · `Dinic's_algorithm` · `Dominating_set` · [[Dynamic_programming]] · `Earth_science` · `Edmonds–Karp_algorithm` · `Ellipsoid_method` · `Eugene_Lawler` · `Evolutionary_algorithm` · `Finite_set` · `Flow_network` · `Floyd–Warshall_algorithm` · `Ford–Fulkerson_algorithm` · `Frank–Wolfe_algorithm` · `Function_(mathematics)` · `Gauss–Newton_algorithm` · `Gerhard_J._Woeginger` · `Germany` · `Golden-section_search` · `Gradient` · `Gradient_descent` · `Graph_(discrete_mathematics)` · `Greedy_algorithm` · `Hessian_matrix` · `Hill_climbing` · `Integer_programming` · `Iterative_method` · `Jon_Lee_(mathematician)` · `Juraj_Hromkovič` · `Karen_Aardal` · `Karmarkar's_algorithm` · `Kenneth_Steiglitz` · `Knapsack_problem` · `Kruskal's_algorithm` · `L-reduction` · `Lemke's_algorithm` · `Levenberg–Marquardt_algorithm` · `Limited-memory_BFGS` · `Line_search` · `Linear_programming` · `Local_convergence` · `Local_search_(optimization)` · [[Logistics]] · [[Machine_learning]] · `Makespan` · `Marek_Karpinski` · `Matching_(graph_theory)` · [[Mathematical_optimization]] · `Matroid` · `Metaheuristic` · `Metric_k-center` · `Minimum_relevant_variables_in_linear_system` · `Minimum_spanning_tree` · `Mirror_descent` · `NP-completeness` · `NP_(complexity)` · `Nelder–Mead_method` · `Newton's_method_in_optimization` · `Nonlinear_conjugate_gradient_method` · `Nonlinear_programming` · `Nurse_scheduling_problem` · [[Operations_research]] · `Parallel_metaheuristic` · `Parameterized_approximation_algorithm` · `Penalty_method` · `Planar_graph` · `Polynomial` · `Polynomial-time_approximation_scheme` · `Powell's_dog_leg_method` · `Powell's_method` · `Prim's_algorithm` · `Push–relabel_maximum_flow_algorithm` · `Quadratic_programming` · `Quasi-Newton_method` · `Reservoir` · `Revised_simplex_method` · `Ring_star_problem` · `Search_algorithm` · `Sequential_quadratic_programming` · `Set_cover_problem` · `Shortest-path_tree` · `Shortest_path_problem` · `Simplex_algorithm` · `Simulated_annealing` · [[Software_engineering]] · `Spanning_tree` · `Spiral_optimization_algorithm` · `Subgradient_method` · `Successive_linear_programming` · `Successive_parabolic_interpolation` · `Supply_chain_optimization` · `Symmetric_rank-one` · `Tabu_search` · `Talent_scheduling` · `Theoretical_computer_science` · `Travelling_salesman_problem` · `Truncated_Newton_method` · `Trust_region` · `Turing_reduction` · `University_of_Waterloo` · `Vehicle_rescheduling_problem` · `Vehicle_routing_problem` · `William_J._Cook` · `William_R._Pulleyblank` · `Wolfe_conditions` ## Overview Combinatorial optimization is a branch of mathematical optimization concerned with finding an optimal object from a *finite* set of feasible ones. It sits where computer science, operations research, and applied mathematics meet, and includes classic problems such as the minimum spanning tree, knapsack, set cover, and the Traveling Salesman Problem (TSP). The TSP was studied by Karl Menger in 1930s Vienna as *das Botenproblem* ("the messenger problem") and popularized in the United States by Hassler Whitney. In 1954 George Dantzig, Ray Fulkerson, and Selmer Johnson solved a 49-city instance to optimality using linear programming with cutting planes, helping found integer programming. Its decision version is NP-complete (following Richard Karp, 1972), making the TSP the canonical hard problem for testing exact algorithms, approximation guarantees, and metaheuristics. ## How it works An instance gives $n$ cities and a distance $d(i,j)$ between every pair — here, the straight-line distance between points in the plane. A tour is a cyclic ordering, a permutation $\pi$, with length $L(\pi) = \sum_{i=1}^{n} d\big(\pi(i),\,\pi(i{+}1)\big),$ where indices are taken modulo $n$ so the last city links back to the first. Because the loop's starting city (a factor of $n$) and its direction (a factor of $2$) leave the length unchanged, there are $(n-1)!/2$ genuinely distinct tours: | Cities $n$ | Distinct tours $(n-1)!/2$ | |---|---| | 5 | 12 | | 6 | 60 | | 7 | 360 | | 8 | 2,520 | | 9 | 20,160 | Just past the control's range the count reaches $181{,}440$ at $n=10$ and about $4.4\times10^{10}$ at $n=15$ — the *combinatorial explosion* that caps the sim at 9. **Brute Force Best** evaluates every tour and keeps the shortest, guaranteeing optimality in $O(n!)$ time; the best known exact method, the Held–Karp dynamic program, cuts this to $O(n^2 2^n)$ — still exponential. No polynomial-time exact algorithm is known, since an efficient one would imply P = NP. The **greedy** buttons run the nearest-neighbor heuristic: from the current city, always step to the closest unvisited one. This takes only $O(n^2)$ time but is myopic — grabbing near edges early can force a long jump home — and averages roughly 25% above optimal on random instances. ## Controls -> what each maps to | Control | Maps to | Range / values | Meaning | |---|---|---|---| | Cities (N) | Problem size $n$ | 5–9 | Number of cities; fixes the search space at $(n-1)!/2$ tours | | New Cities | Instance generation | button | Scatters a fresh set of random city positions | | Random Tour | Baseline solution | button | Draws an arbitrary tour as an unoptimized reference | | Step Greedy | One nearest-neighbor step | button | Extends the tour to the closest unvisited city, one edge | | Auto Greedy | Full greedy heuristic | button | Completes the nearest-neighbor tour automatically | | Brute Force Best | Exact optimization | button | Enumerates all tours to find the provably shortest | | Reset Tour | Clear state | button | Removes the current tour but keeps the cities | ## Learning objective After playing, you can predict that a greedy nearest-neighbor tour will look plausible yet usually fall short of the brute-force optimum, and explain why exact search becomes intractable as the number of cities grows. ## Limits and connections Real solvers do far better than brute force: Christofides' algorithm guarantees a tour at most $3/2$ times optimal when distances obey the triangle inequality, branch-and-cut solvers such as Concorde have proven optimal tours through tens of thousands of cities, and local search (2-opt, Lin–Kernighan) handles far larger instances heuristically. The TSP is a template for vehicle routing, chip layout, and DNA sequencing, and its study underpins the theory of NP-completeness and polyhedral combinatorics. ## Poster & source <div class="microsim-fallback">  <p><em>Live microsim · <a href="https://wikitube-3d-microsims.netlify.app/Combinatorial_optimization.html">open full</a> · source: Microsims for Dissemination/ALGORITHM_microsims/Combinatorial_optimization.html</em></p> </div>  *Built to the [[WT!Three_js_Microsim_Master_Class|three.js Master Class]].*  ## Wikipedia : Wikitube **Strict pair:** [Wikipedia](https://en.wikipedia.org/wiki/Combinatorial_optimization) : [Wikitube](https://en.wikitube.io/wiki/Combinatorial_optimization) ## Previous hub tags Tree parents: [[Network_theory]] · [[Operations_research]]. Legacy hubs: `ALGORITHM`. --- *Sources: 1 legacy note. Minted wave 1, 2026-07-30 (v1.6 order).*