ENMG 616 Notes, Spring 2011

Concepts Definition Theorem Hamiltonian Circuit Eulerian Circuit Concepts Example Function & Constraints Solution Linear Program Graphical (or Simplex) Non Linear Program Lagrange Multiplier Specialized Algorithm S-T Cut Capacity of an S-T cut The sum of the capacities of the forward arcs. Min Cut An S-T cut whose capacity is minimum among all S-T cuts cycle passing through every node in a graph G exactly once No Theorem - Basis of the Traveling Salesman Problem walk beginning and ending at the same node, but traversing each arc exactly once A connected simple graph G possesses an Eulerian Circuit if and only if the degree of each vertex in G is even. max Z = Yc*Xc + Yw*Xw; Cw*Xw + Cc*Xc <= 2; Xw + Xc >= 5; max Z = xy; x^2 + y^2 = H^2; Integer Program (Combinatorics [counting] optimization) Min Z = SUM[i, j](Cij*Xij); SUM[i](Xij) = 1; SUM[j](Xij) = 1; Traveling Salesman Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. Simulated Annealing Let Delta = increase in cost; cost differential by going through neighbor. If Delta<= 0, accept. If Delta > 0, accept with probability e^(-Delta/T) T = Temperature At start, T is high; most moves accepted. At end, T is low; most deteriorating moves rejected. T is controlled by a "cooling scheme". Tabu Search Search whole neighborhood to Make best move, but could lead to cycling! 1- Begin with a starting solution 2- Create a list of moves 3- Choose best permissible move 4- Check if stopping criterion is met Max-Flow, Min-Cut Theorem The maximum value of the flow from a source node S to a sink node T, in a capacitated network, equals the minimum capacity among all S-T cuts. Algorithm Hungarian Algorithm: Kuhn-Munkres Method O(n^3) Create Matrix, then: Step 0: Make sure the problem is a minimization problem. If maximization, convert to minimization. Step 1: For each row of the matrix, find the smallest element and subtract it from every element in its row. Go to Step 2. Step 2: Find a zero in the resulting matrix. If there is no starred zero in its row or column, star the zero. Repeat for each element in the matrix. Go to Step 3. Step 3: Cover each column containing a starred zero. If n columns are covered, the starred zeros describe a complete set of unique assignments. In this case, Go to DONE; otherwise, Go to Step 4 Step 4: Find a noncovered zero and prime it. If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6. Step 5: Construct a series of alternating primed and starred zeros as follows. Let Z0 represent the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until the series terminates at a primed zero that has no starred zero in its column. Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix. Return to Step 3. Step 6: Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column. Return to Step 4 without altering any stars, primes, or covered lines. Done: Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If cij is a starred zero, then the element associated with row i is assigned to the element associated with column j. Topological Sorting O(m + n) Initizalize: Determine Indegrees of each node; LIST: set of nodes with indegree of zero; NEXT = 0 is the label of nodes in topological order Select a node i from LIST and delete it; NEXT := NEXT +1; order(i) := NEXT; update indegrees; update LIST; Iterate until LIST is empty. Dijkstra O(n^2 + m) = O(n^2) (See figure for additional Implementation) INPUT: A directed network, with no negative cycles. OUTPUT: Shortest path tree rooted at node 1. Set S := {1}, T := N/ {1}; d(j) = inf, for all j in T; and d(1) := 0, pred(1) := 0. Update(1) While S != N: 1 let {i} in T be a node for which d(i) = min {d(j)|j in T}; S := S U i ;T := T/ {i}; 2 Update(i ). Label Correcting Each distance label takes O(2*n*C) iterations, in the worst case. Thus, updating all distance labels takes O(n^2 * C). Identifying the arc to update at each iteration takes O(m). Total Runtime: O(m*n^2 * C) Depending on C this may terminate in O(m*2^n) INPUT: A directed network, with no negative cycles. OUTPUT: Shortest path tree rooted at node s. Set d(j) = inf, for all j except the source "s"; d(s) := 0, pred(s) := 0. While some arc (i ; j) is such that d(j) > d(i ) + cij : 1 d(j) := d(i) + cij ; 2 pred(j) := i . Modified Label Correcting Initializing takes O(n) time. Each distance label takes O(2nC) iterations, in the worst case. Thus, updating all distance labels takes O(nmC). Total Runtime: O(nmC) Depending on C this algorithm may terminate in O(m2^n) time. Can we do better?Yes! FIFO INPUT: A directed network, with no negative cycles. OUTPUT: Shortest path tree rooted at node s. Initialize: Set d(j) = inf, for all j in N/s; d(s) := 0, pred(s) := 0; and LIST := s. While LIST not empty: Remove an element i from LIST. For each arc (i ; j) in A(i ), if d(j) > d(i) + cij then: 1 d(j) := d(i) + cij ; 2 pred(j) := i . 3 If j is not in LIST then add j to LIST. Floyd Warshall O(n^3) INPUT: A network, with no negative cycles. OUTPUT: Shortest path between all pairs of nodes. Establish two matrices, D and P; set d[i ; j ] := inf and p[i ; j ] := 0, for all [i ; j ] in N x N; For each i in N set d[i ; i ] := 0. For each arc (i ; j) in A set d[i ; j ] := Cij and p[i ; j ] := i. For each k from 1 to n: For each [i ; j ] in N x N, if d[i ; j ] > d[i ; k] + d[k; j ] then: 1 d[i ; j ] := d[i ; k] + d[k; j ]; 2 p[i ; j ] := p[k; j ]. Ford Fulkerson rij =? uij - xij + xji INPUT: A directed network, A, with nonnegative capacities on all arcs and no infinite paths between designated S and T. OUTPUT: Maximum Flow from S to T. Set x := 0. Create residual network, G(x). While G(x) contains a path from S to T: 1 Identify an augmenting path, P. 2 Set Delta(P) = min {rij | (i ; j) in P}. 3 Augment Delta(P) along P and update G(x) Labeling O(nmU) INPUT: A directed network, A, with nonnegative capacities on all arcs and distance labels on all nodes including designated S and T. OUTPUT: Maximum Flow from S to T. Label node T. While T is labeled: Unlabel all nodes; Set pred(j) := 0 for each j in N Label node S and set LIST := {S} While LIST not empty and T is unlabeled: Remove a node i from LIST ; For each (i ; j) in the residual, if node j is unlabeled, then set pred(j) := i and label node j . Add j to LIST . If T is labeled, augment the path from S to T de ned by the predecessors. Shortest Augmenting Path O(n^2 * m) INPUT: A directed network, A, with nonnegative capacities on all arcs and distance labels on all nodes including designated S and T. OUTPUT: Maximum Flow from S to T. Set x:=0; i = s; While d(s) < n: if there is a node with d(i) <= d(s) and no admissible arcs from j then: Relabel(i ) else find an admissible path from s to t and augment flow along the path. _________ Relabel(i) If there are no admissible arcs coming out of node i , then d(i) = 1 + min {d(j) | rij > 0} If d(s) > n - 1, then quit. Preflow/Push O(n^2 * m) INPUT: A directed network, A, with nonnegative capacities on all arcs and designated S and T. OUTPUT: Maximum Flow from S to T. PreFlow; While there is a node i with e(i) > 0: //e(i) = excess on node I; 1 Select an active node i ; 2 push/relabel(i); PreFlow Set x := 0; Compute the exact distance labels, d(i); Set e(i) := 0 for all i ; Set x[Sj] := U[Sj] and e(j) := U[Sj] for each arc (S; j) in A; Set d(S) := n; push/relabel(i) If the network contains an admissible arc (i ; j ), then push Delta := min {e(i); rij} units of flow from i to j ; Set e(i) := e(i) - Delta, and e(j) := e(j) + Delta; If there is no admissible arc (i ; j ), then set d(i) := min {d(j) + 1 | (i ; j) in A; rij > 0}