Scippy

SCIP

Solving Constraint Integer Programs

How to add interfaces to expression interpreters

An expression interpreter is a tool to compute point-wise the function values, gradients, and Hessians of algebraic expressions which are given in the form of an expression. Typically, this is done via automatic differentiation. It is used, e.g., by an NLP solver interface to compute Jacobians and Hessians for the solver.

The expression interpreter interface in SCIP has been implemented similar to those of the LP solver interface (LPI). For one binary, exactly one expression interpreter has to be linked. The expression interpreter API has been designed such that it can be used independently from a SCIP problem.

A complete list of all expression interpreters contained in this release can be found here.

We now explain how users can add their own expression interpreters. Take the interface to CppAD (exprinterpret_cppad.cpp) as an example. Unlike most other plugins, it is written in C++.

Additional documentation for the callback methods of an expression interpreter, in particular for their input parameters, can be found in the file exprinterpret.h.

Here is what you have to do to implement an expression interpreter:

  1. Copy the file exprinterpret_none.c into a file named "exprinterpret_myad.c". Make sure to adjust your build system such that this file is compiled and linked to your project instead of exprinterpret implementations.
    If you are adding a new default plugin, this means updating the src/CMakeLists.txt and Makefile files in the SCIP distribution.
  2. Open the new file with a text editor.
  3. Define the expression interpreter data (see Expression Interpreter Data).
  4. Implement the interface methods (see Interface Methods).

Expression Interpreter Data

In struct SCIP_ExprInt, you can store the general data of your expression interpreter. For example, you could store the environment of your automatic differentiation code.

Interface Methods

The expression interpreter has to implement a set of interface method. In your "exprinterpret_myad.c", these methods are mostly dummy methods that return error codes.

SCIPexprintGetName

The SCIPexprintGetName() method should return the name of the expression interpreter.

SCIPexprintGetDesc

The SCIPexprintGetDesc() method should return a short description of the expression interpreter, e.g., the name of the developer of the code.

SCIPexprintGetCapability

The SCIPexprintGetCapability() method should return a bitmask that indicates the capabilities of the expression interpreter, i.e., whether it can compute gradients and Hessians.

SCIPexprintCreate

The SCIPexprintCreate() method is called to create an expression interpreter data structure. The method should initialize a struct SCIP_ExprInt here.

SCIPexprintFree

The SCIPexprintFree() method is called to free an expression interpreter data structure. The method should free a struct SCIP_ExprInt here.

SCIPexprintCompile

The SCIPexprintCompile() method is called to initialize the data structures that are required to evaluate a particular expression. The expression interpreter can create and return data that is particular to a given expression in the argument exprintdata.

SCIPexprintFreeData

The SCIPexprintFreeData() method is called to free the data that is particular to a given expression and was possibly created in SCIPexprintCompile().

SCIPexprintGetExprCapability

The SCIPexprintGetExprCapability() method is called to request the capability to evaluate a specific expression by the expression interpreter.

In cases of user-given expressions, higher order derivatives may not be available for the user-expression, even if the expression interpreter could handle these. This method allows to recognize that, e.g., the Hessian for an expression is not available because it contains a user expression that does not provide Hessians.

SCIPexprintEval

The SCIPexprintEval() method is called when the value of an expression should be computed for a point.

SCIPexprintGrad

The SCIPexprintGrad() method is called when the gradient of an expression represented by an expression should be computed for a point.

SCIPexprintHessianSparsity

The SCIPexprintHessianSparsity() method is called when the sparsity structure of the Hessian matrix should be computed and returned. Only the position of nonzero entries in the lower-triangular part of Hessian should be reported.

SCIPexprintHessian

The SCIPexprintHessian() method is called when the Hessian of an expression should be computed for a point.