[Coin-standards] minutes / strategy

[Irv Lustig]

Leo:

At 06:28 PM 4/8/02 -0500, Leonardo B. Lopes wrote:

>I value your opinion and experience tremendously, but it is obvious that I
>disagree with you here.

So we agree to disagree!

>  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).

I think you need to separate out the interest from academics and vendors, 
from the *users* of optimization in business settings. (By users here, I 
mean people who understand how to formulate optimization problems, not the 
end users of an application embedding optimization).  If I was still in 
academia, I would believe that it would be a good idea to come up with a 
standard. However, I work for a vendor, and the users of optimization 
software aren't banging down our doors asking for a new standard.  So, from 
where I sit, there is not a "standards problem" for those users of 
optimization.



>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 .nl file is a means to an end.  If someone wants to use AMPL, a .nl 
file provides the mechanism for hooking up a solver.  It is a solution that 
works, but it is NOT a trivial task to hook up a solver to AMPL!  It would 
have been great if AMPL had been designed to also provide an in-memory 
hookup to a solver.  That would have provided a cleaner solution for many 
users.  Maybe when a standard exists, AMPL would get re-engineered to 
provide that via your standard.

AMPL is a very nice modeling language.  If its implementation was not so 
directly tied to its command line interface, and the language design 
separated the imperative directives (solve, display, option setting, 
looping, etc.) from the modeling directives, AMPL could be a potential 
standard for representing problems.  However, the real impediment for the 
acceptance of any modeling language as such a standard is that when someone 
formulates a problem using a modeling language, the model is their 
intellectual property.  They are not keen on sharing that with others, 
including vendors!  We often find that when AMPL users want us to 
benchmark, they are unwilling to give us their AMPL models, but are willing 
to give us MPS files.  And we could be able to help them so much more if 
they gave us the AMPL model, because often changing a formulation can 
improve performance (especially for MIPs).

So one concern is that when you propose a standard that gets closer to a 
formulation, there may be less likelihood for people to share that standard 
with others.

>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;

Sure it has linear complexity.  For an LP with m rows, n columns, and nz 
nonzeros, the format can be parsed in O(n + m + nz) operations.  This means 
that the number of operations is some constant alpha times (n + m + nz). 
But you're ignoring the fact that alpha is on the order of 1.0e9. (Pardon 
my sarcasm and cynicism here).

>  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;

Now, things get more interesting!

>  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.

But then you'll get to the issue I mentioned above about having the format 
too close to the model and the intellectual property of the model 
developer.  I'm also not sure if people really "think" this way in 
modeling.  Certainly when you write an AMPL model, the block structure is 
not something you think about.  And would it be that easy to figure out the 
blocks from an AMPL model?  (Maybe so - this would be interesting for 
someone in academia to investigate).

>  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/.

Thanks for the pointer.


>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.

And how does a modeling language like AMPL not achieve this goal?


>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?

I don't think so.  The barrier today is having enough people out there who 
know how to apply optimization (i.e., do good modeling) in the first place.

>  Would there be new
>opportunities for complex applications, such as smarter assembly line
>products, or web-enabled sales decision support systems?

I don't think so.  See previous paragraph.

>  Would there be
>new opportunities for less complex applications, such as inventory
>management modules for small business software, or handheld-based
>applications?

I don't think so.  See previous paragraph.

>Would there be more research problems?

Yes.  A standard would help the research community.


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

I think the applications are there *today*.  A standard contributes very 
little to our ability to make those applications successful.


         -Irv Lustig
          ilustig at ilog.com
          Manager, Technical Services, ILOG Direct
          http://www.ilog.com/