Reformulating LP Problems Flashcards
(6 cards)
1
Q
How would you formulate Djikstra’s algorithm as an LP?
A
- Minimise Σ (weight x arc)
- Subject to:
arcs out from start node = 1
arcs into each node - arcs out of each node = 0
arcs into finish node = 1
Indicator variables
2
Q
How would you formulate finding the longest path as an LP?
A
- Maximise Σ (arc weights x arcs)
- Subject to:
- arcs out of start node = 1
- arcs into each node - arcs out of every node = 0
- arcs into finish node = 1
- evry arc ≤ 1
3
Q
How would you formulate maximising network flow as an LP?
A
- Maximise arcs out of source OR arcs into sink
- Subject to
- flow into each node - flow out of each node = 0
- each arc ≤ its capacity
4
Q
How would you formulate a matching problem as an LP?
A
- Maximise Σ arcs
- Arcs out of every node in set 1 ≤ 1
- Arcs into every node in set 2 ≤ 1
5
Q
How would you formulate an allocation problem as an LP?
The table one
A
- Minimise Σ ‘weight x arcs’ (aka each cell of table x the value in it)
- A1 + A2 + A3 +… = 1 (for every row)
- A1 + B1 + D1 +… = 1 (for every column)
6
Q
How would you formulate a transportation problem as an LP?
A
- Minimise Σ ‘weight x arcs’ (aka each cell of table x the value in it)
- A1 + A2 + A3 +… = row capacity/requirement (for every row)
- A1 + B1 + D1 +… = column capacity/requirement (for every column)
