Hello João, all ------------------------------------------------------------ To: Robbie Morrison <[email protected]> Subject: Re: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code Message-ID: <CABroSTaDT16u53Y9b=l3lqfuwyrj1qd3ivog3w+8pwuuwfb...@mail.gmail.com> From: =?ISO-8859-1?Q?Jo=E3o_Fl=E1vio_de_Freitas_Almeida?= <[email protected]> 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 <[email protected]> > >> >> Hello Steven >> >> ------------------------------------------------------------ >> To: [email protected] >> Subject: [Help-glpk] [Fwd: Converting AMPL Bender's Decomposition code >> Message-ID: <1352358939.2022.0.camel@corvax> >> From: Andrew Makhorin <[email protected]> >> Date: Thu, 08 Nov 2012 11:15:39 +0400 >> ------------------------------------------------------------ >> >> You should register for the [Help-glpk] list. >> >> > -------- Forwarded Message -------- >> > From: Steven G <[email protected]> >> > To: [email protected] >> > 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) : [email protected] >> Webmail (preferred) : [email protected] >> [from Webmail client] --- Robbie Morrison PhD student -- policy-oriented energy system simulation Technical University of Berlin (TU-Berlin), Germany University email (redirected) : [email protected] Webmail (preferred) : [email protected] [from Webmail client] _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
