Network Problems as LPs

Question 1

Formulating shortest path

Answer 1

1. Define all variables forwards and backwards (total = 2* number of arcs)
2. Discard from these unneeded variables (variables that flow into source and out of sink)
3. With remaining variables write the objective function with the arc length the coefficient of the variables (minimise)
4. Write constraints (“subject to “).
   For source vertices all arcs leaving =0
   For sink all vertices all arcs entering = 0
   For all other vertices all arcs coming into point are positive. All arcs leaving point are negative. (Make sure not to include the unnecessary arcs). These are =0

Question 2

Formulating the longest path (direction given)

Answer 2

1. Define all variables forwards and backwards (total = number of arcs) - coz direction given
2. Discard from these unneeded variables (variables that flow into source and out of sink)- NONE in this case coz direction given
3. With remaining variables write the objective function with the arc length the coefficient of the variables (maximise)
4. Write constraints (“subject to “).
   For source vertices all arcs leaving =0
   For sink all vertices all arcs entering = 0
   For all other vertices all arcs coming into point are positive. All arcs leaving point are negative. (Make sure not to include the unnecessary arcs). These are =0
5. Because is a longest path question need to write contract of every variable being less than or equal to 1, otherwise the variables would be infinity

Question 3

Formulating maximum flow

Answer 3

1. Define variables - IN FLOW NO INDICATOR VARIABLES- variables hold value of arc weight
2. Remove unnecessary variables
3. Write expression for objective function (maximise) only the arcs leaving the source
4. Write down constraints for each vertex =0, will not be an equation for sink
5. Because is a maximum problem, each variables needs to be less than or equal to arc weight

Question 4

Formulating matching problems

Answer 4

Aim: to get each one from each set to match with another 1 from each set
1. All variables are indicator variables, each variable is just an arc presented
2. Objective function is maximise all variables
3. Place constraints on each vertices to be less than or equal to 1( cos could be zero in case that no one matches sadly) BOTH SETS INCLUDED

Question 5

Formulating allocation problems (minimise)

Answer 5

1. All variables are indicator variables, each variable is just an arc presented
2. Objective function is minimise all variables, with arc weight as coefficient
3. Place constraints on each vertices to be equal to 1- BOTH SETS INCLUDED

Question 6

Formulating transportation problems

Answer 6

1. Variables are indicator variables
2. Set up objective function with aim to minimise
3. Set up constraints with equal sign

Question 7

Shortest path summary

Answer 7

Question 8

Longest path summary

Answer 8

Question 9

Maximum flow summary

Answer 9

Question 10

Maximal matching

Answer 10

Question 11

Allocation problem minimum costs summary

Answer 11

Question 12

Transportation problem minimum cost

Answer 12

Question 13

Answer 13

Question 14

Answer 14

Question 15

Answer 15