Scilab function

min_lcost_flow2 - minimum linear cost flow

Calling Sequence

[c,phi,flag] = min_lcost_flow2(g)

Parameters

Description

min_lcost_flow2 computes the minimum linear cost flow in the network g. It returns the total cost of the flows on the arcs c and the row vector of the flows on the arcs phi. If the problem is not feasible (impossible to find a compatible flow for instance), flag is equal to 0, otherwise it is equal to 1.

The bounds of the flow are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the minimum capacity must be equal to zero. The values of the maximum capacity must be non negative and must be integer numbers. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the element edge_cost of the graph list. The costs must be non negative and must be integer numbers. If the value of edge_cost is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The demand on the nodes are given by the element node_demand of the graph list. The demands must be integer numbers. Note that the sum of the demands must be equal to zero for the problem to be feasible. If the value of node_demand is not given (empty row vector []), it is assumed to be equal to 0 on each node.

This functions uses a relaxation algorithm due to D. Bertsekas.

Examples

See Also