Re: [Help-glpk] [Fwd: mip behavior]

[glpk xypron]

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 <address@hidden> 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