Chapter 10 - Network

Question 1

What is a directed network?

Answer 1

A network with only directed edges/arcs

Question 2

Define a path between two nodes

Answer 2

A path is a sequence of distinct arcs connecting the two nodes.

Question 3

What types of “paths” do we have?

Answer 3

Directed, undirected. If we have directed path, then we can only move in one direction. If undirected, the path works as a channel in both ways.

Question 4

What is a cycle in networks?

Answer 4

A path that begins and ends in the same point/node

Question 5

What is the requirement for two nodes to be connected?

Answer 5

There must exist at least one undirectional edge between them.

There is no requirement on direction, and there can be different edges (directed and undirected).

Question 6

What is a connected network?

Answer 6

A connected network is one where all nodes are connected to each other.

Question 7

What is a spanning tree?

Answer 7

A spanning tree is a connected network that contains no undirected cycles.

Question 8

How many arcs will a minimum spanning tree?

Answer 8

Exactly n-1 arcs.

Question 9

What is “arc capacity”?

Answer 9

The maximum amount of flow that a specific arc can hold

Question 10

What is a supply node?

Answer 10

A supply node is a node where the flow out of the node exceeds the flow in to the node. It is also called source node.

Question 11

What is a demand node?

Answer 11

A demand node is a node that have more flow in than out. Also called a sink.

Question 12

What is a transshipment node?

Answer 12

A transshipment node is a node that satisfies the conservation of flow, meaning that flow in equals flow out.

Question 13

Formuler korteste vei problemet matematisk

Answer 13

Vi bruker indekser i og j.

Xij = binær beslutningsvariabel som er 1 dersom path i-j er med i den optimale (korteste) løsningen.

cij = Kantvekt som representerer en form for kostnad.

N er mengden av alle noder.
B er mengden av alle kanter/buer.

Problemet kan da defineres slik:

min Z = ∑cijxij [(i,j) in B]

s.t.

∑xsj [j in N] = 1

∑xin [i in N] = 1

∑xij [i in N] - ∑xji [i in N]= 0 , for all J in N.

and

xij = {0,1} for all i and j.

Question 14

Forklar stegene i PRIM

Answer 14

Trinn 0:
Start fra en vilkårlig node i grafen. Valget har ingenting å si, alle noder skal med i MST uansett.
LA denne noden definere mengden S.
La resterende noder definere mengden S’.
La også T = Ø være mengden med kanter i vårt foreløpige MST.

Trinn 1:
Finn den buen (j,k) i nettverket med LAVEST KOSTNAD der j er i mengden S og k er i mengden S’.
Vi bruker altså mengden S som angrepspunkt hver iterasjon. Husk kruskal, som ikke gjør dette.

Trinn 2:
Oppdater mengden T til å være T union (j,k).
Oppdater S = S union k.
T er mengden med kanter i MST.
S er arbeidsmengden vår.

Trinn 3:
Stopp hvis |T| = n-1. Ellers gå til trinn 1.

KOMMENTARER:

Legg merke til hvordan T, ved hver iterasjon, holder et MST som er en delmengde av MST vi ønsker å finne.

Vi vet at den endelige mengden med kanter skal være lik n-1. Dette kommer også frem fra trinn 3.

Question 15

Describe the maximum flow problem

Answer 15

1) All flow through a directed and connected network originates at ONE node, called the source, and terminates at ONE node, called the sink.

2) All remaining nodes are called TRANSSHIPMENT nodes.

3) Flow through an arc is allowed only in the direction of the arrowhead, where the maximum allowed flow through that arc is given by its capacity. At the source, all flow goes out from the node, while at the sink, all flow goes in to the node.

4) THe objective is to maximize the total amount of flow from SOURCE to DESTINATION/SINK.
We can measure this max flow in two ways: Either as the flow leaving the source, or the flow entering the sink.

Question 16

What do we do if our network have multiple sources, and or multiple sinks, and we want to find max flow?

Answer 16

Max flow algorithm doesnt allow this, so we have to adjust the network.

