麻省理工 网络优化 课程课件13globalmincutalgorithm.pdfVIP

15.082 and 6.855J April 1, 2003 The Global Min Cut problem 1 Global Min cut INPUT: A network G = (N, A) OUTPUT: A cut (S, N\S) such that cap(S, N\S) is minimum. Note: We do not assume that there is a source node s and destination node t. Typically, but not always, the network is undirected. 2 Application to the TSP: Traveling Salesman Problem What is a minimum length tour that visits each point? 3 An integer programming formulation Let xij = 1 if there is an arc (i,j) in the tour T x = 0 otherwise. ij There are two arcs incident to node i For every cutset (S, N-S), there are two arcs from S to N-S. ∑j xij 2 for each node i (1) ∑∈ , ∈ \ xij ≥2 for each node set S ≠N (2) i S j N S (3) xij xji for each i,j 0 ≤x ≤1 x integer for each i,j (4) ij ij 4 Any integer solution will be a tour S Any solution to (1) and (3) and (4) will be the union of disjoint directed cycles. But 2 or more disjoint cycles violates (2). 5 More on the formulation Suppose that one has a solution to the linear program satisfying (1), (3) and (4) but relaxing the integrality constraints. Separation problem: Either show that all constraints in