[Coin-standards] Re: Sparse matrix representation

[Gus Gassmann]

Leo Lopes wrote:
>
> On Mon, 15 Apr 2002, Gus Gassmann wrote:
> 
> > For continuous distributions you ought to store the distributions
> > themselves in some suitable format; I haven't come up with a good
> > format. 
> 
> I tend to think that distribution information doesn't belong here,
> unless it is in the nonlinear part. (Are we still talking of your SMPS
> extension, or are we being more general and talking about both
> projects?). 

I disagree. How can you model chance constraints if not by giving 
distribution information? So I don't think it matters whether we are 
talking about SMPS or the big picture. And with the sampling 
approaches of Infanger and Higle and Sen, the discretization is part 
of the algorithm, making the continuous distributions part of the 
instance. It would be a mistake to ignore those problems.

> There are two reasons: first, the interactions between
> different distributions seem too specialized (in the general case) to
> be dealt with directly by solvers anytime soon; second, the decisions
> about which distributions to choose, which parameters, sampling
> granularity, etc... seem to me like modeling issues and not instance
> issues. 

This is a matter of opinion. I suspect that there may very well be a 
layer between the general model, which flags some data items (or 
parameter classes) as random or uncertain, and the instance, 
which provides specific distributions to these data items. An 
intermediate step might include the class of distribution (normal, for 
instance, or uniform or whatever) that the data items are supposed 
to take, but exclude specific distribution parameters.

> I think that might be the reason so many smart people have
> looked at this and no one has come out with a real good solution...

It's a tough problem, no doubt about it. My current pet peeve is that 
the stochastic granularity is only understandable once the time 
structure is fixed, and we don't even know how to do that yet! 

> Actually, I think there might be a relatively elegant way of
> communicating chance constraints. In SNOML there are <rowset> tags
> with probability parameters, which default to 1.

That's a start, but I don't see (off-hand) how you can model multi-
dimensional chance-constraints in this fashion. 

> I guess I am thinking that no matter what we do, people are going to
> want to convert the data structures we give them to their own internal
> format. They will need to do inner products, but we won't. Do you
> think we might need to do inner products just as part of setting up
> the data structures?

This point I will concede. A reader with generic data structure can 
be one step removed from the solver's data structure. If the generic 
data structure is sufficiently well documented, then any solver 
implementer can shovel the data into whatever is suitable for the 
algorithm.

> > (Of course you are right: If you have a general purpose LP solver,
> > you will instead pull full columns out of the data structure for
> > further processing, so there will have to be a variety of support
> > procedures, too.)
> 
> Yes! This is an important point. The API/DOM *must* contain support
> procedures that allow the same file to be viewed different ways.

I am glad to see agreement on this point. Of course it means more 
work, but I think this level of support is essential.

-------------------------------------------------------

gus gassmann          (Horand.Gassmann at dal.ca)

School of Business Administration, Dalhousie University
Halifax, Nova Scotia, Canada , B3H 1Z5
ph. (902) 494-1844
fax (902) 494-1107

http://www.mgmt.dal.ca/sba/profs/hgassmann/