Wednesday, May 22, 2013

Fodder

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
http://en.wikipedia.org/wiki/Shortest_path_problem

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.