The .nl format is possibly the most widely used format for representing mathematical optimization problems you’ve never heard of unless you are a solver developer. The reason it is not very well-known is because .nl is a low-level format designed for efficient machine input and output unlike algebraic modeling languages that are designed for human readability (at least some of them) and unlike MPS which is neither particularly human readable nor efficient.
Originally developed for
connecting solvers to AMPL,
the .nl format is now used in other modeling systems as well, including
It is supported by numerous commercial and open-source solvers, either natively or
via separate driver programs. For example, the
cplexamp executable included in the
accepts problems in this format. Cbc,
Ipopt and other COIN-OR
solvers have built-in support for it.
The AMPL Solver Library (ASL), which is mainly used to connect solvers to AMPL, includes a reference implementation of an .nl reader (parser). While it does its job well, it has some limitations. Most importantly, it always constructs the ASL representation of an optimization problem in memory. You cannot reuse the parser for anything else such as constructing a different problem representation. And it only supports reading from files or file-like objects, although, depending on the file system, they can be memory-backed.
Now there is an alternative .nl reader, included in the ampl/mp library, that addresses these limitations. It supports all features of the format including nonlinear functions and expressions as well as suffixes (arbitrary metadata that can be attached to variables, constraints, etc), logic and constraint programming features.
The new reader is fully reusable and is not limited to a specific problem representation. It provides a SAX-like sequential access parser API. What this means is that instead of constructing the memory representation of a problem, the reader sends notifications of problem constructs to the handler object. Unlike SAX, however, the handler uses static rather than dynamic polymorphism so its methods can be easily inlined at compile time.
The API of the new .nl reader is very simple, it consists of two functions
fmt::CStringRef are string references which can refer to
C strings or
As their names suggest, the first function reads a string containing an optimization problem in the .nl format while the second one reads an .nl file.
handler object receives notification of problem components.
For example, when the parser reads a binary expression, it invokes
OnBinary method. The
is designed in such a way that it is possible, although not necessary,
to construct a problem representation on the fly.
The ability to connect a custom handler makes unit testing much easier while reading input from memory makes it fast.
Now I am going to demonstrate how to use the reader on a simple example that counts the number of expressions of certain kind. This can be used, for instance, to filter out problems containing expressions not supported by some solver.
In this example I go over the file names passed as command-line arguments, read each file, count the number of divisions by non-constant expressions and print the file name together with expression count:
The header file
provides the declarations of
described above as well as the definition of the
This class provides the default implementations of handler methods that
ignore all input. This is perfect for our example, as we only need
to handle two types of expressions, numeric constant and division.
Expr type represents an expression. It is a simple enum as we don’t
construct an expression tree here, but only distinguish between constants
and other expressions. The expression type is passed as a template argument
NullNLHandler. This ensures that default handler methods such as
NullNLHandler::OnUnary also return
Expr. These methods
the expression objects they return which in this case gives the value
The implementation of
ExprCounter is very straightforward, the
method called by the .nl reader for binary expressions increments the
if the expression kind is division (
expr::DIV) and the right-hand side is not
a numeric constant. The
OnNumericConstant method returns
CONST to mark
a constant expression. This value is automatically propagated as an argument
to the parent expression if necessary.
main function iterates over command-line arguments containing file
ReadNLFile to parse each file passing an
to handle notifications.
Note that the example doesn’t contain any dynamic memory allocations. In fact the new .nl reader normally doesn’t use dynamic memory either. Together with inlining of handler methods and single-pass mmap-based input, this makes processing .nl files extremely fast.
Let’s build this example:
Now let’s get a bunch of nonlinear problems from the CUTE set, convert them into .nl format and pass them to our program:
nlreader-example program processes 712 .nl files, totaling 205 MiB,
in just 1.6 seconds. I plan to compare its performance to the reference ASL
reader in a follow-up post.
This functionality enables building new powerful tools for processing optimization problems. It can be used to directly construct problems in native solver formats bypassing intermediate representation, reformulate problems on the fly and convert them to other formats.
Note that the code described here is fresh from the
repository and, although it has been thoroughly tested,
it hasn’t been documented yet, other than with source comments.
Update 2016-03-07: Updated to the latest NL reader API which is now documented at http://ampl.github.io/nl-reader.html.comments powered by Disqus