[Coin-standards] minutes / strategy

[Leonardo B. Lopes]

This is an interesting statement. Let's look at it carefully.

On Mon, 8 Apr 2002, Irv Lustig wrote:

> At 02:56 PM 4/8/02 -0500, Leonardo B. Lopes wrote:
> >How would you do business differently if we suddenly had a solution to
> >this standards problem?
> 
> This statement assumes there is a "standards problem".

I value your opinion and experience tremendously, but it is obvious that I
disagree with you here. More importantly, a lot of other people also do,
both in research and in business. There really is a standards problem, and
there are two sanity checks to show that: The attendance and discussion
level at the different talks on the subject; and the methods through which
optimization software currently communicates (including ILOG software).

> 
> Today, we have an agreed upon standard, called MPS format.  The various 
> vendors have some minor differences in how this standard is interpreted in 
> some very detailed points, but for 99.90f problems that we each see, the 
> interpretation of MPS files is the same.
> 

This may be true. I think a lot of people disagree with this statement,
but I won't get into that. I personally agree with it for the most
part. So let's assume it is completely true. What are its implications?

I would argue that its implications are narrow. It implies that if you
really really need to, you can transfer _linear_ programs -- with
practically no structure information -- between systems of different
vendors, if you're reasonably lucky, or have a motivated (financially,
strategically or otherwise) expert around.

That might be fine for supporting bugs, or benchmarking software, but it
is a far cry from an industry-wide solution that addresses the
representation and communication needs we have -- and will have -- in a
comprehensive way. To confirm this, it is enough to see that virtually
every solver connected to ampl uses the .nl file and associated library,
an example of a far superior solution in design and implementation.

> The "solutions" that are being proposed are just to change the format from 
> MPS to XML.  This wouldn't change how we do business, except we'd probably 
> need more gigabytes of storage to store all those very fat XML files. :->
> 

That is certainly not the solution I'm proposing. My presentation and
Bjarni's show that even the current proposals do a lot more than what MPS
does. In fact, finding an XML equivalent for MPS is about 1-3 days of
work, and we certainly don't need this many smart people together to
accomplish it.

As for the "fatness" of XML, it would be nice for our application if the
textual representation of XML objects were more terse. But XML's verbosity
will not be a serious problem, for three reasons:

First, the format can be designed to guarantee linear complexity in all
operations; Second, part of developing an XML format is defining a DOM (in
rough terms, a DOM is an access library). In almost all practical
scenarios, objects will get passed around between applications directly in
memory, using much more terse representations; Third, since we can express
a tremendous amount of structure using XML, we will actually produce
smaller files to begin with. Imagine for example building a matrix out of
blocks and having only one copy of the block. For an example of this see
my informs presentation. In addition, XML compresses extremely well. There
is even software specifically designed to compress XML, with which the
compressed XML becomes smaller than the compressed original data. See for
example http://www.research.att.com/sw/tools/xmill/.

Developing a new standard means finding a cheaper, faster, easier way to
convey mathematical programs of as many practical categories as possible,
with as much structure information as possible, in an efficient manner and
in the context we do business and research in. 

Now let me repost my question: Assume for a minute that we had such a
mechanism in place. In other words, assume that it were much much easier,
faster, and cheaper to communicate mathematical programming instances.
That brings two questions:

First, do people think there would be a greater number of profitable
applications involving an optimization component? Would there be new
opportunities for complex applications, such as smarter assembly line
products, or web-enabled sales decision support systems? Would there be
new opportunities for less complex applications, such as inventory
management modules for small business software, or handheld-based
applications? Would there be more research problems?

Second, assuming there are these applications, would your company or your
research group be interested in them?

Cheers,
Leo.

========================================================================
Leonardo B. Lopes                                       leo at iems.nwu.edu 
Ph.D. Student                                              (847)491-8470
IEMS - Northwestern University              http://www.iems.nwu.edu/~leo