1

A little while ago I read a wiki about alternating between linear programming and shortest path problem (https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation). I'm just starting to learn linear optimization, and i can't seems to find a real example (implementable in real life) of a problem solvable with simplex method that can be solved (preferably faster) with shortest path algorithm. I have also heard about problems such as network optimization in linear programming but having difficulty to translate it into a form that can be solved by shortest path algorithm (such as dijkstra / A*)

So in short; can somebody points me an example of linear optimization problem that can be solved using shortest path algorithm?

Sorry if my question sounds vague or obvious, i'm a beginner in this topic.

SimpliCty
  • 11

1 Answers1

1

Specialized solvers are often but not always faster than general purpose solvers. I.e. a large shortest path problem can be solved faster using a shortest path algorithm than using an LP algorithm. However, state-of-the-art LP solvers are very, very fast. That means a simplistic specialized algorithm may actually lose to a good LP solver. Here are some examples using different algorithms for the assignment problem. You can do something similar: generate a large random sparse network, and see how different algorithms behave (including Dijkstra and Linear Programming).

Garam Lee
  • 15
Erwin Kalvelagen
  • 4,267