Scippy

SCIP

Solving Constraint Integer Programs

How to add interfaces to nonlinear programming solvers

NLPIs are used to interface a solver for nonlinear programs (NLP). It is used, e.g., to solve convex relaxations of the problem or to find locally optimal solutions of nonlinear relaxations or subproblems. The NLPI has been designed such that it can be used independently of a SCIP problem.

While the NLPI itself corresponds to the solver interface, the NLPIPROBLEM corresponds to the (solver specific) representation of a concrete nonlinear program. An NLP is specified as a set of indexed variables with variable bounds, an objective function, and a set of constraints, where each constraint is specified as a function which is restricted to lie between given left and right hand sides (possibly infinite). A function consists of a linear and a nonlinear part. The linear part is specified via variable indices and coefficients, while the nonlinear part is specified via an expression. That is, the user of the NLPI does not provide function evaluation callbacks but an algebraic representation of the NLP. Interfaces for solvers that require function evaluations can make use of the NLPIORACLE, which provides functionality to store a NLP and compute functions values, gradients, Jacobians, and Hessians. See the interface to Ipopt for an example on how to use the NLPIORACLE.

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

We now explain how users can add their own NLP solver interface. Take the interface to Ipopt (src/scip/nlpi_ipopt.cpp) as an example. Unlike most other plugins, it is written in C++. Additional documentation for the callback methods of an NLPI, in particular for their input parameters, can be found in the file type_nlpi.h.

Here is what you have to do to implement an NLPI:

  1. Copy the template files src/scip/nlpi_xyz.c and src/scip/nlpi_xyz.h into files named "nlpi_mysolver.c" and "nlpi_mysolver.h". Make sure to adjust your Makefile such that these files are compiled and linked to your project.
  2. Use SCIPincludeNlpSolverMysolver() in order to include the NLPI into your SCIP instance, e.g., in the main file of your project (see, e.g., src/cmain.c in the Binpacking example).
  3. Open the new files with a text editor and replace all occurrences of "xyz" by "mysolver".
  4. Adjust the properties of the nlpi (see Properties of an NLPI).
  5. Define the NLPI and NLPIPROBLEM data (see NLPI Data).
  6. Implement the interface methods (see Interface Methods).
  7. Implement the fundamental callback methods (see Fundamental Callback Methods of an NLPI).
  8. Implement the additional callback methods (see Additional Callback Methods of an NLPI). This is optional.

Properties of an NLPI

At the top of the new file "nlpi_mysolver.c", you can find the NLPI properties. These are given as compiler defines. The properties you have to set have the following meaning:

NLPI_NAME: the name of the NLP solver interface.
This name is used in the interactive shell to address the NLPI. Additionally, if you are searching for an NLPI with SCIPfindNlpi(), this name is looked up. Names have to be unique: no two NLPIs may have the same name.
NLPI_DESC: the description of the NLPI.
This string is printed as a description of the NLPI in the interactive shell.
NLPI_PRIORITY: the priority of the NLPI.
If an NLP has to be solved, an NLP solver has to be selected. By default, the solver with the NLPI with highest priority is selected. The priority of an NLPI should be set according to performance of the solver: solvers that provide fast algorithms that are usually successful on a wide range of problems should have a high priority. An easy way to list the priorities of all NLPIs is to type "display nlpis" in the interactive shell of SCIP.

NLPI Data

Below the header "Data structures" you can find structs which are called struct SCIP_NlpiData and struct SCIP_NlpiProblem. In these data structures, you can store the data of your solver interface and of a specific NLP problem. For example, you could store a pointer to your NLP solver environment object in the SCIP_NlpiData data structure and store a pointer to an NLPIORACLE in the SCIP_NlpiProblem data structure.

Interface Methods

At the bottom of "nlpi_mysolver.c", you can find the interface method SCIPincludeNlpSolverXyz(), which also appears in "nlpi_mysolver.h".

This method only has to be adjusted slightly. It is responsible for creating an NLPI that contains all properties and callback methods of your solver interface and included it into SCIP by calling the method SCIPincludeNlpi(). SCIPincludeNlpSolverXyz() is called by the user (e.g., SCIP), if (s)he wants to use this solver interface in his/her application.

If you are using NLPI data, you have to allocate the memory for the data at this point. You can do this by calling:

SCIP_CALL( SCIPallocBlockMemory(scip, &nlpidata) );

You also have to initialize the fields in struct SCIP_NlpiData afterwards. For freeing the NLPI data, see NLPIFREE.

Fundamental Callback Methods of an NLPI

The fundamental callback methods of the plugins are the ones that have to be implemented in order to obtain an operational algorithm. Most NLPI callbacks are fundamental.

Additional documentation of the callback methods, in particular to their input parameters, can be found in type_nlpi.h.

NLPIFREE

The NLPIFREE callback is executed if the NLP solver interface data structure should be freed, e.g., when a SCIP instance is freed.