We add a dummy source and possibly a dummy sink.
The important thing is that the edge going from dummy source to each of the original sources MUST have the same capacity as the original source support out from them. So, if source 1 sends out flow to 3 nodes, each along arcs of capacity 10, the capacity on the new arc between the new dummy source and original source #1 must be equal to 3 times 10 = 30.
The same principle applies for dummy sink.

Remember, we can do this because the source is not “generating” any flow. In a max flow problem, we dont look at what the node is generating. We are ponly looking at how much potential flow this network can carry.

Question 17

What do we call the algorithm we use for maximum flow?

Answer 17

Augmenting path algorithm.

This algorithm is built on concepts:
1) Residual network
2) Residual capacities

Question 18

What does the residual network show?

Answer 18

The residual network shows the remaining available capacities.

The original/actual network contains only directed arcs. However, the residual network consists of undirected edges.

Question 19

How do we illustrate residual capacity?

Answer 19

like the image.
The number on the side indicate the remaining available capacity from its node, to the other node.

Recall that we can also cancel flows.

Question 20

What is the relationship between assigning a flow, and the residual network?

Answer 20

When we assign a flow to an arc, that flow-amount is subtracted from the residual capacity in the same direction, AND ADDED to the residual capacity in the opposite direction.

So, when we assign a flow, we remove this from the residual capacity, indicating less availability. At the same time, we offer the possibility of cancelling this amount of flow.

Question 21

What is an augmenting path?

Answer 21

An augmenting path is a directed path from source to sink in the RESIDUAL NETWORK such that every arc on this path has STRICTLY POSITIVE residual capacity.

The minimum of these residual capacities (along the path) is called the “residual capacity of the augmenting path” because it represent the flow that can feasibly be added to the entire path. Therefore, each augmenting path provides an opportunity to further augment the flow through the original network.

Question 22

briefly, what does the augmenting path algorithm do?

Answer 22

It repeadetly selects some augmenting path and adds a flow equal to its residual capacity to that path in the original network. This process continue untl there are no more augmenting paths in the residual network, indicating that the flow cannot be further augmented.

Question 23

Iterate through the steps of the Augmenting path algorithm

Answer 23

1) Identify an augmenting path by finding some directed path from the source to the sink in the residual network such that every arc on this path has strictly positive residual capacity.

2) Identify the residual capacity c-star of this augmenting path by finding the minimum of the residual capacities of the arcs on this path. Increase the flow in this path by c-star.

3) Decrease by c-star the residual capacity of each arc on this augmenting path. Increase by c-star the residual capacity of each arc in the opposite direction on this augmenting path.
Return to step 1.

Just note that the choice of selecting augmenting paths have great impact on efficiency, but we dont care here. For our sake now, we can pick arbitrarily.

Question 24

Why is the residual network a UNDIRECTED network?

Answer 24

Because this allows us to “cancel” flows. Cancelling flows basically just means “oh nevermind, this other path is better. Let us re-assign some of this flow”.

Question 25

What is the most difficult task of the Ford-Fulkerson/augmenting path algorithm?

Answer 25

Finding augmenting path.

We use breadth-first to systematically search for augmenting paths. Note that this is called Edmonds-Karp.

Question 26

How can we quickly check whether we have the optimal max flow or not?

Answer 26

If the current flow is equal to some cut, we have the optimal flow.

Question 27

What is the minimum cost flow problem?

Answer 27

THe minimum cost flow problem concerns itself by finding the minimized total cost of sending a certain amount of supply through the network to satisfy the given demand.

It is formally described as follows:
1) The network is a directed and connected network
2) At least one supply nodes
3) At least on demand node (cannot be the supply node)

4) All remaining nodes are called TRANSSHIPMENT nodes.

5) Flow is generally only accepted in one direction (arrowhead). Max flow is given by the capacity of arcs.

6) The network has enough arcs with sufficient capacity to enable all the flow generated at the supply node to reach all the demand nodes.

7) The cost of the flow through each arc is proportional to the amount of that flow, where the cost per unit flow is known.

