Monday, July 6, 2009

Dense Input Format: does not work for large problems

In yet another input format for LP’s is proposed. I don’t think this particular format will work in practice: it stores all elements, even the zero ones. Large LP’s have typically a large number of nonzero elements. Lets take the medium sized LP indus89 (m=2,726, n= 6,570) from the GAMS model library:

Representation Size (bytes)
GAMS: indus98.gms 262,612
MPS: fixed MPS generated by convert 1,634,841
proposed format (estim.) 143,359,504

For the large test model described in (m=1e6, n=1.2e6) we have:

Representation Size (MB)
MPS: fixed MPS generated by convert 180
proposed format (estim.) 9,155,308

Anything dense will never work for large models (“dense does not make sense”). I doubt this will become a standard format. Besides the inability to store large problems, it seems that ASCII formats are more popular, not in the least because they are platform independent and because you can actually look at the content.