[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] "The conflict graph is either empty or too big"
From: |
Meketon, Marc |
Subject: |
Re: [Help-glpk] "The conflict graph is either empty or too big" |
Date: |
Tue, 22 May 2012 18:32:35 -0500 |
A long time ago I built linear programming solvers. One of the lessons was
that double precision helps in getting solutions faster - using single
precision runs into too many numerical problems (say, too many times when the
inverse of the basis needs to be rebuilt).
Michael's comment is interesting. Intel architecture does all of its
arithmetic in 10-byte precision. Unless you natively use "long double"
everywhere, there is always the conversion of the number to a 10-byte real
number before a computation is made. The only "win" in a performance viewpoint
from using single precision over double precision is the time it takes to fetch
4 bytes versus 8 bytes. And that "win" disappears with 64-bit architecture.
-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Michael Hennebry
Sent: Tuesday, May 22, 2012 12:34 PM
To: spiritfire
Cc: address@hidden
Subject: Re: [Help-glpk] "The conflict graph is either empty or too big"
On Tue, 22 May 2012, spiritfire wrote:
> By doing some researches I found out that my code is doing fine but
> the problem is hard to solve.
>
> I would like to fasten the solver by reducing the precision from 9 to
> 7 digits. Is it possible ? Or by reducing the number of iterations but
> I do not know how to do either one of these.
Reducing iterations will certainly not work:
You have yet to get a solution with the iterations you have.
Going from double to single precsion would not be helpful on any Intel or AMD
device.
All floating point arithmetic is done in at least double precision.
I'm not sure there are any devices on which you would get a speed up.
At better tactic might be to use problem-specific information to generate
either constraints or solutions.
Also, suppose one has a zero-one problem and for the current "solution" x:
0<=x<=1
SUM x[j] + SUM (1-x[j]) < 1
j in S j in T
and there is no feasible solution with
x[j]=0 for j in S and x[j]=1 for j in T.
In that case SUM x[j] + SUM (1-x[j]) >= 1 is a valid cut
j in S j in T
--
Michael address@hidden
"On Monday, I'm gonna have to tell my kindergarten class, whom I teach not to
run with scissors, that my fiance ran me through with a broadsword." -- Lily
_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk
This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
- [Help-glpk] "The conflict graph is either empty or too big", spiritfire, 2012/05/14
- Re: [Help-glpk] "The conflict graph is either empty or too big", Haroldo Santos, 2012/05/14
- Re: [Help-glpk] "The conflict graph is either empty or too big", spiritfire, 2012/05/14
- Re: [Help-glpk] "The conflict graph is either empty or too big", glpk xypron, 2012/05/14
- Re: [Help-glpk] "The conflict graph is either empty or too big", spiritfire, 2012/05/22
- Re: [Help-glpk] "The conflict graph is either empty or too big", spiritfire, 2012/05/22
- Re: [Help-glpk] "The conflict graph is either empty or too big", spiritfire, 2012/05/22