Discrete Optimization

Definitions

Traveling Salesman Problem (TSP)

— Given $n$ cities with distances $d_{ij}$ between them. Find the shortest route visiting each city exactly once and returning to the start.

Knapsack Problem

— $n$ items with values $c_i$ and weights $w_i$. The knapsack can hold $W$ kg. Choose a set of items with maximal total value.

Set Cover Problem

— Given a universal set $U$ and a family of subsets $S_1,...,S_m$. Choose the minimal subfamily covering $U$. Applications: minimal number of fire stations to cover an entire city.

MAX-CUT

— Graph $G=(V,E)$. Split $V$ into two sets $S$, $V \setminus S$, maximizing the number of edges between them. Applications: data clustering, VLSI layout.

Example (TSP as ILP)

— $x_{ij} \in \{0,1\}$—use of edge $(i,j)$. Constraints: $\sum_j x_{ij} = 1$ (entering each city), $\sum_i x_{ij} = 1$ (exiting), $y_i - y_j + n x_{ij} \leq n-1$ for $i \neq j \neq 1$ (elimination of subroutes).

Class P

— problems solvable in polynomial time $O(n^k)$. Examples: sorting $O(n \log n)$, shortest path in a graph $O(n^2)$, linear programming $O(n^{3.5})$.

Class NP

— problems whose solution can be verified in polynomial time. Example: TSP—a given route can be checked in $O(n)$. But finding the optimum—we don't know how.

NP-complete problems

— hardest in NP. Any NP problem can be polynomially reduced to any NP-complete problem. The first NP-complete problem: SAT (Cook, 1971).

What this means in practice

— three strategies for NP-hard problems:

Data

— $W = 10$ kg, 4 items: $(c_1,w_1) = (6,4)$, $(c_2,w_2) = (5,3)$, $(c_3,w_3) = (4,2)$, $(c_4,w_4) = (3,1)$.

Optimum

— $\{1,2,3,4\}$ with $c=18$. But for $n = 50$ items—$2^{50} > 10^{15}$ options, enumeration is unrealistic.

FedEx delivers 15 million parcels per day. The route of each truck is a sequence of stops. How should the routes be assigned so the total mileage is minimized? This is a vehicle routing problem—a discrete optimization problem. Or: an airline must schedule flights, assigning crews to routes so as ...

It may seem that one could simply enumerate all options. But the scale makes this impossible. The traveling salesman problem (find the shortest route through n cities): number of possible routes = $(n−1)!/2$. For $n = 20$: ≈ 60 quintillion routes. At 1 billion operations per second, enumeration w...

The solution? Smart algorithms that find the optimum (or a good approximation) in reasonable time.

Traveling Salesman Problem (TSP): Given $n$ cities with distances $d_{ij}$ between them. Find the shortest route visiting each city exactly once and returning to the start.

Definitions

Formulation

— a directed network G = (V, E) with capacities c(e) > 0 on each edge. Source s, sink t. Find the maximum flow from s to t.

Ford-Fulkerson Theorem

— max flow = min cut.

Ford-Fulkerson Algorithm

— we search for an "augmenting path" in the residual network: a path from s to t where each edge has a residual capacity > 0. We increase the flow along the path. We repeat until there is no such path.

Complexity

— O(E · f_max) for rational capacities. The Edmonds-Karp algorithm uses BFS to find the shortest path → O(V E²).

Full Example Analysis

— network: s→a (c=4), s→b (c=3), a→t (c=3), a→b (c=2), b→t (c=4).

Bipartite graph

— V = A ∪ B, edges only between A and B.

Hopcroft-Karp Algorithm

— O(E√V). Searches for augmenting paths using BFS (finds all shortest augmenting paths simultaneously), then DFS to find the maximum matching of this length.

Hungarian Algorithm (assignment problem)

— given a complete bipartite graph with weights wᵢⱼ (cost of assigning task i to executor j). Find the minimal assignment (= matching of minimal total weight). Complexity: O(n³).

MST problem

— find a spanning tree with the minimal total weight of edges.

Kruskal’s Algorithm

— O(E log E)

Prim’s Algorithm

— O(E log V) with heap

Proof of optimality (cut property)

— for any cut (S, V∖S), the minimal edge through the cut belongs to any MST.

Full analysis

