10.1. Bandwidth Allocation Problem

In the bandwidth allocation problem, we use one variable per path in order to encode a network flow problem as a linear program and we argued that does not an efficient way to do it. So, let us look at a mode direct way to represent network flows in terms of linear programs.

So, suppose we have an oil network which is shown as given in this directed graph. So, we have a source vertex s and we have a target or a sink vertex t and our aim is to shift as much oil as we can from s to t given the pipes that we are given.

In this section, we're introduced to the concept of network flow as it relates to the bandwidth allocation problem. The focus is on efficiently representing these flows using linear programming instead of using multiple variables for each path, which can be inefficient. We visualize this using an oil network, where the source (s) represents the start of the flow, and the sink (t) is the endpoint. Our goal in this network is to transfer as much oil as possible from the source to the sink through various pathways (represented as edges in a directed graph).

Imagine a city's water supply system. The water source (like a reservoir) is akin to the 's' in our network, and the point where water is consumed (like a households or businesses) is similar to 't'. The pipes (edges) connecting these points have certain capacities (how much water they can carry) just like our oil network. Our goal is to efficiently manage the water flow through the pipes to ensure every home gets enough water.

So, of course, one property of a flow is that it is must flow, so I cannot keep any quantity at any intermediate node. So, anything that enters b must leave b, anything that enters d must leave d. If we try to do this, then for instance this green quantity represents one possible flow, I send two units from s to a, 1 from s to b, and 4 from s to c and you can check that these interact with in the capacity.

A fundamental principle in network flows is flow conservation, meaning that whatever enters a node must also leave that node. This principle prevents storage at intermediate nodes in the network. For example, if '2 units of flow' enters node 'b', '2 units' must also exit node 'b'. The focus here is on ensuring that the quantities of flow sent from 's' to various nodes (like 'a', 'b', and 'c') do not exceed the edge capacities. If the total outgoing flow matches the incoming flow at every node, then we can be confident we have a valid flow.

Consider a highway system where each junction (like our nodes) allows cars to enter and exit. If 5 cars enter a junction, they must exit from that junction as well. You can think of this like a turnstile at a concert; if five people come in, five must also exit, as the turnstile only allows flow through. This setup helps us manage traffic efficiently and ensures that we never have a 'traffic jam' at the junction (or node) where cars (or flow) are stuck.

But, the question is, is this the maximum? How do we know that we achieve the maximum or not? The problem just to face it formally is that we have given a special type of graph, it is a directed graph and it has two special nodes, a source and a sink. ... we want to optimize the total volume on flow, the total volume of flow is the amount of flow which is coming out of here which is also of course, the amount of which is going that in the flow can be lost.

In determining the maximum flow, we must assess whether the flow we've achieved (like our previous example of 7 units) is indeed the highest possible from 's' to 't'. Representing the flow in a directed graph allows us to set clear constraints, such as the capacities of edges and the requirement of flow conservation. Our goal transcends merely achieving flow; it instead focuses on maximizing this flow subject to the outlined conditions, which leads us to construct and solve linear programming problems.

Think about a school’s bus system transporting students to different locations. The bus can only take so many students at a time (capacity of the edge). We want to maximize how many students can be transported throughout the day without having extra buses waiting (which would represent flow conservation). Identifying the optimal path of bus routes is crucial to ensuring that every student gets to their destination efficiently while adhering to capacity restrictions.

So, now we have this formulation remain, so we can now set up a linear program,... So, we have 11 edges and therefore, we have 11 variables in this linear program. Now, what can we do in this variables,...we must have a conservation of flow at each internal node.

To approach solving the flow maximization problem, we set up a linear program where each variable corresponds to flow on an edge. We define constraints for each variable based on edge capacities and ensure flow conservation at every internal node. This structured approach allows us to mathematically determine the optimal flow pathways through the network, leveraging the principles of linear programming to find a solution efficiently.

Imagine setting up a budget plan for a school event where each expense (like catering, decor, and transportation) has a limit (like the edge capacities). Each part of the budget (variable) gets defined, and you add limits based on actual costs (capacity constraints). You then need to balance the budget so that each department doesn’t overspend while still maximizing the event's overall effectiveness (the flow).

So, this is an algorithm called the Ford-Fulkerson algorithm which actually tries to directly solve a network flow problem by gradually building up an optimum flow. So, the algorithm assume you starts with 0 flow and then you choose some path on which there is pair capacity and then on this path, you augment the flow as much as possible...

The Ford-Fulkerson algorithm provides a practical means to compute the maximum flow in a flow network. By starting at an initial flow of zero, the algorithm identifies paths where flow can still be added (it's feasible) and then incrementally increases the flow along these paths until no further augmentation is possible. This step-by-step growth ensures that we explore various feasible paths, approaching the overall maximum flow while adhering to capacity constraints.

Think of the Ford-Fulkerson algorithm as a team of chefs working in a kitchen. They start with zero ingredients ready (like our zero flow), but as they identify recipes (paths), they begin preparing meals by incrementally adding ingredients (increasing flow). Each dish reflects a unique path in maximizing what can be served. Eventually, when all ingredients are used up and all recipes are served to capacity, the kitchen reaches its maximum output, reflecting the maximum flow in our network.

--