Re: [Help-glpk] "The conflict graph is either empty or too big"

[Meketon, Marc]

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.