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

[Joey Rios]

Thanks for the response Michael.

>
> > 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.
>
> What do you mean by "the correct form"?
> Given any set of complicationg constraints,
> one can readily derive the minimal block structure of the rest.
> To make the problem hard,
> one would need some criterion other than correctness.

Kind of a sidetrack, but an interesting one nonetheless.

Clearly, we could just partition the rows of the original LP constraint matrix into two parts and call one the connecting (complicating) constraints and the other the only subproblem, so you are correct that we need more criteria.

I haven't proven it, but I think the problem I'm trying to describe is reducable to graph partitioning.  The only algorithm I've come across to perform this specific task is from Weil and Kettler (1971):

http://www.paulcarlislekettler.net/docs/Weil_Kettler.pdf

They call it a 'maximal decomposition' or something.  In that article they'll have more precise definitions/criteria than I provide in this or my previous email.

An implementation of Weil and Kettler's algorithm would be handy and interesting to test on modern computers and LPs.

Joey