L. Vandenberghe EE236A (Fall 2013-14)Lecture 17Network flow optimization• minimum cost network flows• total unimodular i ty• examples17–1Networksnetwork (directed graph, digraph): m nodes connected by n directed arcs• arcs are ordered pairs (i, j) of nodes• we assume there is at most one arc from node i to node j• there are no loops (arcs (i, i))arc-node incidence matrix: m × n matrix A with en tri esAij=1 if arc j starts at node i−1 if arc j ends at node i0 otherwiseNetwork flow optimization 17–2Example12345612345678A =1 1 0 0 0 0 0 −1−1 0 1 0 0 0 0 10 −1 −1 −1 1 1 0 00 0 0 1 0 0 −1 00 0 0 0 0 −1 1 00 0 0 0 −1 0 0 0Network flow optimization 17–3Network flowflow vector x ∈ Rn• xj: flow (of mate ri al , traffic, charge, information, . . . ) through arc j• posi tiv e if in direction of arc; negative otherwisetotal flow leaving node i:nXj=1Aijxj= (Ax)iixjAij= −1xkAik= 1Network flow optimization 17–4External supplysupply vector b ∈ Rm• biis external supply at node i (negative birepresents external de ma nd )• must satisfy 1Tb = 0 (total supply = total demand )ixjAij= −1xkAik= 1bibalance equations:Ax = bNetwork flow optimization 17–5Minimum cost network flow problemminimize cTxsubject to Ax = bl ≤ x ≤ u• ciis unit cost of flow through arc i• ljand ujare limits on flow through arc j (typically, lj≤ 0, uj≥ 0)• we assume lj< uj, but allow lj= −∞ and uj= ∞ to simplify notat ionincludes many network optimizati on problems as special casesNetwork flow optimization 17–6Maximum flow problemmaximize flow f rom node 1 (source) to node m (sink) through the network1mt tmaximize tsubject to Ax = tel ≤ x ≤ uwhere e = (1, 0, . . . , 0, −1)Network flow optimization 17–7Formulation as minimum cost flow problem1martificial arc n + 1minimize −tsubject toA −e xt= 0l ≤ x ≤ uNetwork flow optimization 17–8Outline• minimum cost network flows• total unimodularity• examplesTotally unimodular matrixa matrix is totally unimodular if all its minors are −1, 0, or 1(a minor is the d ete rm in an t of a sq u ar e submatrix)examples• the matrix1 0 −1 0 10 −1 1 −1 −10 0 0 1 1• node- arc inciden ce matrix of a dire cted graph (proof on next page)properti es of a totall y unimodular matrix A• the entries Aij(i.e., its minors of order 1) are −1, 0, or 1• the inverse of any nonsingular square submatrix of A has entries ±1, 0Network flow optimization 17–9proof: let A be an m × n node -ar c incidence matrix• the entries of A are −1, 0, or 1• A has exactly two nonz er o entries (−1 and 1) per columnconsider a k × k submatrix B of A• if B has a zero colum n, its determinant is zero• if all columns of B have two nonzero entries, then 1TB = 0, det B = 0• otherwise B has a column, say column j, with one nonzero entry Bij, sodet B = (−1)i+jBijdet CC is square of order k − 1, obtain ed by deleting row i and column j of Bhence, can show by induction on k that all minors of A are ±1 or 0Network flow optimization 17–10Integrality of extrem e pointslet P be a polyhedron in Rndefined byAx = b, l ≤ x ≤ uwhere• A is totally unimodular• b is an integer ve ctor• the finite lower bounds lkand finite upper bou nd s ukare integersthen all the extreme points of P are integer vectorsNetwork flow optimization 17–11proof: apply rank test to d ete rm in e whether ˆx ∈ P is an extreme point• partition {1, 2, . . . , n} in three sets J0, J−, J+withlk< ˆxk< ukfor k ∈ J0ˆxk= lkfor k ∈ J−ˆxk= ukfor k ∈ J+let A0, A−, A+be the submatrices of A with columns in J0, J−, J+• ˆx is an extreme poi nt if and only ifrank0 I 00 0 −IA0A−A+= n ⇐⇒ A0has full column rankintegrality of ˆx then follows from A0ˆxJ0= b − A−ˆxJ−− A+ˆxJ+• right-hand side is an integral vector (ˆxkis integer for k ∈ J−∪ J+)• inverse of any nonsingular submatrix of A0has integer entriesNetwork flow optimization 17–12Implications for combinatorial optimi zat ionminimize cTxsubject to Ax = bl ≤ x ≤ ux ∈ Zn• an integer linear program, very difficult in gen era l• equivalent to its linear program relaxationminimize cTxsubject to Ax = bl ≤ x ≤ uif A is totally un im odular and b, l, u are i nte ger vectors(extreme optim al solution of the relaxation is optimal f or the integer LP )Network flow optimization 17–13Outline• minimum cost network flows• total unimodularity• examplesShortest path problemshortest path in directed graph with node-arc incidence matrix A• (forward) paths from node 1 to m can be repr ese nte d by vectors x withAx = (1, 0, . . . , 0, −1), x ∈ {0, 1}n• shortest path is solution ofminimize 1Txsubject to Ax = (1, 0, . . . , 0, −1)x ∈ {0, 1}nLP formulationminimize 1Txsubject to Ax = (1, 0, . . . , 0, −1)0 ≤ x ≤ 1extreme optima l solutions satisfy xi∈ {0, 1}Network flow optimization 17–14Birkhoff theoremdoubly stochastic matrix: N × N matrices X with 0 ≤ Xij≤ 1 andNXi=1Xij= 1, j = 1, . . . , N,NXj=1Xij= 1, i = 1, . . . , Nset of doubly stochastic matrices is a pol yh edr on P in RN×Ntheorem (p.3–29): the extrem e points of P are the permutation matricesproof : interpret X as network fl ow• N input nodes, N outp ut nodes• Xijis flow from input i to output jhence extrem e X has integer entries123123111111example (N = 3)Network flow optimization 17–15Weighted bipartite matching• match N per son s to N tasks• each person assigned to one task; each task assi gne d to one person• cost of matching person i to t ask j is AijLP formulationminimizeNPi,j=1AijXijsubject toNPi=1Xij= 1, j = 1, . . . , NNPj=1Xij= 1, i = 1, . . . , N0 ≤ Xij≤ 1, i, j = 1, . . . , Nintegrality: ext rem e optimal solution X has entries Xij∈ {0, 1}Network flow optimization
View Full Document
Unlocking...