help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Robbie Morrison
Subject: Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code
Date: Thu, 7 Feb 2013 07:01:05 +1300
User-agent: SquirrelMail/1.4.22

Hello João, all

------------------------------------------------------------
To:           Robbie Morrison <address@hidden>
Subject:      Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition
code
Message-ID: 
<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]





reply via email to

[Prev in Thread] Current Thread [Next in Thread]