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

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, quadratic, and general nonlinear part. The linear and quadratic parts are specified via variable indices and coefficients, while the general nonlinear part is specified via an expression tree. 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 a set of methods to compute functions values, gradients, Jacobians, and Hessians for a given NLP. 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/nlpi/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/nlpi/nlpi_xyz.c and src/nlpi/nlpi_xyz.h into files named "nlpi_mynlpi.c" and "nlpi_mynlpi.h".
    Make sure to adjust your Makefile such that these files are compiled and linked to your project.
  2. Use SCIPcreateNlpSolverMynlpi() in order to include the NLPI into your SCIP instance, e.g., in the main file of your project (see, e.g., src/main.c in the Coloring example).
  3. Open the new files with a text editor and replace all occurrences of "xyz" by "mynlpi".
  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).

Properties of an NLPI

At the top of the new file "nlpi_mynlpi.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 this data structure, you can store the data of your solver interface and of a specific NLP problem. For example, you could store a pointer to the block memory data structure 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_mynlpi.c", you can find the interface method SCIPcreateNlpSolverXyz(), which also appears in "nlpi_mynlpi.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 by calling the method SCIPnlpiCreate(). SCIPcreateNlpSolverXyz() 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( SCIPallocMemory(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. Currently, all NLPI callbacks are fundamental.

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

NLPICOPY

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

NLPIFREE

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

NLPIGETSOLVERPOINTER

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

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.

NLPIGETPROBLEMPOINTER

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

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 and quadratic coefficients, expression trees, 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.

NLPICHGQUADCOEFS

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

NLPICHGEXPRTREE

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

NLPICHGNONLINCOEF

The NLPICHGNONLINCOEF callback is executed to change a single parameter in the (parametrized) expression tree 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.

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, these values can 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.

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.

NLPIGETINTPAR

The NLPIGETINTPAR callback can be used to request the value of an integer valued NLP parameter.

NLPISETINTPAR

The NLPISETINTPAR callback is executed to set the value of an integer valued NLP parameter.

NLPIGETREALPAR

The NLPIGETREALPAR callback can be used to request the value of a real valued NLP parameter.

NLPISETREALPAR

The NLPISETREALPAR callback is executed to set the value of a real valued NLP parameter.

NLPIGETSTRINGPAR

The NLPIGETSTRINGPAR callback can be used to request the value of a string valued NLP parameter.

NLPISETSTRINGPAR

The NLPISETSTRINGPAR callback is executed to set the value of a string valued NLP parameter.