Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code

[João Flávio de Freitas Almeida]

Hi all,

An interesting thing is that other solvers for large scale optimization also have problems implementing strategy for decomposition techiniques on problems. 

On a Benders Decomposition problem, when returning the dual value of constraing some solvers can use "InfeasibleOrUnbounded" instead of "Infeasible" or "Unbounded".

Here is a post of Robert Fourer (AMPL) about this issue, my post related to Benders Decomposition and Erling D. Andersen (Mosek) with some (math) explanation of the difficulties on implementing such feature.

http://bob4er.blogspot.com.br/2013/02/more-than-one-large-scale-solver-for.html

http://mosek.com/fileadmin/reports/tech/infeas.pdf.

On "Dantzig-Wolfe decomposition with GLPK" Joey Rios also present the algorithm limitations: "subproblems must be bounded. There may also be bugs."

http://en.wikibooks.org/wiki/GLPK/Add-Ons#Dantzig-Wolfe_decomposition

I also would like very much to see script .run file on Gmpl for Glpk.

Bests,

João Flávio F. Almeida

2012/11/8 Robbie Morrison <address@hidden>

Hello Steven

------------------------------------------------------------
To:           address@hidden
Subject:      [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code
Message-ID:  <address@hidden>
From:         Andrew Makhorin <address@hidden>
Date:         Thu, 08 Nov 2012 11:15:39 +0400
------------------------------------------------------------

You should register for the [Help-glpk] list.

> -------- Forwarded Message --------
> From: Steven G <address@hidden>
> To: address@hidden
> Subject: Converting AMPL Bender's Decomposition code to GLPK
> Date: Thu, 8 Nov 2012 00:45:51 -0500
>
> Hello,
>
> I am trying to convert the following .data .mod
> and .run files from APML to GLPK. The reason for
> this is that I have to solve a Bender's
> Decomposition in GLPK, and I have an AMPL
> example of a Bender's problem so I am trying to
> learn from that.
>
> I release that GLPK only allows to use the solve
> statement once; however, in Bender's
> decomposition you need to solve a Subproblem and
> a master problem simultaneously (as seen in the
> .run file), so I am very confused on how to do
> this with one solve statement.
>
> I know there isn't a run file in GLPK and I will
> need to combine the .mod and .run files for
> GLPK.
>
> If you could help me to convert this code into
> GLPK to look at or have a similar example or can
> give me any advice on the matter it will be
> greatly apprieciated.
>
> Thank you.

Here are two links to the GLPK wikibook.  The
first describes a Dantzig-Wolfe decomposition
project:

  http://en.wikibooks.org/wiki/GLPK/Add-Ons#Dantzig-Wolfe_decomposition

The second describes how to mix scripting and
MathProg:

  http://en.wikibooks.org/wiki/GLPK/Scripting_plus_MathProg

This 2003 thread might also be of interest:

  http://lists.gnu.org/archive/html/help-glpk/2003-12/msg00006.html

I don't have any direct knowledge of Benders
decomposition.  If you get something working, can
you post it back here and I will add it to the wikibook.

HTH, Robbie
---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]



_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk