- Many of my models are not pure networks (i.e. an LP with an embedded network or a network with side constraints - these are essentially the same, the difference is a matter of gradation),
- LP solvers are actually quite good in solving network models,
- Some models can be be converted to pure networks, but this can make the model less straightforward and more removed from the original problem
A complete GAMS model can look like:
|set i 'nodes' /n1*n5000/;|
* network topology (directed arcs)
* approx 5% density
set a(i,j) 'arcs i -> j';
a(i,j) = uniform(0,1)<0.05;
a(i,i) = no;
c(i,j) 'cost coefficients (over arcs)'
cap(i,j) 'arc capacities'
supply(i) 'exogenous inflow (sources)'
/ (n1,n2) 1 /
demand(i) 'exogenous outflow (sinks)'
/ (n3,n4) 1 /
c(a) = uniform(1,10);
cap(a) = uniform(0,0.5);
positive variable x(i,j) 'flow';
variable z 'objective variable';
* arc capacities
x.up(a) = cap(a);
flowbal 'inflow = outflow'
obj.. z =e= sum(a,c(a)*x(a));
sum(a(j,i),x(a)) + supply(i) =e=
sum(a(i,j),x(a)) + demand(i);
* reduce printing
model m /all/;
solve m minimizing z using lp;
We have \(n=5,000\) nodes. Arcs are modeled by a two-dimensional subset a(i,j). This set is sparse: only relatively few arcs exist. The step to generate approximately \(0.05 n^2\) takes a few seconds: we draw and compare \(n^2\) random numbers. We actually have 1,250,314 entries afterwards. This is indeed sparse:
|Partial view of two dimensional set a(i,j)|
We have two source nodes (\n1,n2\) and two sink nodes \(n3,n4\). The matrices cap and c and the vectors demand and supply are also sparse, The flow balance equation is heavily dependent on the sparse set a. Given a node \(i\) the first summation finds all incoming arcs, i.e. nodes \(j\) such that \(j \rightarrow i\) is an existing arc. The second summation finds all leaving arcs: nodes \(j\) such that \(i \rightarrow j\) is an existing arc. This equation is quite close to what we have in the mathematical model.
The model is not small. We have:
As the capacities are somewhat small, the solution is somewhat complex:
Some timings from my Windows laptop vs NEOS:
|GAMS Generation Time||26.406||12.816|
Somehow NEOS is relatively slow when solving. I think timing programs on NEOS is rather difficult with all that is happening on their machines.
It is noted that a pure network like this solves quickly. If I use COIN CBC instead of Cplex, we see excellent performance:
AMPL has two ways to express network models. The first is equation based and is basically the same as the GAMS model above.
The model looks quite nice,
I had some problems printing the results. In some cases funny results were printed with set elements I did not recognize.. A fragment is:
This is not normal output and looks like a bug when printing with options to suppress empty rows. In the end I worked around the problem and just printed the nonzero values using an expression.
AMPL also has special facilities to express networks. Let's see how that works with this example.
I actually prefer the equation based version: it conveys better what we are modeling. For more information about implementing network models in AMPL see .
GLPK is an open source LP/MIP solver which includes a modeling tool called MathProg based on a subset of AMPL. Mathprog is different enough from AMPL such that the AMPL model did not work out of the box. I applied some edits things to make things work again:
It is interesting to see how a free solver/modeling system would stack up against commercial ones. Unfortunately generating and solving this model took a very long time. Instead of less than a minute we deal with more than an hour:
The solver takes about 730 seconds, and the modeling tool needs the rest of the 4340 seconds (i.e. about an hour). I suspect running through the sparse two-dimensional set A in the flowbal equation is the killer.
- Chapter 15, Network Linear Programs, AMPL book, https://ampl.com/BOOK/CHAPTERS/18-network.pdf