— graph with 4 vertices: a-b (4), a-c (3), b-c (2), b-d (5), c-d (1).

Applications

— laying cables for a network with minimal cable length (telephone, electrical networks), data clustering (single-linkage), approximation algorithms for TSP.

Dijkstra's Algorithm

— non-negative weights. O((V+E) log V) with binary heap. Idea: greedily expand the "front" of shortest paths from s.

Formulas

A graph is a mathematical abstraction of a network: vertices (nodes) and edges (connections). The Internet is a graph of routers. A social network is a graph of users. A transportation network is a graph of cities and roads. Many discrete optimization problems are graph problems. Three classical ...

Formulation: a directed network G = (V, E) with capacities c(e) > 0 on each edge. Source s, sink t. Find the maximum flow from s to t.

Flow f: flow on edge (u,v) ≤ c(u,v), in each vertex (except s, t) the sum of incoming flows equals the sum of outgoing flows.

Cut (S, V∖S) with s ∈ S, t ∈ V∖S: capacity of the cut = sum of capacities of edges from S to V∖S. The minimal cut is the "bottleneck" of the network.

Definitions

Standard form of LP

— min $c^\top x$ subject to $Ax \leq b$, $x \geq 0$.

ILP

— min $c^\top x$ subject to $Ax \leq b$, $x \in \{0,1\}^n$.

LP relaxation

— min $c^\top x$ subject to $Ax \leq b$, $0 \leq x \leq 1$. (Drop integrality)

Example

— knapsack problem with $W=5$, $n=3$: $(c_1, w_1)=(4,3)$, $(c_2, w_2)=(3,2)$, $(c_3, w_3)=(2,1)$.

Definition

— a matrix $A$ is called totally unimodular (TU) if the determinant of every square submatrix is in $\{-1, 0, +1\}$.

Theorem (Hoffman-Kruskal)

— if $A$ is a TU matrix and $b$ is integer, then the vertices of the polytope $\{x: Ax \leq b, x \geq 0\}$ are all integer. Thus, LP optimum = ILP optimum—you can solve the ILP via LP!

Corollary

— the maximum matching problem, the maximum flow problem, and the shortest path problem—all can be solved by LP!

LP duality

— for the problem (P): min $c^\top x$ subject to $Ax \geq b$, $x \geq 0$ the dual (D) is: max $b^\top y$ subject to $A^\top y \leq c$, $y \geq 0$.

Weak duality

— any feasible $y$ gives $b^\top y \leq c^\top x$ for any feasible $x$. Corollary: $b^\top y$ is a lower bound on the optimum of (P).

Primal-Dual Method

— simultaneously construct a feasible integer solution $\hat{x}$ and a feasible dual solution $\hat{y}$. Guarantee: $c^\top \hat{x} \leq \rho \cdot b^\top \hat{y} \leq \rho \cdot OPT \rightarrow \rho$-approximation.

Guarantee

— $\ln n$-approximation ($\ln n$ is the maximum degree of a vertex in the cover hypergraph).

Graph

— $V = \{1,2,3,4\}$, edges: $(1,2)=2$, $(1,3)=4$, $(2,3)=1$, $(2,4)=5$, $(3,4)=2$. Find the shortest path from 1 to 4.

Flow LP formulation

— $x_{ij} \geq 0$—flow through edge $(i,j)$. Problem: min $\sum d_{ij} x_{ij}$ subject to flow-balance constraints (flow 1 from source, $-1$ at sink, 0 elsewhere).

Solution

— simplex yields $x_{12}=1$, $x_{23}=1$, $x_{34}=1$ (path $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$, cost = $2+1+2=5$). Solution is integer (network matrix is TU)!

Dual LP

— vertex potentials: max $\pi_4-\pi_1$ subject to $\pi_j-\pi_i \leq d_{ij}$. Optimum: $\pi_1=0$, $\pi_2=2$, $\pi_3=3$, $\pi_4=5$. Dual optimum = 5 = primal ✓ (strong duality).

Formulas

Integer optimization problems are discrete by their very nature. Yet the key tool for solving them is linear programming, a continuous problem. The idea: “relax” the integer constraints to continuous ones, solve a much simpler problem, and use the result to find the integer optimum. This is “LP r...

The feasible set—the intersection of half-spaces—is a polytope (a convex polyhedron).

