Networks

Question 1

arcs

Answer 1

edges, links,branches
in the course:
arcs are directed
links are undirected

arc can have a capacity : max of flow that can pass through them

Question 2

net flow

Answer 2

the difference in flow of both direction

it is possible to add a fictional flow in the opposite direction to reduce the net flow

Question 3

spanning tree

Answer 3

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.
spanning trees represent the BFS of the network simplex. any set of n-1 arc of a minimum cost problem is a spanning tree as there cant be any undirected cycles (otherwise this leads to averages of other BFS)

Question 4

types of node

Answer 4

supply/source: flow out of node (will have a + flow)
demand/sink: flow into node (will have a - flow)
transshipment node: no net flow, as much in then out (will have a 0 flow)

Question 5

minimum cost flow problem

Answer 5

all the flow from the supply nodes need to reach the demand nodes with minimum costs (if there would be mismatch: add dummy supply or dummy demand).
Arcs have capacities that can limit some paths.
directed network

xij flow from i to j 
cij cost from i to j 
uij capacity from i to j
bi net flow at i
objective minimizing total cost
sum i sum j cij xij
subject to 
sum j xij - sum j xji = bi for each i ( flow difference = net flow) 

if there is a lower bound : xij’ = xij - Lij -> xij = xij’ + Lij. replace everywhere xij with this

Integral Property: if all numbers are integral our solution will also be integral

Question 6

shortest path problem

Answer 6

finding edges from point to point b with smallest associated cost

Question 7

maximum flow problem

Answer 7

need to bring as much flow from the supply node to the demand node but arcs have capacities that limit it.

min cut max flow theorem: the size of the max flow is equal to the minimum total capacity of any set of arcs whose removal destroys all directed path from source to sink

Question 8

transportation to minimum cost

Answer 8

supply node for each source. demand node for each destination. no arc capacity. cost remains the same per unit of flow. arcs between each source and destination.
supply + demain -

There are no transhipment nodes (nodes that don’t supply or demand), the supply and demand are directly connected

Question 9

assignment to minimum cost

Answer 9

same as transportation:
supply node for each source. demand node for each destination. no arc capacity. cost remains the same per unit of flow. arcs between each source and destination.

BUT number of supply nodes = number of demand nodes AND supply, demands are 1

Question 10

shortest path to minimum cost

Answer 10

have arcs going in both direction. have supply and demand of 1

Integrality property will ensure this is a path.

Question 11

max flow to minimum cost

Answer 11

have all cost=0 as no cost is associated with max flow problem. 1 supply , 1 demand node. Choose an upper bound flow to add to supply and demand node. Add arc (dummy edge) from supply to demand node with unlimited capacity and a cost of M

Question 12

number of basic variables

Answer 12

if there are n nodes then there are n-1 basic variables and these form a spanning tree.