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

[Marcelo Pinto]

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 --------
> 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
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk
>