Key theorem: the optimal solution to an LP is always achieved at a vertex of the polytope (provided an optimum exists). A vertex is a point where $n$ constraints are “active” (hold as equalities).

Number of vertices: up to $C_{m+n}^n \approx m^n/n!$ (exponential). But in practice, the simplex method traverses only $O(m)$ vertices. Karmarkar’s method (1984): polynomial—$O(n^{3.5})$, moves “through the center” of the polytope.

Definitions

Search tree

— each node is a subproblem with additional constraints. The root is the original problem without any additional constraints.

Pruning rule

— if LB(node) ≥ incumbent, this node is useless — we prune (cut off) it along with all descendants.

LP bound

— solve the LP relaxation. Good bound, but computationally expensive.

Lagrangian relaxation

— “soften” some constraints by adding them to the objective with penalties $\lambda$.

Task

— $W=10$, items $(c,w)$: (6,4), (5,3), (4,2), (3,1).

Root node

— LP relaxation. Greedy strategy by $c/w$ ratio: take 4 ($c=3$, $w=1$), 3 ($c=4$, $w=2$), 2 ($c=5$, $w=3$). Remaining 4 kg → take $6/4 = 1.5$ units of item 1: $x_1=1$, $x_2=1$, $x_3=1$, $x_4=1$, value = $3+4+5+6=18$. $LB = 18$ (integer!).

A complete enumeration of all options is impossible for large n. But we can be smarter: if at some step we know that "nothing good will come further," we can cut off an entire branch of the search tree. The Branch and Bound (B&B) method systematizes this idea. This is the foundation of all indust...

Search tree: each node is a subproblem with additional constraints. The root is the original problem without any additional constraints.

Lower bound (LB) for a node: the minimally possible value of the objective function in this node. Usually this is the optimum of the LP relaxation of the subproblem.

Pruning rule: if LB(node) ≥ incumbent, this node is useless — we prune (cut off) it along with all descendants.

Formulas

LP relaxation may yield fractional optima (x₁ = 1.5, x₂ = 0.7...). Is it possible to add "smart" linear constraints that "cut off" these fractional solutions without removing any integer ones? This is precisely what cutting planes do. Instead of branching immediately, we add such planes to "pull"...

Definition: an inequality $a^\top x \leq b$ is called a *cutting plane* for MILP if: 1. It holds for all integer feasible points $x \in \{0,1\}^n$ 2. It is violated by the current LP optimum $x^*$ (fractional)

By adding such an inequality, we "cut off" the fractional $x^*$, but do not lose any integer solution. The new LP relaxation gives a better (higher) lower bound.

Ralph Gomory's idea (1958): take a row of the simplex tableau for a fractional variable and generate a cutting plane.

Definitions

Formulation

— the optimal solution contains optimal solutions to all its subproblems.

Statement

— n items with values cᵢ and weights wᵢ, knapsack capacity W.

State

— V[i][w] = maximum value using the first i items and capacity w.

Initial conditions

— V[0][w] = 0 for all w (no items—no value).

Complexity

— O(nW) in time and memory—pseudo-polynomial (not polynomial, since W can be enormous).

Bellman-Ford

— d[v] = min_{(u,v)∈E} {d[u] + w(u,v)}.

Negative cycle detection

— if d[n][v] < d[n−1][v] for some v — negative cycle!

Floyd-Warshall

— all pairs shortest paths.

Problem

— given strings s₁ and s₂. Find the longest common subsequence (not necessarily contiguous).

Applications

— bioinformatics—DNA sequence alignment (the BLAST program). Systems programming—diff algorithm for comparing files in git. Data compression—LZW uses common substrings.

Recurrence

— dp[S][v] = min_{u ∈ S{v}} {dp[S{v}][u] + d(u,v)}.

Answer

— min_{v ≠ 1} {dp[{2,...,n}][v] + d(v,1)}.

Formulas

Dynamic Programming (DP) is one of the most elegant methods in discrete optimization. The idea is both simple and profound: the optimal solution to a large problem is constructed from optimal solutions to smaller subproblems. This is the Bellman principle of optimality. DP “remembers” the results...

Formulation: the optimal solution contains optimal solutions to all its subproblems.

When is the principle satisfied? When subproblems are independent (the solution to one does not interfere with another) and the structure of the optimal solution allows a recursive decomposition.

