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

Hi Robbie! Hi All,

A new MathProg feature based on AMPL would be great! AMPL is so popular because it enables almost every mathematical programming techniques in a fast and easy way, besides being very similar to mathematical programming models.

In my opinion, that's why GMPL (a subset of AMPL) became one of the most popular open source high level matematical programming language, and that's why it has so many users.

We have many open source solvers that aren't so easy to use as GLPK, and it is due to GMPL. If it is based on AMPL and If we can evolve and become even more popular, why not including high level scripting features, like AMPL?

I've seen that much of developents is on improving speed of algorithms or functions on IDE (which I agree), but we can't forget improvements on usability for non computer cientists (like me).

I know it would demand a lot of work, but a new MathProg feature based on AMPL would be a great evolution to GMPL! We haven't this feature on any open source solver! Even for those how want to implement models on low level (like c) scripting on GMPL would be important for prototyping (As it is on AMPL): We could get functionality and quality on results, then, improve speed on lower level functions.

A attach a benders decomposition problem I implemented on AMPL for prototyping. Once it was correct, it was implemented on lower level language for gaining performance.

I used AMPL with Cplex solver. For running the problem we need to type on shell:

"C:\address\...\ampl ptppbenders.run"

Bests,

João Flávio F. Almeida

2013/2/6 Robbie Morrison <address@hidden>

Hello João, all

------------------------------------------------------------
To: Robbie Morrison <address@hidden>
Subject: Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition
code
Message-ID:
<CABroSTaDT16u53Y9b=address@hidden>
From: =?ISO-8859-1?Q?Jo=E3o_Fl=E1vio_de_Freitas_Almeida?=
<address@hidden>
Date: Wed, 6 Feb 2013 15:18:04 -0200
------------------------------------------------------------

> 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

For example, a MIP object will report its status
(p76 of the API manual for version 4.48):

int glp_mip_status(glp_prob *mip)

GLP_UNDEF

MIP solution is undefined

GLP_OPT

MIP solution is integer optimal

GLP_FEAS

MIP solution is integer feasible, however,
its optimality (or non-optimality) has not
been proven, perhaps due to premature
termination of the search

GLP_NOFEAS

problem has no integer feasible solution
(proven by the solver)

Unboundedness is a property of the LP relaxation
(if I am not mistaken) so likewise:

int glp_get_status(glp_prob *lp)

GLP_OPT

LP solution is optimal

GLP_FEAS

LP solution is feasible

GLP_INFEAS

solution is infeasible

GLP_NOFEAS

problem has no feasible solution

GLP_UNBND

problem has unbounded solution

GLP_UNDEF

solution is undefined

Can you not get all the information your need?
And reprocess it as you wish:

int mystatus = -1;
mystatus = (glp_mip_status(mip) == GLP_NOFEAS
||
glp_get_status(mip) == GLP_UNBND);

Or would you like GLPK offer that functionality
directly? A new return code perhaps?

GLP_PROVEN_INFEASIBLE_XOR_UNBOUNDED

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

Are you asking for a new MathProg feature
based on AMPL?

(I do not use AMPL or MathProg so excuse me if my
question misses the point.)

cheers, Robbie

> 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]
---
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]

From:	João Flávio de Freitas Almeida
Subject:	Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code
Date:	Sun, 10 Feb 2013 13:01:12 -0300