[Help-glpk] [Fwd: mip behavior]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Veit Elser <address@hidden>
To: address@hidden <address@hidden>
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