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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
