## `Network::minCost` -- computes a minimal cost flow

#### Introduction

``Network::minCost`(G)` computes a minimal cost flow for the network `G`, taking into consideration supply and demand, capacities and transportation cost.

#### Call(s)

`Network::minCost(G)`

#### Parameters

`G` | - | network

#### Returns

a sequence, consisting of a number and two tables

#### Details

- ``Network::minCost`(G)` computes a minimal cost flow in `G` with respect to the edge capacities, the edge weights and the vertex weights of `G`.

  The vertex weights are interpreted as supply and demand. The edge capacities give restrictions for the flow on every edge. The edge weights are the cost for one unit flow over an edge.

  The algorithm computes a flow, if there is any, which is possible and satisfactory, i.e., it is within the supply and demand range, which respects the capacities and which has minimal cost.

- The result of ``Network::minCost`(G)` is a sequence of the price of a minimal cost flow, the minimal cost flow itself (in form of table), and a table with the dual prices.

#### Example 1

We construct a network with five nodes and seven edges. One of the nodes is a pure source (1), another one is a pure sink (5). No other nodes supply or demand any goods, they only serve as transportation junctions.

    >> V := [1,2,3,4,5]:
       Vw := [25,0,0,0,-25]:
       Ed := [[1,2], [1,3], [2,3], [2,4], [3,4], [3,5], [4,5]]:
       Ew := [7, 6, 5, 4, 2, 2, 1]:
       Ecap := [30, 20, 25, 10, 20, 25, 20]:
       N1 := Network(V,Ed,Eweight=Ew, Capacity=Ecap, Vweight=Vw):
       Network::minCost(N1)

                                table(
                                  [4, 5] = 5,   table(
                                  [3, 5] = 20,    5 = 2,
                                  [3, 4] = 0,     4 = 3,
                           220,   [2, 4] = 5, ,   3 = 4,
                                  [2, 3] = 0,     2 = 7,
                                  [1, 3] = 20,    1 = 14
                                  [1, 2] = 5    )
                                )

All 25 units could be transported from node 1 to node 5, for a total cost of 220.

#### Background

- The implemented algorithm is the relaxation algorithm due to Bertsekas (taken from Bertsekas, ``Linear Network Optimization'', MIT Press, Cambridge(Mass.)-London, 1991) which is known to be one of the fastest algorithms in practice.

#### Changes

- used to be called `Network::MinCost`

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000