8) The objective is to send the demand/supply at the minimized cost.

Question 28

What do we typically use a minimum cost flow problem for?

Answer 28

Supply chain shite.

Ordering inputs, shipping them to factory, sending them to customers.

It is especially needed for intermediate storage facilities.

Question 29

Formulate the mathematical model of the minimum cost flow problem

Answer 29

We need decision variables that indicate the amount of flow through each arc:
Xij : the flow through arc (i,j).

We need some parameters:

Cij: cost per unit through arc (i,j).

Uij : arc capacity for arc (i,j).

bi : net flow generated at node i.

The value for bi depends on the nature of the node. If it is a supply node, it will be positive, strictly positive.
If the node is demand node, it will be strictly negative.
bi will be zero, 0, if the node is a transshipment node.

The image shows the mathematical model.

The model is surprisingly simple. It only includes the fact that flow OUT must equal flow IN for all nodes, except the source and sink. We make a constraint for this nicely by using bi values. The fact that bi is zero whenever the node in question is a transshipment node is ideal for us.

Question 30

What is the “feasible solutions property” of minimum cost flow problems?

Answer 30

The sum of bi for all i must be equal to 0.

This means: the total flow generated at the supply node equals the flow accepted at the demand node.

If this is not satisfied, we cannot have a feasible solution.

If we happen to have a network that violates this property, we need to either add a dummy supply node or a dummy demand node. These dummy nodes will accept/handle the excess supply/demand.

Dummy nodes have arcs with cost 0 and capacity high enough to handle the excess.

If we have excess supply, we add a dummy demand node that we connect directly to all source nodes so that they can directly map the excess there. 0 cost, lots of capacity.

Question 31

What is the “integer solutions property”?

Answer 31

The integer solutions property is that for a minimum cost problem where every bi and Uij have integer values, all the basic variables in every basic feasible solution also have integer values.

Question 32

What is interesting about network optimization problems?

Answer 32

many are actually all part of LP problems.

This means that we can use simplex on them. There is also the network-suímplex.

However, the specific problems also have tailored algos that work better than simplex.

Question 33

Formulate the mathematical model of the shortest path problem.

Answer 33

min Z = ∑∑Cij Xij

s.t.

∑Xjn = 1

∑Xsi = 1

∑Xij - ∑Xji = 0, for all j

Xij binary

Question 34

When we use Dijkstra, what is the assumptions?

Answer 34

No negative edges.

Question 35

Explain the steps in Dijkstra

Answer 35

Step 0: Divide the set of nodes into A={colored} and D={not colored}.

Initially, A is empty, and D contains all nodes.

Then we assign a label to every node ( - , infinity), but the source gets label ( - , 0).

Step 1:
We extract the node from D that have the minimum cost in its label. We call this node “i”.

Step 2:
Consider every arc (i, j) in B (the set of arcs) that starts from node i. If yi + Cij < yj, we have found a shorter path from source to node “j”, and we update the label of “j”.

Step 3:
We place node “i” into the set A.

Step 4:
If all nodes are in A, meaning that D is empty, we are finished. If not, return to step 1.

Question 36

What is a project network?

Answer 36

A project network is a network structure that display the different activities that are to be performed in the project, their time duration and their precedence relationships.

The point in using project networks is to highlight activities that must be done sequentially, so that the remaining ones can be run in parallell.

There are two ways to represent a project as a network:
1) Activities on Arcs (AOA)
2) Activities on Nodes (AON)

Activities on nodes is the most common approach.

Question 37

What are immediate predecessors?

Answer 37

In the context of project networks, immediate predecessors are activities that MUST be performed no later than the starting time of the specific current activity.
NOTE: We only consider “immediate” activities. If A must be done before B, and B before C, and C before D, then we if we look at D, only C is the immediate predecessor. If we look at C, only B is the immediate predecessor.

Also, note that there are shite called “immediate successors” as well, which is the exact same but opposite.

Question 38

What does a project network show?

Answer 38

