Re: [Help-glpk] lpx_load_matrix

[Jeff Abrahamson]

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

 Jeff Abrahamson  <http://www.purple.com/jeff/>    +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:
 http://www.amazon.com/exec/obidos/ASIN/1931686963/purple-20

glplpx1.patch
Description: Text document

signature.asc
Description: Digital signature