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 -------- > From: Veit Elser <[email protected]> > To: [email protected] <[email protected]> > 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 > > > _______________________________________________ > Help-glpk mailing list > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk > _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
