Re: [Help-glpk] MIP stopping

[Klas Markström]

Hi Brady,
yes I am aware that it only applies under 
somewhat special circumstances. However when it 
applies it could make a big difference in running 
time and thus be worth quite a lot.
If one is doing integer programing and have an 
objective function with integer coefficients 
then this should be applicable. If one wants to 
generalise one could also do this when the 
variables are integers and the coefficients are 
rational, since one can then in principle just 
multiply the objective function with the largest 
denominator present.
However for large denominators this could lead to 
very large integers in the objective function.


/Klas

> Klas,
>
> I think it makes sense to add the feature you mention; I don't think
> GLPK has it already, but I haven't checked the code for it.
>
> Realize, however, that your situation is a special case in which all
> variables that appear in the objective are integer variables and all of
> their objective coefficients are integers as well.  The rule you
> describe does not apply for general integer programs (even pure integer
> programs).
>
> Brady
>
> Klas Markström wrote:
> >  Hi!
> >  I have been using glpsol to solve some
> >  minimisation integer programming problems. Right
> >  now the solver often finds the  optimal integer
> >  solution with value opt fairly fast and then uses
> >  a lot of time to improve the lower bound from opt
> >  -1 to opt. Since the solver "knows" that this is
> >  an integer programming problem it should be able
> >  to stop as soon as it has improved the lower
> >  bound to anything strictly above the current
> >  optimum minus one.
> >
> >  Is this going to be changed in some upcoming
> >  version of glpsol or is there some simple way to
> >  change the code so it will stop as soon as it
> >  knows that the current best is the optimum?
> >
> >  /Klas
> >
> >  --
> >
> >  ==========================================================================
> >
> >  Klas Markström                email: address@hidden
> >  Department of Mathematics        fax:   (+46)90 786 52 22
> >  Umeå University                         phone: (+46)90 786 97 21
> >  S-901 87 Umea, Sweden
> >
> >  URL: http://abel.math.umu.se/~klasm/
> >
> >  ==========================================================================
> --
> Brady Hunsaker
> Assistant Professor
> Industrial Engineering
> University of Pittsburgh
> http://www.engr.pitt.edu/hunsaker/


--

==========================================================================

Klas Markström                 email: address@hidden
Department of Mathematics        fax:   (+46)90 786 52 22
Umeå University                         phone: (+46)90 786 97 21
S-901 87 Umea, Sweden

URL: http://abel.math.umu.se/~klasm/

==========================================================================