[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] lpx_load_matrix

From: Jeff Abrahamson
Subject: Re: [Help-glpk] lpx_load_matrix
Date: Sat, 11 Sep 2004 20:59:27 -0400
User-agent: Mutt/1.5.6+20040722i

On Sat, Sep 11, 2004 at 01:40:27PM -0400, Jeff Abrahamson wrote:
>   [48 lines, 265 words, 1437 characters]  Top characters: ,1\naotrl
> I have an LP problem that looks like this:
>     S1 = F11 + F12 + F13 
>     S2 =                 + F21 + F22 + F23
>     D1 = F11             + F21           
>     D2 =       F12             + F22     
>     D3 =             F13             + F23
> (Aside: it's a graph theory statement about flow from vertices VS1 and
> VS2 and flow to VD1, VD2, and VD3.)
> But when loading the coefficient matrix I'm told that zero values
> aren't allowed.  Am I misunderstanding something?
> [snip]
> The error comes from glplpx1.c, line 26 ff:
>          if (ar[k] == 0.0)
>             fault("lpx_load_matrix: ar[%d] = 0; zero element not allowe"
>                "d", k);

I believe the answer to my question is the following: lpx_load_matrix
expects the arrays to be passed such that ar has no zero values.

I have attached a patch to fix this.  It simply ignores entries whose
ar value is 0.  At least in my case, it would have simplified my code
to have been able to pass a sparse matrix written out completely
rather than being obliged to compact it myself.  The patch is
compatible with existing client code except in the case that the
client depends on getting an error for a zero ar entry.

(Note that the patch is really just four lines: an if statement and
its closing brace as well as deleting the fault line.  But it changes
indentation, so it's longer.)

The routine has another problem that I have not fixed:

Presenting the values as three arrays, ia, ja, and ar, increases the
likelihood of cache misses over defining a structure

    struct coeff { int i; int j; double val; }

and passing an array of these structures.  (This can be significant at
the level of L1 or L2 cache, which are much smaller.  Normally VM
cache is too large to be affected.)


 Jeff Abrahamson  <>    +1 215/837-2287
 GPG fingerprint: 1A1A BA95 D082 A558 A276  63C6 16BF 8C4C 0D1D AE4B

 A cool book of games, highly worth checking out:

Attachment: glplpx1.patch
Description: Text document

Attachment: signature.asc
Description: Digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]