2) longest Path Problem (not Flow = PATH ) = CPA

Question 1

First thing is critical path analysis =longest path?

Answer 1

Yes you can solve both by using longest path because cos requires each thing to be fine similar to longest path

Also note this isn’t MAXIMUM FLOW

Question 2

How to do longest path compared to shortest path

Answer 2

Again as paths , we can use indicator variables !

1) MAXIMISE , and the same way for shortest path (total length of circuit except for going into start and away from end)
2) constraints again like shortest (start and end going in out = 1, in between going in - going out =0)

3) EXTRA CONSTRAINT

Question 3

Why do we need an extra constraint for longest path ? What’s changed?

Answer 3

-Now where there is a path in middle, surely you can just spam up down forever .
- + this time you can’t assume they hold a value of 1, could be 10, thus longest path could be whatever it’s not defined

Question 4

How to put in extra constraint

Answer 4

For any case

In the middle paths WHERE YOU CAN TRAVEL IN TEO DIRECTIONS WHATEVER
- going one way + going other way is LESS THAN = TO ONE

This ensures either non is picked or only one is picked!

Question 5

Ben if they only have one direction why mus still do?

Answer 5

Must still do going out direction <=1

Otherwise unbounded variable could take 100

Question 6

What about starting and end points? Do we still need extra constraints to make sure only used once / variables are bounded? Even tho already defined

Answer 6

I wouldn’t think so but integral said YES!

Question 7

Summary

Answer 7

Maximise = lentgh of total possoble paths (INDICATOR MULTIPLEID BY WEIGHT)
Subject to
Constraint from esch corners, start and end add to 1, in between in - out = 0
EXTRA = if multiple ways, must define each way add to be less than equal to 1 (either one is picked or none)

If still one directional, must define as less than equal to one, to ensure values bounded

Question 8

AGAIN FOR ONE WAY HOW TO DO

Answer 8

If everything is one way, maxi is as normal but remove all the coming backs

Constrains as normal but no coming backs

FOR THE EXTRA CONSTRAINTS, define EACH path is less than equal to one, even tho I think only have to do for undefined ones, do for ALL, so that variables aren’t UNBOUNDED