[Coin-standards] SP Interface -- two levels?

[Alan King]

At the SMPS level, one may describe a continuous distribution whose value
is revealed in a deterministic time interval.  We haven't worked out a
general way of representing stopping times (ie stochastic time intervals).
Let us call the first type a stochastic program with deterministic time
increments (SPDT) and the second a stochastic program with stochastic time
increments (SPST) --- whatever that is.

At the solver level, one may solve stochastic programs using several types
of programming methods.  The ones that seem to be currently most useful are
the L-shaped method (regularized and non-), Progressive Hedging, and
non-linear treatments of chance constraints. There are others:
Frauendorfer, Dantzig-Infanger, Higle-Sen.

It seems that this state of affairs may require two levels of intermediate
architecture.  Level SPI1 that supplies methods to communicate efficiently
with solvers, and level SPI2 that supplies methods to communicate
efficiently with SMPS and/or modeling environments.

This may be needed even in the simplest case of solving SPDT with L-shaped
method.  For example, the L-shaped method in OSLSE doesn't much care what
the distribution is so long as it looks like a scenario tree.  Managing the
scenario tree data structure is quite a big job that could be done by SPI1.
On the other hand, deciding how to generate the scenario tree might be
something best undertaken by SPI2 --- presumably SPI2 might be instructed
to solve multiple versions of the problem (ie multiple calls to SPI1) with
different approximations of SPDT.

One might take the view that SPI1 + "L-shaped method" is in fact an SPDT
"solver" class, but I would argue that there is still so much work to be
done in this space that it may be better to keep them separate at least
until the community converges on the short list of the most useful methods.

Also, it is probably the case that one might choose different computer
languages to code SPI1 and SPI2.  For example, I would prefer to code SPI1
in C/C++, but I would probably want to code SPI2 in Java/XML.

Alan


On Wed, 17 Apr 2002, Gus Gassman wrote:

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.