Working with optimization problems in .nl files

In one of the previous posts I have described an API for reading .nl files. The NL reader API is now stable and documented at http://ampl.github.io/nl-reader.html. Also you can find a few examples of using it in nl-example.cc. It is still the way to go if you want to process .nl files in the most efficient way. However, if you want to load the complete optimization problem and work with it, the NL reader will require you to manage the data structures that represent the problem yourself. Fortunately, the AMPL/MP library now provides a new API for working with optimization problems and this post will introduce this new API.

The optimization problem is represented by the mp::Problem type which provides methods for accessing variables, objectives (multiple objectives are supported) and constraints. It can handle all types of optimization problems that the NL format can represent including LP, MIP, quadratic, general nonlinear and constraint programming problems.

Optimization problems can be constructed programmatically or read from .nl files (other input formats will be added in the future). Here’s an example of loading a problem from an .nl file:

#include <mp/nl-reader.h>
#include <mp/problem.h>

int main() {
  mp::Problem p;
  ReadNLFile("diet.nl", p);
}

As you can see, this example uses the NL reader API function ReadNLFile but passes a reference to the Problem object instead of an NL handler as a second argument. ReadNLFile automatically recognizes this and constructs an optimization problem instead of sending notifications of NL constructs to it. Reading problems from memory is also supported with ReadNLString.

But why yet another API, doesn’t the AMPL Solver Library (ASL) have the same functionality? The difference from the ASL is that the new API is simpler, fully type-safe (no unsafe casts required), faster, and allows modification of the problem after it has been loaded that can be used to implement transformations. The new implementation is already ~36% faster on the CUTE test set and it hasn’t been even optimized yet. The current limitation is that it doesn’t provide support automatic differentiation, but this will be addressed in the future.

As for the API simplicity, here’s a concrete example of reading a problem from an .nl file and checking if the initial solution is feasible using AMPL/MP:

#include <mp/nl-reader.h>
#include <mp/problem.h>

int main() {
  mp::Problem p;
  ReadNLFile("diet.nl", p);
  if (p.has_nonlinear_cons() || p.num_logical_cons() != 0) {
    std::puts("problem has nonlinear constraints");
    return 1;
  } 
  for (auto var: p.vars()) {
    if (!(var.lb() <= var.value() && var.value() <= var.ub())) {
      std::puts("infeasible");
      return 1;
    }
  }
  for (auto con: p.algebraic_cons()) {
    double body = 0;
    for (auto term: con.linear_expr())
      body += term.coef() * p.var(term.var_index()).value();
    if (!(con.lb() <= body && body <= con.ub())) {
      std::puts("infeasible");
      return 1;
    }
  }
  std::puts("feasible");
}

and the same using ASL:

#include <cstdio>
#include <cstring>
#include <asl.h>

int main() {
  ASL *asl = ASL_alloc(ASL_read_fg);
  const char stub[] = "diet";
  FILE *f = jac0dim(stub, std::strlen(stub));
  if (asl->i.nlc_ != 0 || asl->i.n_lcon_ != 0) {
    std::puts("problem has nonlinear constraints");
    return 1;
  }
  asl->i.want_xpi0_ = 1;
  asl->i.Uvx_ = static_cast<real*>(malloc(asl->i.n_var_ * sizeof(real)));
  asl->i.Urhsx_ = static_cast<real*>(malloc(asl->i.n_con_ * sizeof(real)));
  fg_read(f, 0);
  for (int i = 0; i < asl->i.n_var_; ++i) {
    if (!(asl->i.LUv_[i] <= asl->i.X0_[i] && asl->i.X0_[i] <= asl->i.Uvx_[i])) {
      std::puts("infeasible");
      return 1;
    }
  }
  for (int i = 0; i < asl->i.n_con_; ++i) {
    double body = 0;
    for (cgrad *term = asl->i.Cgrad_[i]; term; term = term->next)
      body += term->coef * asl->i.X0_[term->varno];
    if (!(asl->i.LUrhs_[i] <= body && body <= asl->i.Urhsx_[i])) {
      std::puts("infeasible");
      return 1;
    }
  }
  std::puts("feasible");
}

Even this little example shows the advantage of the new API where you can work with abstractions like variables and constraints rather than with a single big ASL data structure. The new API provides iterators over problem components which you can use with the C++ standard library algorithms. Here’s an example that finds a variable with nonzero value:

auto vars = p.vars();
auto var = std::find_if(vars.begin(), vars.end(),
                        [](mp::Problem::Variable v) { return v.value() != 0; });

The new API is nearly complete supporting all problems that can be represented in NL files but it is still being documented and finalized. For now you can refer to the source which is pretty straightforward and commented. Also feel free to leave questions or comments below.

comments powered by Disqus