Formulating a network problem as an LP problem

• For Djikstra's and CPA, arcs are either used or they're not
• An arc has a value 1 if it is used, and 0 if it is not - referred to as Indicator Variables
• Paths must be written both ways if they can go either direction
• LP Solver for the Shortest Path

  Minimise (arc weight x indicator)

  subject to

  (indicators from start vertex)=1

  (indicators to finish vertex)=1

  (indicators to vertex - indicators from vertex)=0
• For Longest Path, an inequality should be written for every path not part of the source or sink to stop them getting repeated
• LP Solver: Longest Path

  Maximise (arc weight x indicator)

  subject to

  (indicators from start vertex)=1

  (indicators to finish vertex)=1

  (indicators to vertex - indicators from vertex)=0

  (indicators to vertex)<=1
• We want to maximise the flow coming out of the source or going into the sink
• LP Solver: Network Flows

  Maximise (flows from source)

  subject to

  (flow to vertex - flow from vertex)=0

  flow <= capacity