Re: [Help-glpk] Any users of dwsolver (Dantzig-Wolfe)?

[Joey Rios]

Hi Paul,

Sorry I didn't see your message sooner... haven't been keeping up with the mailing list very well.

> Hey Joey,
> I'm interested in using your software though Matlab for a power systems
> problem. I was wondering
> a) Is it straightforward to use your software with glpkmex

The current implementation of dwsolver is command line only.  There is no API to directly integrate with other tools.

> b) are you to define the partitions for a decentralised implementation
> easily.

If I understand your question, you do have to find the decomposition or your LP yourself.  It can be easy if you really understand the mathematical structure of you problem, or it can be very difficult if you are just looking at a huge constraint matrix with no obvious structure.  My suggestion is to start with the mathematical model of your problem to determine how it should be decomposed, then generate your master and subproblems accordingly.

> Well done for putting this together. I'm very surprised that there's no
> other open source implementations of it out there (although I'm discovering
> the hard way on Matlab at the moment that there's quite a few subtleties
> that a lot of the books don't tease out. Bazaraa I'm finding provides by far
> the clearest explanation on it by far of the different sources I've tried)

Bertsimas' LP book was the best one I found for actually implementing the algorithm.  You are right that there a lot of issues that most textbooks leave out when discussing implementation issues of DW.

Let me know if you have any other questions.  I'm happy to help knowing that dwsolver might be useful to you.

Joey

> Joey Rios wrote:
> >
> >
> > Hi all,
> > Just wondering if anyone on the list has used dwsolver. For reference,
> > dwsolver is an open source implementation of Dantzig-Wolfe decomposition
> > using glpk as the solver library:
> > http://sourceforge.net/projects/dwsolver/http://en.wikibooks.org/wiki/GLPK/Add-Ons#Dantzig-Wolfe_decomposition
> > I'm hoping to get some problem instances if anyone has any they've
> > developed. I have some of my own and I've generated some random problem
> > instances, but those are unsatisfying.
> > Oh, I'm the author of dwsolver. My interest is in doing some
> > computational tests on 'real' problems. Turns out it's hard (in the NP
> > sense, I think) to decompose a given LP instance into the correct form for
> > DW decomposition. It's much easier to generate the decomposition if you
> > know the model you are using.
> > If you have any instances you could share, please email me or the list.
> > Thanks,Joey
> > PS: dwsolver has had 400-ish downloads from around the world! Mostly
> > Spain for some unknown reason!