When is it NOT satisfied? When global constraints must be considered (for example, the traveling salesman problem—the subproblems are connected through the constraint “visit each city exactly once”). Nevertheless, TSP can also be solved by DP in O(2ⁿ n²)!

Definitions

Vertex Cover problem

— graph $G = (V, E)$. Find a minimal cardinality set of vertices $C \subseteq V$ such that every edge $(u,v)$ has at least one endpoint in $C$.

Proof of 2-approximation

— $M$ is a matching (edges in $M$ have no common vertices). Therefore, $|M| \leq OPT$ (the optimum must cover all edges in $M$ $\rightarrow$ needs $\geq |M|$ vertices). $|C| = 2|M| \leq 2 \cdot OPT$. ✓

Example

— $K_4$ (complete graph with 4 vertices). $OPT = 2$ (do any 2 vertices cover all 6 edges? No: 2 vertices cover 5 edges. $OPT = 3$). The algorithm picks 2 edges $\rightarrow$ 4 vertices. Approximation $= 4/3 < 2$. ✓

APX-hard problems

— there is no PTAS (Polynomial-Time Approximation Scheme) if $P \neq NP$.

Max-3-SAT

— APX-hard. Best known approximation: $7/8$ (randomized—assign each variable randomly). Impossible to do better if $P \neq NP$ (Håstad 2001).

Problem

— $n$ items with sizes $s_i \in (0,1]$. Minimal number of unit bins to fit all items.

First-Fit (FF)

— for each item, place in first bin that fits. If none—open new bin. Approximation: $\leq \frac{17}{10} OPT + 2$ — not very good.

First-Fit Decreasing (FFD)

— sort items in decreasing order, then apply FF.

Theorem (Johnson, 1974)

— $FFD(I) \leq \frac{11}{9} OPT(I) + 4$.

How it is proven

— analyze how much "space" is wasted in each bin. When sorted in decreasing order, losses are minimized.

FPTAS for Bin Packing

— if sizes are known in advance, there exists a $(1+\epsilon)$-approximation in $O(n \log n + f(1/\epsilon))$ — Fernandez de la Vega & Lueker (1981). Split items into "large" ($s_i > \epsilon$) and "small" ($s_i \leq \epsilon$), process differently.

$k$-Median problem

— given $n$ clients and $n$ "warehouse" points, metric $d$. Choose $k$ warehouses to minimize the sum of distances from clients to nearest warehouse.

Guarantee

— in local optimum, the algorithm gives $\leq (3+\epsilon) \cdot OPT$. Proof: amortized analysis of swaps. Application: optimal server placement, regional center distribution.

If a problem is NP-hard, we cannot (presumably) find an optimal solution in polynomial time. But often we do not need perfect precision—"good enough" is sufficient. Approximation algorithms find solutions with guaranteed quality: no worse than $\rho$ times the optimum. For $\rho = 1.5$ this means...

An algorithm $A$ is called $\rho$-approximation ($\rho \geq 1$), if for any input $I$:

For minimization problems: $A(I) \leq \rho \cdot OPT(I)$. For maximization: $A(I) \geq OPT(I)/\rho$.

Vertex Cover problem: graph $G = (V, E)$. Find a minimal cardinality set of vertices $C \subseteq V$ such that every edge $(u,v)$ has at least one endpoint in $C$.

Definitions

Kruskal’s Algorithm

— sort the edges by weight. Greedily add the minimum edge that does not create a cycle.

Cut Lemma

— for any cut (S, V∖S), the minimum edge crossing the cut is included in the MST.

Proof

— let $e^*$ be the minimum edge crossing the cut, and let $T$ be an MST not containing $e^*$. Add $e^*$ to $T$ → a cycle is formed, which crosses the cut at least in one other edge $e'$. Since $e^*$ is minimal in the cut: $w(e^*) \leq w(e')$. Replac...

Basis of a matroid

— a maximal independent set. By I3 all bases have the same size (the rank of the matroid).

Linear matroid

— $E$ = columns of matrix $A$ over field $F$, $I$ = linearly independent subsets of columns. The rank of the matroid equals the rank of the matrix.

Partition matroid

— $E$ is partitioned into groups $E_1, ..., E_k$. $I$ = sets with no more than 1 element from each $E_i$. Used to represent schedules.

Theorem

