Wednesday, May 22, 2013


I am teaching an Intro GAMS class at a government agency, and I was thinking about doing a shortest path model as LP. There are lots of interesting angles from a modeling perspective, at least I think so. I can talk easily for an hour or more just about that. But now I read this is all just fodder:

Given a directed graph (VA) with source node s, target node t, and cost wij for each arc (ij) in A, consider the program with variables xij
minimize \sum_{ij \in A} w_{ij} x_{ij} subject to x \ge 0 and for all i\sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1, &\text{if }i=s;\\ -1, &\text{if }i=t;\\ 0, &\text{ otherwise.}\end{cases}
This LP, which is common fodder for operations research courses, has the special property that it is integral

In my opinion there are quite a few things to say about modeling these things (even without discussing algorithms at all):

  1. Dense vs. sparse
  2. How to prevent inadmissible arcs to show up in the solution (high cost, fix to zero, don't generate those at all)
  3. One-directional, bi-directional arcs
  4. Large networks
  5. Data input
The appeal of this model is one does not have explain a lot about the problem itself.