[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] finding integer solutions gives seemingly infinite loop
From: |
John Perry |
Subject: |
Re: [Help-glpk] finding integer solutions gives seemingly infinite loop |
Date: |
Wed, 4 Apr 2012 14:32:04 -0500 |
User-agent: |
KMail/1.13.5 (Linux/2.6.32-40-generic-pae; KDE/4.4.5; i686; ; ) |
Michael Hennebry wrote on Wednesday, April 04, 2012,
> On Tue, 3 Apr 2012, John Perry wrote:
> >> From a previous conversation, I understand that setting upper bounds for
> >> integer solutions helps the mip preprocessor find feasible solutions
> >> for minimization problems that have no maximum. I can make this work
> >> with the systems I'm solving right now, but I'm not sure how to set a
> >> good upper bound in general.
> >
> > Is there a good rule of thumb for this?
>
> Is the corresponding max problem really unbounded?
Now that you make me think of it, it's unbounded above only in theory; the
largest I could have is machine word size. (I don't mean GLPK; this has to do
with the result, which is then fed into a non-LP algorithm.)
I tried it just now, though, and that's also too large. If I set the maximum
at 1000, I get solutions; raising it to a mere 5000 slows it down
tremendously.
I could loop the upper bounds from, say, 1000, but this seems so... CLUMSY.
Since I'm adding constraints after having solved once already, I could also
use the results from the previous solution to guess an upper bound, then go up
from there when it fails. But that also seems clumsy.
I guess I was hoping there might be a way of making an educated guess of the
upper bounds on the variables from solutions obtained by the simplex
algorithm.
regards
john perry
--
John Perry
Associate Professor
Department of Mathematics, Box 5045
University of Southern Mississippi
Hattiesburg MS 39406
address@hidden
Let me seek you in desiring you, let me desire you in seeking you, let me find
you in loving you, let me love you in finding you. - Anselm