Bridging Continuous and Discrete Optimization
Nisheeth K. Vishnoi · Cambridge University Press eBooks · 2021
Example: The Maximum Flow ProblemWe illustrate the interplay between continuous and discrete optimization through the st-maximum flow problem on undirected graphs.The maximum flow problem.Given an undirected graph G = (V ,E) with n |V | and m |E|, we first define the vertex-edge incidence matrix B ∈ R n×m associated to it.Direct each edge i ∈ E arbitrarily and let i + denote the head vertex of i and i -denote its tail vertex.For every edge i, the matrix B contains a column b i e i +e i -∈ R n , where {e j } j ∈[n] are the standard basis vectors for R n .Given s t ∈ V , an s -t-flow in G is an assignment x : E → R that satisfies the following conservation of flow property: For all vertices j ∈ V \ {s,t}, we require that the incoming flow is equal to the outgoing flow, i.e., e j ,Bx = 0.An st-flow is said to be feasible iffor all i ∈ E, i.e., the magnitude of the flow in each edge respects its capacity (1 here).The objective of the st-maximum flow problem is to find a feasible st-flow in G that maximizes the flow out of s, i.e., the value