9.3. Setting Up Linear Programming Variables

For our next example of linear programming, we will look at a problem involving graphs and networks to do with Network Bandwidth. Suppose we have a small communication network involving three users: A, B, and C, connected through switches a, b, and c.

In this example, we have a communication network that consists of three users (A, B, and C). These users are connected by switches (a, b, and c). The goal of this setup is to manage the network bandwidth efficiently so that each pair of users (A to B, B to C, and A to C) receives at least a minimum bandwidth of 2 Mbps. This means that when User A communicates with User B, or when User B communicates with User C, or when User A communicates with User C, the connection should provide a minimum of 2 Megabits per second.

Think of it like a water supply system where three houses (A, B, and C) need a minimum flow of water (2 liters per minute) from one to another through pipes (switches a, b, and c). To ensure each house gets enough water, we have to manage how much water flows through each pipe carefully.

Our aim is to combine the capacity of the red and the green routes for each pair, ensuring that the combinations of the capacities add up to at least 2 Mbps. The challenge comes from the constraints that the links have a maximum capacity.

To meet the bandwidth requirement, we have to combine the available capacities of different routes (the red and the green routes). Each user pairing can use both a direct route and an indirect route, and the total bandwidth allocated to each pair must be at least 2 Mbps. However, we also have constraints because the links have a maximum transmission capacity that cannot be exceeded. For example, if the link between B and C can transmit a maximum of 13 Mbps total for all connections, this determines the maximum amount of data that can flow through it.

Imagine a highway system where different routes (red and green, representing different paths) need to be used to ensure all cars (data) can travel from one city to another. If each highway has a maximum number of cars it can handle (link capacity), we need to allocate the cars efficiently to meet the demand (2 Mbps) without exceeding the maximum allowed on any highway.

We will use variables to represent the quantity of data flowing through each route. For instance, let x represent the data flowing directly from A to B, and y represent data flowing indirectly from A to B. Similar variables can be defined for other user pairs.

To manage and optimize the allocation of bandwidth, we introduce variables. For instance, let 'x_AB' denote the amount of data sent directly from A to B, while 'y_AB' represents the amount sent indirectly. This differentiation allows us to track and control the flow effectively. We will have six variables in total to describe different routes between the pairs of users, namely x and y for each of the three connections (A to B, B to C, A to C).

This is like assigning drivers (variables) to different routes (paths) in a delivery system. Each driver has a specific route they must take (direct or indirect delivery), and by assigning them carefully, we ensure that all packages are delivered on time, within the capacity limits of the roads they use.

The variables must satisfy constraints based on the capacities of the links. For example, the total flow through the link from b to B cannot exceed 10 Mbps, which includes contributions from x_AB, y_AB, x_BC, and y_BC.

The next step is to set up constraints. These constraints make sure that the combined flow on any link (like the link from b to B) does not exceed its maximum capacity. For instance, if we have x_AB (direct A to B), y_AB (indirect A to B), x_BC (direct B to C), and y_BC (indirect B to C), the sum of these flows must be less than or equal to the maximum capacity of the link, which is 10 Mbps in this case. We do this for all links that connect the users.

Imagine you have a carpool where each car can only carry a certain number of passengers (link capacity). If one car is taking some passengers from A to B and others from B to C, you need to ensure the total number of passengers in each car doesn’t exceed its maximum capacity.

The objective function will be to maximize revenue by allocating bandwidth efficiently. Each link provides different revenue rates depending on the volume of traffic.

We now need to define our objective function, which in this case is to maximize revenue. Each user pair has a different revenue rate. For example, sending data from A to B yields 300 rupees per Mbps, while from B to C it yields 200 rupees, and from A to C it yields 400 rupees. Therefore, our goal is to allocate bandwidth such that we maximize the total revenue based on these rates, while still meeting the minimum bandwidth requirements and respecting the capacity constraints.

Think of it like a business where different products have different prices. If you want to make the most profit, you need to figure out how to allocate your resources (in this case, bandwidth) to maximize total sales while ensuring that each product still meets customer demand.

--