— the greedy algorithm is optimal for the maximum-weight independent set problem if and only if $(E, I)$ is a matroid.

Greedy algorithm

— sort the elements in order of decreasing weight. Add the next element if after adding the set remains independent.

MST

— graphic matroid → Kruskal’s algorithm is optimal ✓.

Assignment problem

— bipartite graph $G$, need to pick $k$ edges, none incident to the same vertex (= matching of size $k$). This is the intersection of two partition matroids! → polynomially solvable (Edmonds’ algorithm).

Huffman’s problem

— optimal prefix code for compression. Huffman’s greedy algorithm is optimal — the structure is matroidal.

Problem

— find the largest independent set $I \in I_1 \cap I_2$ (intersection of two matroids).

Algorithm

— $O(r^2 \cdot T_{oracle})$, where $r$ is the rank, $T_{oracle}$ is the time to check independence. Polynomial!

Intersection of 3 matroids

— NP-hard. This is the boundary of polynomial-time solvability.

Formulas

A greedy algorithm makes the locally best choice at each step, never revisiting past decisions. Simple and fast — but not always optimal. The greedy algorithm for the knapsack problem does not produce an optimum. Kruskal’s greedy algorithm for MST — produces an optimum. Why? The answer is the mat...

Kruskal’s Algorithm: sort the edges by weight. Greedily add the minimum edge that does not create a cycle.

Cut Lemma: for any cut (S, V∖S), the minimum edge crossing the cut is included in the MST.

Proof: let $e^*$ be the minimum edge crossing the cut, and let $T$ be an MST not containing $e^*$. Add $e^*$ to $T$ → a cycle is formed, which crosses the cut at least in one other edge $e'$. Since $e^*$ is minimal in the cut: $w(e^*) \leq w(e')$. Replace $e'$ with $e^*$ in $T$ → new tree $T'$, w...

Formulas

A conventional approximation algorithm provides a fixed guarantee: for example, a 2-approximation. But what if we need more precision—for instance, a 1.01-approximation? PTAS (Polynomial-Time Approximation Scheme) is not a single algorithm, but an entire family of algorithms $A_\varepsilon$, para...

Important: the dependence on $\varepsilon$ can be arbitrary. For instance, $O(n^{1/\varepsilon})$ is a PTAS, but $O(2^{1/\varepsilon}\cdot n)$ is also a PTAS.

1. Find the maximum value $c_{\max} = \max c_i$ 2. Scale: $\tilde{c}_i = \left\lfloor c_i \cdot n/(\varepsilon \cdot c_{\max}) \right\rfloor$ (round down) 3. Solve DP with scaled values: time $O\left(n\cdot \sum \tilde{c}_i\right) = O\left(n\cdot n^2/\varepsilon\right) = O(n^3/\varepsilon)$ 4. Re...

Theorem: This is a $(1+\varepsilon)$-approximation. Proof: losses from scaling are $\leq \varepsilon \cdot OPT/n$ per item, total $\leq \varepsilon \cdot OPT$.

Definitions

Neighborhood selection is a key issue

— a small neighborhood → fast iteration but weak improvement. Large → slow but high-quality improvement.

2-opt neighborhood

— remove 2 edges from the tour and rebuild. For the route a→b→c→d→e→a: remove (b,c) and (d,e), add (b,d) and (c,e)—restructuring.

Practice

— 2-opt often gives tours that are 3-5% off the optimum. For a 1000-city problem works in seconds.

3-opt

— remove 3 edges—O(n³) operations. Better quality, more expensive.

Lin-Kernighan (LK)

— adaptive k-opt with "smart" candidate selection. Best-known TSP heuristic. Gives tours within 0.5-1% from optimum. Used in the LKH (Lin-Kernighan-Helsgott) program—industry standard.

Idea

— if local search gets stuck in $N_1$-optimum, "jump" randomly into the $N_2$ neighborhood and descend again. If a local optimum there—$N_3$ and so on.

Motivation

— basic LS may "oscillate" between several solutions. Tabu Search prohibits recently visited solutions.

Aspiration criterion

— allow tabu transition if it improves BestSolution. This lets us "accept" a good solution even if it is forbidden.

Cities

— A(0,0), B(2,0), C(2,2), D(0,2), E(1,1). Initial tour: A→B→C→D→E→A.

Result

