Course 8 : Minimum cost flow problem

Author: OptimizationCity Group

Introduction

So far, we have studied the problem of linear programming in general. In this section, we will examine specific types of linear programming problems. In this section, we first examined the general model of minimum cost flow, and then we will examine the specific model of flow in the network, here the transportation problem.

Minumum cost flow problem

In the problem of minimum cost flow, we are looking for homogeneous product distribution from the factory (origin) to the sales market (destination). Suppose the number of products manufactored in each factory and the number of required products are known. Also, it is not necessary to send the products directly to the destinations, but it is possible to send it to the distribution centers through an intermediate point. In addition, transportation lines are limited in terms of line capacity. The goal in this issue is to minimize the cost of transporting products.

Consider a numerical example of the minimum cost flow problem in the figure below. Nodes are represented by numbered circles and arcs by arrows. Arcs are directional. For example, materials can be sent from node 1 to node 2, but this is not possible from node 2 to node 1. We denote the arc from node i to node j as i-j.

In the above figure, each arc is given a capacity and cost per unit of transportation, which is given next to each arc. For example, in arc (2-4), the flow can be from 0 to 4 units, and the cost of each unit passing through this arc is $2. The symbol ∞ means unlimited capacity. Finally, the numbers in parentheses next to the nodes show the amount of supply and demand. In this figure, node 1 is the origin and the amount of supply is equal to 20 units, and nodes 4 and 5 are the destinations that need 5 and 15 units, and it is the demand that is indicated by the sign -.

In the minimum cost flow problem, the goal is to find the flow pattern with minimum cost. To transform the problem into linear programming, suppose:

x_ij: is the number of units transported from node i to node j using arc i-j.

The linear programming model of minimum cost flow is presented as follows.

Equations 1 to 5 are the flow balance equations in the network. For example, the balance flow equation at node 1 is as follows.

The above equation states that the output flow from node 1 (x₁₂+x₁₃) should be equal to the supply of node 1 (20).

The balance equation in node 2 states that the input flow to node 2 (x₁₂ ) is equal to the output flow from node 2 (x₂₃+x₂₄+x₂₅ ).

The minimum cost flow model in the network has a special structure that is used to provide the solution order. Flow variables x_ij in balance equations only get 0, +1 and -1 coefficients. In addition, they appear exactly in two balance equations: once with a coefficient of +1 corresponding to the node from which they originate and -1 corresponding to the node to which they enter. According to the above, the general form of the Minumum Cost Flow is expressed as follows.

In this section, the simplex network method is presented using the network concepts that have been described yet. The minimum cost flow is more complicated than the transportation problem because the intermadiate nodes and each arc has capacity. To solve this problem using the simplex method, a intial feasible solution is needed. Determining this solution is slightly different from the transportation problem and requires a lot of efforts. Initially, assume that the initial feasible solution is available. We describe the simplex of minimum cost flow in the example.

In the figure, there is (A, B) on each arc, where A represents the capacity of the arc and B represents the cost of passing one unit through the arc. Consider the initial solution below.

In the above figure, arcs _._._ indicate non-basic arcs that are at their upper bound, and arcs ___ (solid arcs) are basic arcs. Solid arcs form a spanning tree for the network, which is the basic solution. To determine whether the current solution is an optimal basic solution, the cost c̄_ij of all non-basic arcs must be calculated. For this purpose, we first calculate y_i (i=1,2,…,n). If the y_i applies in the following relations:

Then the current basic solution is optimal. To calculate the y_is, one of the y_is can be arbitrarily considered equal to zero and the rest of the y_is can be calculated using the relationship c_ij-y_i+y_j=0. The y_is are as follows.

The cost of c̄_ij for non-basic variables is as follows:

To improve the current solution based on the above c̄_ij, we have two solutions:

1- Increasing the arc flow that has a negative c̄_ij and is now at its lower bound.

2- Reducing the arc flow that has a positive c̄_ij and is now at its upper bound.

According to these two cases, the only candidate is the arc (4,5). In the figure below, the arc (4,5) was added to the network to determine which arc should be left out of the basic solution.

The value of θ can be increased up to 2, in which case the arc (2,4) reaches its upper bound and leaves the basic solution. Therefore, the current basic solution is as follows:

According to the assumption y₂=0, the value of y_i can be calculated from the equations c_ij-y_i+y_j=0 for the basic variables as follows.

The c̄_ij costs for determining the input arc to the basic solution and the output arc from the basic solution are as follows.

At this stage, the arc (2,3) enters the basic solution. To determine the output arc, it is done as follows.

The value of θ can be increased up to 8, in which case the arc (2,5) is removed from the basic solution, and therefore the basic solution is as follows.

Based on the basic solution, y_i‘s are calculated.

According to the y_is, the amount of c̄_ij is as follows:

Because for non-basic variables, c̄_ij‘s are negative and the flow of arc is at the upper bound; and for basic variables, c̄_ij‘s are positive and the flow of arc is at the lower bound, the current solution is the optimal solution.

Example:

Solve the minimum cost flow problem in the following network using the simplex method. Use the given tree for the initial solution.

Initial solution:

Solution:

The value of the objective function for the initial answer is equal to 380. Assuming y₂=0, we can calculate the y_is based on c_ij-y_i+y_j=0.

The c̄_ij for non-base arcs are as follows.

Four arcs can enter the basic solution. The arc (2,4) is selected. The output arc is selected as follows.

Since the arc (2,5) reaches its upper bound, this arc leaves the basic solution. Therefore, the current basic solution is as follows.

In this solution, the value of the objective function is equal to 295. According to the assumption y₂=0, the value of y_i can be calculated from the equations c_ij-y_i+y_j =0 for the basic arcs as follows.

The c̄_ij  for non-base arcs is as follows.

The arc (3,5) can enter the basic solutions.

With θ=5, the arc (4,5) leaves the base and the arc (3,5) enters the base. With this change, the current solution is as follows.

In this solution, the value of the objective function is equal to 255. According to the assumption y₂=0, the value of y_i can be calculated from the equations c_ij-y_i+y_j =0 for the basic arcs as follows.

The c̄_ij  for non-base arcs is as follows.

The arc (1,3) can enter the basic solutions.

With θ=10, the arc (3,2) leaves the base and the arc (1,3) enters the base. Therefore, the current solution is as follows.

In this solution, the value of the objective function is equal to 155. According to the assumption y₂=0, the value of y_i can be calculated from the equations c_ij-y_i+y_j =0 for the basic arcs as follows.

The c̄_ij  for non-base arcs is as follows.

The arc (5,6) enters the base. The output arc is calculated as follows.

With θ=0, the arc (1,2) leaves the base. Therefore, the current solution is as follows.

In this solution, the value of the objective function is equal to 155. According to the assumption y₂=0, the value of y_i can be calculated from the equations c_ij-y_i+y_j =0 for the basic arcs as follows.

The c̄_ij for non-base arcs is as follows.

The optimality condition is satisfied, so we reached the optimal solution.

Note: because it is θ=0 in the current step, it means the state of being degenerate, and no improvement in the value of the objective function has occurred. The optimal solution is as follows.

Create an initial feasible basic solution

In the previous example, the initial feasible basic solution was given by default. But it will not always be like this and it will not be easy to find such an solution, especially for large networks. In this section, we will present a method to obtain a initial feasible basic solution. For this purpose, an artificial node is created and we call it V_n+1. If a node like i has a supply, we consider an arc from i to V_n+1 with a cost of one. If a node such as i has demand or an intermediate node (no supply or no demand), we create an arc from node V_n+1 to i with a cost of 1 (one). At the end, we consider the cost of other arcs equal to zero. For this network, the simplex algorithm has been implemented until the value of the optimal objective function is equal to zero, in which case we have reached a initial feasible basic solution and we can start the simplex algorithm with this solution.

Example:

For the following network, find a intial feasible basic solution.

Solution:

We create an artificial node 7 and consider an arc from node 1 to 7 and from 7 to other nodes with a cost of 1.

The basic solution is as follows:

Assuming y₇=0, the y_i coefficients can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Because the arc (1,2) is in the lower bound and c̄_ij< 0, therefore this arc enters the base. The output arc from the base is obtained as follows.

The arc (7,2) leaves the base. Therefore, the current basic solution is as follows.

In this iteration, the value of the objective function is equal to 40. Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Because the arc (1,3) is in the lower bound and c̄_ij< 0 , therefore this arc enters the base. The output arc from the base is obtained as follows.

The arc (7,3) leaves the base. Therefore, the current basic solution is as follows.

In this iteration, the value of the objective function is equal to 40. Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Because the arc (2,4) is in the lower bound and c̄_ij< 0, therefore this arc enters the base. The output arc from the base is obtained as follows.

The arc (7,4) leaves the base. Therefore, the current basic solution is as follows.

In this iteration, the value of the objective function is equal to 40. Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij for non-basic arcs is as follows.

Because the arc (4,6) is in the lower bound and c̄_ij < 0 , therefore this arc enters the base. The output arc from the base is obtained as follows.

With θ=10, the arc (4,6) enters the base and immediately reaches its upper bound and leaves the base. With this change, the current solution becomes as follows and the value of the objective is equal to 20.

Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Because the arc (4,6) is at its upper bound and c̄_ij < 0 , therefore, this arc has optimal conditions. Because the arc (3,5) is at its lower bound and is c̄_ij < 0 , therefore this arc enters the base. The output arc from the base is obtained as follows.

The arc (7,5) leaves the base. Therefore, the current basic solution is as follows and the value of the objective is equal to 20.

Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Because the arc (5,6) is at its lower bound and is c̄_ij < 0, therefore this arc enters the base. The output arc from the base is obtained as follows.

The arc (1,7) leaves the base. Therefore, the current basic solution is as follows and the value of the objective is equal to 0.

Assuming y₇=0, the y_is can be obtained based on c_ij-y_i+y_j=0.

The cost c̄_ij  for non-basic arcs is as follows.

Optimal conditions meet. Therefore, the initial feasible basic solution is as follows. It should be noted that the value of the optimal objective function is equal to zero, thereofore there is no need for artificial arcs anymore and node 7 can be removed from the network and the arc (7,6) is deleted, too.