NLPICREATEPROBLEM

The NLPICREATEPROBLEM callback is executed if a particular NLP problem is to be created. The callback method should initialize a SCIP_NlpiProblem struct here that corresponds to an empty NLP.

NLPIFREEPROBLEM

The NLPIFREEPROBLEMPOINTER callback is executed if a particular NLP problem is to be freed. The callback method should free a SCIP_NlpiProblem struct here.

NLPIADDVARS

The NLPIADDVARS callback is executed if a set of variables with lower and upper bounds and names should be added to a particular NLP. The callback method must add the new variables behind the previously added variables, if any. If NULL is given for the lower bounds arguments, -infinity is assumed as lower bound for each new variable. If NULL is given for the upper bounds arguments, +infinity is assumed as upper bound for each new variable. It is also permitted to use NULL for the names argument.

NLPIADDCONSTRAINTS

The NLPIADDCONSTRAINTS callback is executed if a set of constraints should be added to a particular NLP. Constraints are specified by providing left- and right-hand-sides, linear coefficients, expressions, and constraint names. All of these arguments are optional, giving NULL for left-hand-sides corresponds to -infinity, giving NULL for right-hand-sides corresponds to +infinity.

NLPISETOBJECTIVE

The NLPISETOBJECTIVE callback is executed to set the objective function of a particular NLP.

NLPICHGVARBOUNDS

The NLPICHGVARBOUNDS callback is executed to change the bounds on a set of variables of an NLP.

NLPICHGCONSSIDES

The NLPICHGCONSSIDES callback is executed to change the sides on a set of constraints of an NLP.

NLPIDELVARSET

The NLPIDELVARSET callback is executed to delete a set of variables from an NLP. The caller provides an array in which for each variable it is marked whether it should be deleted. In the same array, the method should return the new position of each variable in the NLP, or -1 if it was deleted.

NLPIDELCONSSET

The NLPIDELCONSSET callback is executed to delete a set of constraints from an NLP. The caller provides an array in which for each constraint it is marked whether it should be deleted. In the same array, the method should return the new position of each constraint in the NLP, or -1 if it was deleted.

NLPICHGLINEARCOEFS

The NLPICHGLINEARCOEFS callback is executed to change the coefficients in the linear part of the objective function or a constraint of an NLP.

NLPICHGEXPR

The NLPICHGEXPR callback is executed to replace the expression of the objective function or a constraint of an NLP.

NLPICHGOBJCONSTANT

The NLPICHGOBJCONSTANT callback is executed to change the constant offset of the objective function of an NLP.

NLPISOLVE

The NLPISOLVE callback is executed when an NLP should be solved. The solver may use the initial guess provided by NLPISETINITIALGUESS as starting point. The status of the solving process and solution can be requested by NLPIGETSOLSTAT, NLPIGETTERMSTAT, NLPIGETSOLUTION, and NLPIGETSTATISTICS.

NLPIGETSOLSTAT

The NLPIGETSOLSTAT callback can be used to request the solution status (solved, infeasible, ...) after an NLP has been solved.

NLPIGETTERMSTAT

The NLPIGETTERMSTAT callback can be used to request the termination reason (normal, iteration limit, ...) after an NLP has been solved.

NLPIGETSOLUTION

The NLPIGETSOLUTION callback can be used to request the primal and dual solution values after an NLP solve. The method should pass pointers to arrays of variable values to the caller. It is possible to return only primal values for the variables, but no values for the dual variables, e.g., if a solver does not compute such values.

NLPIGETSTATISTICS

The NLPIGETSTATISTICS callback can be used to request the statistical values (number of iterations, time, ...) after an NLP solve. The method should fill the provided NLPSTATISTICS data structure.

Additional Callback Methods of an NLPI

The additional callback methods do not need to be implemented in every case.

NLPICOPY

The NLPICOPY callback is executed if the plugin should be copied, e.g., when a SCIP instance is copied.

It is advisable to implement this callback to make the NLP solver available in sub-SCIPs. Note that the sub-NLP heuristic solves NLPs in a sub-SCIP.

NLPIGETSOLVERPOINTER

The NLPIGETSOLVERPOINTER callback can be used to pass a pointer to a solver specific data structure to the user. Return NULL if you do not have a pointer to return.

NLPIGETPROBLEMPOINTER

The NLPIGETPROBLEMPOINTER callback can be used to pass a pointer to a solver specific data structure of the NLP to the user.

NLPISETINITIALGUESS

The NLPISETINITIALGUESS callback is executed to provide primal and dual initial values for the variables and constraints of an NLP. For a local solver, it is strongly advisable to implement this callback, as these values should be used as a starting point for the search. It is possible to pass a NULL pointer for any of the arguments (primal values of variables, dual values of variable bounds, dual values of constraints). In this case, the solver should clear previously set starting values and setup its own starting point.