— the initial tour A→B→C→D→E→A is 2-opt optimal for these cities.

Imagine the "landscape" of the solution space: each solution is a point, its "height" is the value of the objective function. We want to find a deep valley (minimum). Local search is a "descent across the landscape": we start from an arbitrary point and iteratively move to a "neighboring" point w...

Algorithm: 1. Current solution s = s₀ 2. While N(s) contains a better solution s': 3. Return s (local optimum)

Neighborhood selection is a key issue: a small neighborhood → fast iteration but weak improvement. Large → slow but high-quality improvement.

2-opt neighborhood: remove 2 edges from the tour and rebuild. For the route a→b→c→d→e→a: remove (b,c) and (d,e), add (b,d) and (c,e)—restructuring.

Definitions

Probability of accepting worsening

— $\exp(-\Delta/T)$. As $T \to \infty$: probability $\to 1$ (accept any step, random walk). As $T \to 0$: probability $\to 0$ (accept only improvements, standard local search).

Key property

— at high $T$ the algorithm “explores” the solution space, at low $T$ it “exploits” the good solutions found.

Geman-Geman Theorem (1984)

— if $T(k) = C/\log(1+k)$ (logarithmic cooling), SA converges to the global optimum with probability 1.

Practical convergence

— SA finds good (but not guaranteed optimal) solutions in reasonable time. For TSP: tours within 1-2% of the optimum in seconds.

Initial temperature $T_0$

— chosen so that the initial “acceptance rate” is about 80-90%. For example, you can run 1000 random steps, compute the average worsening $\bar{\Delta}$, and choose $T_0$ so that $\exp(-\bar{\Delta}/T_0) = 0.8$.

Cooling rate $\alpha$

— a trade-off between quality and time. $\alpha = 0.99$ means a long run, good quality. $\alpha = 0.9$ means quick, lower quality.

Number of iterations $L_k$ at each temperature

— often $L_k = n$ (problem size). More iterations at one temperature → better “equilibrium”.

Stopping criterion

— $T < T_{min}$, or no improvements in the last $k \cdot L_k$ iterations.

Task

— $n$ components on a chip, minimize the total length of connecting wires. This is called the Placement Problem in VLSI (Very Large Scale Integration).

Historical significance

— SA was first applied to VLSI Layout—IBM, 1983 (Kirkpatrick, Gelatt, Vecchi). The Science paper is one of the most cited in computer science. SA reduced wire length by 10-20% compared to deterministic methods.

Modern VLSI tools

— SA remains fundamental, but with dozens of improvements: adaptive temperature, parallel runs, “restart” on stagnation.

Conclusion

— SA is suitable for problems with a large number of local optima where implementation simplicity is important. Tabu—for structured problems with pronounced “memory”. For TSP, the best is LK heuristic.

Formulas

In metallurgy, “annealing” means heating a metal to a high temperature and then cooling it slowly. At high temperature, atoms have plenty of energy and can "jump" over energy barriers, finding a better crystalline structure. With slow cooling, they settle in the global energy minimum (the ideal c...

The idea of the metaheuristic Simulated Annealing (SA) is to imitate this process! The algorithm accepts "worsening" steps with decreasing probability—this allows “escaping” from local optima and eventually finding the global one.

Algorithm: 1. $s = s_0$ (initial solution), $T = T_0$, $BestS = s_0$ 2. While $T > T_{min}$: a. Repeat $L_k$ times: b. $T \leftarrow \alpha \cdot T$ 3. Return $BestS$

Probability of accepting worsening: $\exp(-\Delta/T)$. As $T \to \infty$: probability $\to 1$ (accept any step, random walk). As $T \to 0$: probability $\to 0$ (accept only improvements, standard local search).

Formulas

Natural evolution has solved an optimization problem of colossal complexity: creating beings capable of surviving in a changing environment. The mechanism: random mutations, gene recombination (crossover), natural selection. Genetic Algorithms (GA) imitate this process for optimization purposes. ...

Chromosome (individual): the encoding of a solution as a vector. For the TSP— a permutation of cities. For the knapsack problem—a binary string.

Fitness: value of the objective function. In GA, we usually work with maximization, so: fitness = −cost for minimization problems.

Problem: chromosome = permutation of cities π = (π₁, π₂, ..., πₙ). Crossover must produce valid permutations (each city appears exactly once).