Note that the BFS of minimum cut and the BFS of max flow arrive at the same value. In linear programming terms, it is the Best Feasible Solution (BFS) Here are two such solutions:Ĭan we do better than B? The answer is no: is the minimum cut possible in the current graph. Let X ⊂ E represent the number of edges you need to remove to eliminate a connection s → t. ![]() The solution to LP tells us that no, eight is the maximum possible flow.Ĭonsider another, seemingly unrelated, problem we might wish to solve: separability. ![]() To answer rigorously, we formalize max flow as a linear optimization problem: Solution B improves on A by pushing volume onto the b → c railway. Here are two possible solutions to flow allocation: Flow is conserved: stuff leaving a city must equal the amount of stuff arriving.Flow cannot exceed the capacity of the railroad.This quantity, which we will call flow, must respect the following properties: To do this, we label each edge with the amount of goods we intend to ship on that railroad. We desire to maximize volume of goods transported s → t. The flow allocation problem defines source and termination vertices, s and t. We assume no available storage at the intermediate cities. The bottleneck is solely the capacities, and not production and consumption. The capacity of each edge was the amount of goods that particular railroad could transport in a given day. Vertices are interpreted as cities, and edges are railroads connecting two cities. Tolstoy published his Methods of finding the minimal total kilometrage in cargo-transportation planning in space, where he formalized the problem as follows. The problem of flow was originally studied in the context of the USSR railway system in the 1930s. Today, I introduce the concept of duality.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |