[Help-glpk] General, parallel Dantzig-Wolfe implementation now available

[Joey Rios]

Hi all,

I had a private email exchange with Andrew a little over a year ago regarding a 
Dantzig-Wolfe implementation built upon GLPK.  Well, the legal department at 
work has finally allowed me to release it.  It can be found currently on 
SourceForge:

http://sourceforge.net/projects/dwsolver/

For those unfamiliar with Dantzig-Wolfe Decomposition, I'd recommend the 
wikipedia entry as a quick primer:

http://en.wikipedia.org/wiki/Dantzig%E2%80%93Wolfe_decomposition

This implementation solves in parallel using pthreads.  There were some small 
modifications needed for GLPK to run in parallel.  The easiest way to make this 
happen was to include all of the GLPK source with my Dantzig-Wolfe code.  
Therefore, the only library requirement (beyond the normal ones to build a c 
project) is pthreads.  I've successfully built it on Mac OS X 10.5 and 10.6, 
Red Hat Enterprise Linux, and Windows XP via cygwin.

Currently, the only input files accepted are LP format.  You must provide an 
LP-formatted file for the master and each of the subproblems.  After you have 
these files, you write a simple guide file that tells the command-line tool 
where everything is.

There are 6 examples taken from textbooks and websites that are included in the 
release and 1 toy example from my own research.

I'd be very excited to receive any feedback on the tool.  I don't know if it is 
more appropriate to do that here or on the sourceforge forums for the projects.

It is hoped that this tool can be a good starting point for folks wanting to do 
research using Dantzig-Wolfe decomposition.  While many papers in several 
domains have taken advantage of DW, there is no currently available software 
that I know of for the algorithm.  Everyone seems to implement it from scratch 
when they need it.  You can't even get this algorithm by dropping thousands on 
a CPLEX license.

Anyway, please have at it!  I'm sure there are many bugs and I know of many 
limitations with the current implementation (LP format only, bounded 
subproblems only, etc), so I'll be interested to hear what might be most 
valuable to improve upon first.

Sincerely,
Joey