It shows the paths that must be taken in a project. We can perform them sequentially, OR we can follow the project network structure and make use of parallel paths, saving important time.

The project network also show the longest path. The longest path is important to us, because it tells us where our project bottleneck is, in regards to time. If we want to improve time, we need to attack the longest path.

The longest path is also called “critical path”.

Question 39

What information is needed for a project network?

Answer 39

We need all activities.

We need all precedence relationships between all activities.

We need time duration estimates of the activities.

These 3 parts will give us a project network structure.

Question 40

What are the advantages of AON?

Answer 40

1) Easier to construct
2) Easier to understand
3) Easier to revise, given some changes.

Question 41

What is important to remember when constructing a project network?

Answer 41

The start node, and the finish node, which are not considered activities. These nodes are labeled “START” and “FINISH”, and have duration of 0 each.

Question 42

What is a “path” in a project network?

Answer 42

A path in the context of project networks is a path going from START to FINISH, containing no cycles.

A project of some size will typically have many different paths.

The longest path is the most interesting one, and is called the CRITICAL PATH.

Question 43

Reducing the duration of an activity is called …?

Answer 43

Crashing.

We say that we crash an activity if we apply measures that reduce its time duration.

We say that we crash the project if we do it to multiple activities.

Question 44

What is “normal point”?

Answer 44

Normal point refers to the original time duration estimate (and cost) of an activity.

The normal point stands contrast to the crashing point, which represent the duration and cost of crashing an activity FULLY.

Question 45

What is “crashing point”?

Answer 45

Crashing point is the duration and cost of crashing the activity FULLY.

Question 46

How do we use crashing point and normal point?

Answer 46

We plot both points, and draw a line between them.

This allows us to assume partial crashing.

Question 47

When using CPM, what do we look for?

Answer 47

Crashing cost per week saved.

Question 48

What is our actual problem?

Answer 48

Given a project, and a goal-duration, what is the minimized cost for reaching the duration goal?

In other words, how can we crash the project in a way that lets us reach our time goal, but at the least expense.

Question 49

What is marginal cost analysis?

Answer 49

In this context, MCA is a method following:

We solve the actual problem by always looking at the marginal cost of reducing the project by one week (or one time unit). We only look at the critical path. Note that this path can change during the process.
We reduce the activity in the critical path that have the lowest “crashing cost per week saved”. Then we update the table or whatever. Then we do it again.
We repeat until we have reached the time goal.

Question 50

Is MCA used widely?

Answer 50

No, it is not that useful for larger projects. Whether this is due to simplex being better or MCA being bad, idk.

Question 51

Formulate the project network problem mathematically

Answer 51

cj is the cost of crashing activity j by one week.

xj is the amount of weeks crashed of activity j.

yfinish is the total time duration of the project.

t is the duration requirement.

yi is the starting time for activity i.

yj is the starting time for activity j.

dj is the duration for activity j.

xj is the weeks crashed of activity j.

THE MOST IMPORTANT constraint is the one with the starting times. These drives the model.
It basically say “If activity i must happen after j, then its starting point must be equal to, or after, the starting point of j plus the time it takes for j to finish, less the crashed amount”.

Question 52

Consider a cut. What is a cut value exactly?

Answer 52

We consider the capacity going from the source side to the sink side. We dont consider “negative capacity”. We only give a fuck about how much one can send from the source side, to the sink side.

In this course, we use “cut” very badly. A cut is actually just the partition of nodes where source is in one side, and sink is in the other.
We should use the term capacity of a partition to talk about “cut value”. c(S, T).

The key is to understand that the capacity of the cut represent how much we can possibly send from the source side to the sink side across this specific ‘line’.

Question 53

Give the mathematical formulation of the maximum flow problem

Answer 53

When we use the max flow problem in this context, we typically want to maximize some final output. We are looking at what our network can handle.

Xij : Flow on arc (i, j)

Uij : Capacity of arc (i, j)

Important to understand that the constraint excludes nodes Source and Sink, as they either generate flow, or accept flow.