Max Flow Problems

Max Flow Problems

Chapter Overview

• Max flow problems are another category of problems in linear programming modeled on networks or graphs, following previous topics such as transportation, transshipment, assignment, shortest path, and minimum spanning tree.

• All discussed problems, including max flow, can be solved using logical reasoning and arithmetic without the need for special algorithms.

Max Flow Model Overview

• Model: In max flow problems, the capacity of each arc (or edge) in the flow network is specified. The primary goal is to determine the maximum flow from a specified starting node (source) to a specified ending node (sink).

• Applications:

  • Flow of water, gas, or oil within pipelines.

  • Processing forms through various systems.

  • Managing traffic within a transportation network.

  • Distribution of products in a manufacturing environment.

Problem Definition

• Statement: Given a graph where each arc has a specific capacity or upper limit on flow, the objective is to maximize the flow from a source node (Node 1) to a sink node (Node n).

• The problem does not take costs into account.

Flow Variables and Constraints

• Let the flow on an arc (i, j) be represented by X_{ij}.

• The constraints governing the problem include typical linear programming constraints:

  • Upper bound constraints for flow on each arc:
    $X<em>{ij} \leq U</em>{ij}$ (where U_{ij} is the capacity of arc (i, j)).

  • Flow conservation constraints for each node, ensuring that the total incoming flow equals the total outgoing flow.

Revising the Graph for Formulation

• To create the mathematical representation, modify the graph by introducing a "return arc" directed from the sink back to the source. This arc is not a part of the actual flow network but serves to cycle back any excess flow for modeling purposes.

• The objective function is formulated to maximize the flow on the return arc.

Textbook Notation

• Some text references different notations for representing arc capacities. However, the method of labeling is not elaborated in this material.

Max Flow LP Formulation: Example Case

• Scenario: The Scott Tractor Company transports tractor parts from Omaha (Node 1) to St. Louis (Node 6) utilizing a railroad system with certain capacity limitations.

• Graph: The accompanying graph depicts the network layout including the return arc which is solely for modeling methods and does not reflect actual changes in capacity or flow.

Decision Variables

• The flow on each arc is denoted as:

  • $X_{ij}$ represents the number of cars transported on arc (i, j).

Objective Function

• Maximize the flow on the return arc:

  • $\text{Max } Z = X_{61}$

Flow Constraints

• Constraints are established based on the inflow and outflow for each node:

  • Node 1: $X<em>{61} = X</em>{12} + X<em>{13} + X</em>{14}$

  • Node 2: $X<em>{12} + X</em>{42} - X<em>{24} - X</em>{25} = 0$

  • Node 3: $X<em>{13} + X</em>{43} - X<em>{34} - X</em>{36} = 0$

  • Node 4: $X<em>{14} + X</em>{24} + X<em>{34} - X</em>{42} - X<em>{43} - X</em>{46} = 0$

  • Node 5: $X<em>{25} - X</em>{56} = 0$

  • Node 6: $X<em>{36} + X</em>{46} + X<em>{56} - X</em>{61} = 0$

Upper Bound Constraints

• The following upper bounds apply for each arc:

  • $X_{12} \leq 6$

  • $X_{13} \leq 7$

  • $X_{14} \leq 4$

  • $X_{24} \leq 3$

  • $X_{25} \leq 8$

  • $X_{34} \leq 2$

  • $X_{36} \leq 6$

  • $X_{42} \leq 3$

  • $X_{43} \leq 2$

  • $X_{46} \leq 5$

  • $X_{56} \leq 4$

  • $X_{61} \leq 17$

• Each flow variable is also constrained to be non-negative: $X_{ij} \geq 0$.

Ford-Fulkerson Algorithm

• The Ford-Fulkerson method, established in 1956, provides a rapid and effective way to compute max flow. Note that the notation applied in this document may differ from the textbook.

General Approach

• Initialization: Set flow on each arc equal to zero at the start.

• Finding Paths: Search for new paths through which additional material can flow from the source to sink node (termed breakthroughs).

  • If an arc is below capacity, it is eligible for increased flow; if previously set flow is positive, it may be decreased to find enhanced solutions.

• Update Flows: Upon finding a breakthrough, adjust flow values according to the smallest change allow on each arc in the path until no valid breakthroughs remain, indicating the maximum flow.

Detailed Iterative Example

• The iterative process involves creating residual graphs that display how much the flow on each arc can be modified to capture the adjustments needed for maximizing flow.

• Each iteration identifies breakthroughs in the residual graph, updating flows based on the minimum allowable change across those breakthroughs.

Homework Assignments

• Complete the provided exercises from Chapter 7, focusing on problems 28 through 31 located on pages 322-341.

• Additional problems may involve networks that mimic simpler structures for practice and preparation for quizzes and exams.