Hello Marcelo, I guess Veit only described a special case of a problem in the branch and bound algorithm.
More generally speaking, a lower bound should always be raised to the next integer, if the objective function can only be integer. Best regards Xypron -------- Original-Nachricht -------- > Datum: Thu, 14 Apr 2011 17:30:12 -0300 > Betreff: Re: [Help-glpk] [Fwd: mip behavior] > Hi Veit, > > The first part of GLPK execution finds the LP solution (if exists). > The second part finds a MIP solution, that better approximates the LP > solution, and by default, stops when this difference <= 0.0% (10e-8). > > As you can imagine, can be very difficult (or impossible) satisfy this > stoppage criterion (that's why your optimization doesn't stop). > > To solve this problem, you can specify a MIPGAP, that makes the > optimizer stop and return the solution vector, when the MIP solution > is a percentage from the LP solution. > > Look for the --mipgap option at the manual. > > Best Regards, > Marcelo. > > > On Thu, Apr 14, 2011 at 3:28 PM, Andrew Makhorin <[email protected]> wrote: > > -------- Forwarded Message -------- > > Subject: mip behavior > > Date: Thu, 14 Apr 2011 13:20:58 -0400 > > > > I'm a bit puzzled about the behavior of glpk when solving pure integer > programs. All > > my variables are binary and all the non-zero constants are 1. I'm > running the stand-alone > > version and here is what I get in the late stage of the run: > > > > +3032261: mip = 6.000000000e+00 >= 5.644706378e+00 5.9% (39730; > 54174) > > +3037891: mip = 6.000000000e+00 >= 5.644706378e+00 5.9% (39645; > 54442) > > +3044704: mip = 6.000000000e+00 >= 5.644706378e+00 5.9% (39579; > 54703) > > > > My interpretation of this output (documentation?) is that glpk found an > integer solution > > with objective 6, and found a lower bound of 5.644... My question: why > does it keep > > going -- sometimes for a very long time? We know the objective is an > integer and greater > > than 5, and a solution with value 6 has already been found -- why > doesn't glpk terminate? > > > > Veit Elser > > -- NEU: FreePhone - kostenlos mobil telefonieren und surfen! Jetzt informieren: http://www.gmx.net/de/go/freephone _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
