Combinatorial Optimization and TSP

The Travelling Salesman Problem-visit 50 cities by the optimal route. Sounds simple, but the number of possible routes is 50!/2 ≈ 10⁶⁴. Brute force would take longer than the age of the Universe. So how do UPS and FedEx plan millions of routes daily? How are chips designed with minimum wire length? The answer-in intelligent methods: **branch-and-bound, cutting planes, Lin-Kernighan and approximation algorithms with mathematical guarantees**.

• **Logistics**: UPS solves millions of TSP-like problems daily: the ORION algorithm based on LK saves 100M miles per year
• **VLSI design**: chip layout-combinatorial optimization; branch-and-cut in Cadence/Synopsis tools solves problems with 10⁶ variables
• **Production scheduling**: job-shop scheduling (in what sequence to process parts)-MIP with Gurobi/CPLEX solves problems previously considered intractable

Предварительные знания

• Distributed Optimization
• Optimization in ML and Production

Branch and Bound: Systematic Search with Pruning

**Branch and Bound** (B&B) is a universal algorithm for integer optimization problems. It systematically explores the solution space, cutting off branches of the search tree that provably cannot yield a better result than the solution already found.

**Next node selection**: - **Best-First**: node with smallest LB → quick finding of good incumbent - **Depth-First (LIFO)**: go deep → quickly find feasible solution, less memory - **Best-Bound + Depth-First**: hybrid-standard in commercial solvers **Branching variable selection**: - **Most fractional**: variable xᵢ with minimum |xᵢ*-0.5| → greatest uncertainty - **Strong branching**: evaluate both branches → best bound, expensive - **Pseudo-costs**: history of bound changes → fast approximation of strong branching

Cutting Planes: Gomory Cuts and MIP

The **Cutting Planes** method improves LP relaxation by adding **additional inequalities** (cuts) that eliminate fractional LP solutions but do not cut off any integer solution. This tightens the LP bound and speeds up B&B.

**Branch-and-Cut** = Branch and Bound + Cutting Planes-standard in commercial MIP solvers (CPLEX, Gurobi). **Algorithm**: 1. Solve LP relaxation at B&B tree node 2. If fractional solution-search for violated cuts 3. Add cuts → improve LP bound → repeat 4. If cuts don't help-branch **Real problems** solved with Branch-and-Cut: - **TSP**: routes with 1000+ cities in seconds - **Scheduling**: hospital and airline scheduling - **Facility Location**: where to open warehouses - **Network Design**: telecommunications network design

Advanced Local Search: Lin-Kernighan for TSP

For most NP-hard combinatorial problems, exact methods (B&B) are too slow for n > 1000. **Local search** is an effective heuristic: start from some solution and iteratively improve it by changing 'neighboring' configurations.

**Or-opt** (Or, 1976): move a group of 1, 2 or 3 nodes to another position in the route-more effective than 2-opt for asymmetric problems. **Tabu Search**: prohibit the reverse move after each step (tabu list). Allows escaping local minima by moving 'upward'. **VNS (Variable Neighborhood Search)**: systematically change the neighborhood, switching between 2-opt, 3-opt, Or-opt when the current neighborhood is exhausted. **Quality vs time**:

Approximation Algorithms: Guaranteed Quality

An **approximation algorithm** is a polynomial algorithm with a proven quality guarantee: the result is no worse than ρ × OPT, where ρ is the **approximation ratio**. This is a theoretically justified substitute for an exact algorithm on NP-hard problems.

**PTAS (Polynomial-Time Approximation Scheme)**: for any ε>0 there exists an algorithm with guarantee (1+ε) in time poly(n). Time may depend exponentially on ε: O(n^{1/ε}). **FPTAS (Fully Polynomial)**: time poly(n, 1/ε). For the Knapsack problem. **Examples**: - Euclidean TSP: PTAS (Arora, 1998)-for the geometric version! - Metric TSP: no PTAS (otherwise P=NP), but Christofides gives 1.5 - Knapsack: FPTAS via dynamic programming with weight scaling

Key Ideas

• **Branch and Bound**: systematic search with LP relaxation as lower bound; pruning cuts branches where LB ≥ incumbent
• **Cutting Planes / Gomory Cuts**: add inequalities cutting fractional LP solutions without touching integer ones; Branch-and-Cut = B&B + Cuts
• **Lin-Kernighan**: variable k-opt depth with candidate lists; practically the best algorithm for TSP, usually within 0-2% of optimum
• **Approximation algorithms**: Christofides (1.5× for metric TSP), greedy Set Cover (ln n×), MAX-CLIQUE has no approximation better than O(n^{1-ε})

Related Topics

Combinatorial optimization combines methods from different areas:

• Integer Programming — B&B and cutting planes - main algorithms for solving ILP and MIP problems
• Metaheuristics — Simulated Annealing, Genetic Algorithms - alternatives to local search for very large n or high neighborhood complexity
• Bayesian Optimization — For expensive combinatorial problems (NAS, hyperparameter search) Bayesian Opt is an efficient black-box alternative

Вопросы для размышления

• For a problem with 1000 cities and 1 minute time limit: which algorithm would you choose - exact B&B, LK or Christofides - and why?
• Christofides gives a 1.5 guarantee. Does this mean the practical result is always close to 1.5×OPT, or is actual quality much better?
• If a problem is NP-hard with no approximation better than O(n^{1-ε}), how can it be applied in practice for large real-world instances?

Связанные уроки

• alg-34-approximation