Re: [Help-glpk] FW: FW: Leap/OSeMOSYS

[Joey Rios]

 

> Fortunately, the techniques of decomposition, Dantzig-Wolfe and Benders'
> Decomposition, work very well for this type of problem. There are other
> idiosyncratic tricks and techniques that can be applied if the structure
> of the problem can be further limited. Note that decomposition is not
> an alternative to a simplex solver but rather capitalizes on the
> structure of the problem to use the solver more effectively.
>

Might I suggest trying dwsolver?  It implements Dantzig-Wolfe decomposition using glpk as the solving engine:

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

> Evidently the Plexos application implements some of these techniques
> because Plexos requires the user to supply a simplex solver. The
> techniques used by commercial vendors of power system analysis
> applications are of course not well documented.

Just an additional plug for dwsolver: it is open source and there are a few examples.  I'm not guaranteeing that it will work out-of-the-box for every problem, but it might provide some good computational gains for the right problems.  For an example of that code in use on a real problem (air traffic scheduling) check out this paper:

Rios, J and Ross, K.  "Massively Parallel Dantzig-Wolfe Decomposition Applied to Traffic Flow Scheduling."  Journal of Aerospace Computing, Information, and Communication. Vol 7, Jan 2010.  http://users.soe.ucsc.edu/~kross/Publications/JACIC2010.pdf

I'd love to see it formally applied to another problem.

> >> Also, in case there is a generic option to make glpk solve this
> >> problem, apart from heavily adjusting the OSeMOSYS code, e.g., by
> >> splitting up the problem somehow, please do let us know.

dwsolver won't split the problem up for you automatically, so you'll have to examine your constraints and see if it has the correct form and then generate the necessary subproblems (as described in the dwsolver documentation).

I typed "dantzig-wolfe power" into Google Scholar and received several promising hits that might help you decide if DW is appropriate for you.

OK, I'm done with the shameless plugging of dwsolver, but I'm happy to talk about it further if anyone is interested.

Joey