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 (V, A) with source node s, target node t, and cost w_ij for each arc (i, j) in A, consider the program with variables x_ij

minimize  subject to  and for all i, 

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.