Python interface to CUTEr test problems for optimization

Note!

PyCUTEr is now a part of PyOPUS library for Python. You can find out more about PyOPUS here.

About

CUTEr is a set of tools for integrating test problems described as SIF files with optimization algorithms for the purpose of testing the algorithm's performance. CUTEr problems are described in a special format (SIF) which is converted to a set of FORTRAN files by using a SIF decoder. These files are then compiled and linked with the CUTEr library and with your program which uses the CUTEr test problem. The CUTEr library provides a plethora of so-called tools - FORTRAN/C functions which evaluate and return various aspects of the test problem (objective function value, constraint values, gradients, constraints Jacobian, and Hessians). There are also CUTEr tools for obtaining information on the test problem and accessing the statistics (number of evaluations) CUTEr keeps internally.

The latest versions of the SIF decoder and CUTEr are available at
https://magi-trac-svn.mathappl.polymtl.ca/Trac/cuter.

PyCuter is a Python interface to CUTEr along with a set of tools which make it simple to compile, link, and import test problems described by SIF files.

Was it tested?

Until now PyCUTEr has only been tested on AMD64 Debian Linux (Squeeze), Python 2.6.6, Numpy 1.4.1 and SciPy 0.7.2. If you have any problems, report them to me. I can help fix things on x86 and AMD64 platform. Drop me a note if you test PyCUTEr on any other platform.

License

PyCUTEr (or to be fair the changes to CUTEr) are licensed under LGPLv2.1. It would be nice (although LGPL does not strictly require it) to send your changes back to me so I can publish them in the official implementation of PyCUTEr. You can use PyCUTEr almost any way you want (ain't this LGPL thing just great, huh) as long as you give me proper credit for it.

Installing PyCUTEr

Download the SIF decoder (revision 147) and the updated CUTEr package (based on revision 147). You will also need to install Python, NumPy, SciPy, gfortran, and gcc. Also install the Lapack and the Blas libraries.

Instead of using the updated CUTEr package you could download CUTEr revision 147 from
https://magi-trac-svn.mathappl.polymtl.ca/Trac/cuter
and patch it with this patch.

Older versions of PyCUTEr can be found here.

Unpack the SIF decoder, build it by running install_sifdec (answers to first four questions should be: PC, Linux, gfortran, double precision), and set the environmental variables SIFDEC and MYSIFDEC. Add $MYSIFDEC/bin to path so sifdecode will be accessible from anywhere. Also add $SIFDEC/common/man to MANPATH.

Unpack CUTEr, build it by running install_cuter (answers to first five questions should be: PC, Linux, gfortran, GNU gcc, double precision), and set the CUTER, and MYCUTER environmental variables. Add $CUTER/common/man to MANPATH. You should also add $CUTER/common/include to C_INCLUDE_PATH, $MYCUTER/double/lib to LIBPATH, and $MYCUTER/bin to PATH.

Download SIF files describing the available problems from http://www.cuter.rl.ac.uk/ and create a SIF repository (create a directory, unpack the problems, and set the MASTSIF environmental variable to point to the directory holding the SIF files).

Create a directory for the PyCUTEr cache. Set the PYCUTER_CACHE environmental variable to point to the cache directory. Add $PYCUTER_CACHE and $CUTER/common/src/python to the PYTHONPATH envorinmental variable. The last step will make sure you can access the cached problems and the pycutermgr module from Python.

A quick introduction to CUTEr test problems

CUTEr provides constrained and unconstrained test problems. The objective function is a map from Rⁿ to R:
  y = f(x)
where y is a real scalar (member of R) and x is a n-dimensional real vector (member of Rⁿ). The i-th component of x is denoted by x_i and is also referred to as the i-th problem variable. Problem variables can be continuous (take any value from R), integer (take only integer values) or boolean (only 0 and 1 are allowed as variable's value).

The optimization problem can be subject to simple bounds of the form
  bl_i ≤ x_i ≤ bu_i
where bl_i and bu_i denote the lower and the upper bound on the i-th component of vector x. If there is no lower (or upper) bound on x_i CUTEr reports bl_i=-1e20 (or bu_i=1e20).

Beside simple bounds on problem variables some CUTEr problems also provide more sophisticated constraints of the form
  cl_i ≤ c_i(x) ≤ cu_i   (inequality constraint) or
  c_i(x) = 0   (equality constraint)
where c_i is the i-th constraint function. CUTEr problems have generally m such constraints. In cl_i and cu_i the values -1e20 and 1e20 stand for -∞ and +∞. For inequality constraints either cl_i or cu_i is always infinite. If it is not, then it is 0. This means that every inequality constraint is of the form
  c_i(x) ≥ 0   or
  c_i(x) ≤ 0.
For equality constraints cl_i and cu_i are both equal to 0. All constraint functions c_i(x) are joined in a single vector-valued function (map from Rⁿ to R^m) named c(x).

CUTEr can order the constraints in such manner that equality constraints appear before inequality constraints. It is also possible to place linear constraints before nonlinear constraints. This of course reorders the components of c(x). Similarly variables (components of x) can also be reordered in such manner that nonlinear variables appear before linear ones.

Definitions of the Lagrangian function, the Jacobian matrix, and the Hessian matrix

The Lagrangian function is defined as
  L(x, v) = f(x) + v₁ c₁(x) + v₂ c₂(x) + ... + v_m c_m(x)
Vector v is m-dimensional. Its components are the Lagrange multipliers.

The Jacobian matrix (J) is the matrix of constraint gradients. One row corresponds to one constraint function c_i(x). The matrix has n columns. The element in the i-th row and j-th column is the derivative of the i-th constraint function with respect to the j-th problem variable
  J_ij = dc_i / dx_j

The Hessian matrix (H) is the matrix of second derivatives. The element in i-th row and j-th column corresponds to the second derivative with respect to the i-th and j-th problem variable.
  H_ij = d²f / (dx_i dx_j).
The Hessian is a symmetric matrix so it is sufficient to know its diagonal and its upper triangle.

Beside Hessian of the objective CUTEr can also calculate the Hessian of the Lagrangian and the Hessians of the constraint functions.

The gradient (of objective, Lagrangian, or constraint functions) is always taken with respect to the problem's variables. Therefore it always has n components.

What PyCUTEr offers

All compiled test problems are stored in a cache. The location of the cache can be set by defining the PYCUTER_CACHE environmental variable. If no cache location is defined the current working directory is used for caching the compiled test problems. PyCuter has a manager module named pycutermgr.

The manager module (pycutermgr) offers the following functions:
clearCache()
  remove a compiled problem from cache
prepareProblem()
  compile a problem, place it in the cache, and return a reference to the imported problem module
importProblem()
  import an already compiled problem from cache and return a reference to its module

Every problem module has several functions that access the corresponding problem's CUTEr tools:
getinfo()
  get problem description
varnames()
  get names of problem's variables
connames()
  get names of problem's constraints
objcons()
  objective and constraints
obj()
  objective and objective gradient
cons()
  constraints and constraints gradients/Jacobian
lagjac()
  gradient of objective/Lagrangian and constraints Jacobian
jprod()
  product of constraints Jacobian with a vector
hess()
  Hessian of objective/Lagrangian
ihess()
  Hessian of objective/constraint
hprod()
  product of Hessian of objective/Lagrangian with a vector
gradhess()
  gradient and Hessian of objective (if m=0) or
  gradient of objective/Lagrangian, Jacobian, and Hessian of Lagrangian (if m > 0)
scons()
  constraints and sparse Jacobian of constraints
slagjac()
  gradient of objective/Lagrangian and sparse Jacobian
sphess()
  sparse Hessian of objective/Lagrangian
isphess()
  sparse Hessian of objective/constraint
gradsphess()
  gradient and sparse Hessian of objective (if m=0) or
  gradient of objective/Lagrangian, sparse Jacobian, and sparse Hessian of Lagrangian (if m > 0)
report()
  get usage statistics

All sparse matrices are returned as scipy.sparse.coo_matrix objects.

Examples of PyCUTEr use

First you have to import the pycutermgr module

import pycutermgr

If you want to remove the HS71 problem from the cache, type

pycutermgr.clearCache('HS71')

To prepare the ROSENBR problem, type

pycutermgr.prepareProblem('ROSENBR')

Importing a prepared problem can be done in two ways. One is to use pycutermgr

rb=pycutermgr.importProblem('ROSENBR')

while the other is to use Python't import statement

import ROSENBR as rb

Now you can use the problem. Let's get the information about the imported problem and extract the initial point

info=rb.getinfo()
x0=info['x']

To evaluate the objective function's value at the extracted initial point, type

f=rb.obj(x0)
print "f(x0)=", f

To get help on all interface functions of the previously imported problem, type

help(rb)

You can also get help on individual functions of a problem interface

help(rb.obj)

The pycutermgr module has also builtin help

help(pycutermgr)
help(pycutermgr.importProblem)

For an example of PyCUTEr use with an unconstrained function see $CUTER/common/source/python/udemo.py. A demonstration of usage with a constrained function is in $CUTER/common/source/python/cdemo.py.

Advanced topics

Storing compiled problems in cache under arbitrary names
A problem can be stored in cache using a different name than the original CUTEr problem name (the name of teh corresponding SIF file) by specifying the destination parameter to pycutermgr.prepareProblem(). For instance to prepare the ROSENBR problem (the one defined by ROSENBR.SIF) and store it in cache as rbentry, type

pycutermgr.prepareProblem('ROSENBR', destination='rbentry')

Importing the compiled problem interface and its removal from the cache must now use rbentry instead of ROSENBR.

# Use pycutermgr.importProblem()
rb=pycutermgr.importProblem('rbentry')  

# Use the intrinsic Python import statement 
import pycuter.rbentry as rb  

# Remove the compiled problem from cache
pycutermgr.clearCache('rbentry')  

To check if a problem is in cache under the name 'rbentry' without trying to import the actual module, use

if pycutermgr.isCached('rbentry'):
	...

Specifying problem parameters and sifdecode command line options
Some CUTEr problems have parameters on which the problem itself depends. Often the dimension of the problem depends on some parameter. Such parameters must be passed to sifdecode with the -param option. PyCUTEr handles such parameters with the sifParams argument to pycuter.prepareProblem(). Parameters are passed in the form of a Python dictionary, where the key specifies the name of a parameter. The value of a parameter is converted using str() to a string and passed to sifdecode's command line as '-param key=value'.

# Prepare the LUBRIFC problem, pass NN=10 to sifdecode
pycutermgr.prepareProblem("LUBRIFC", sifParams={'NN': 10})

Arbitrary command line options can be passed to sifdecode by specifying them in form of a list of strings and passing the list to pycutermgr.prepareProblem() as sifOptions. The following is the equivalent of the last example

# Prepare the LUBRIFC problem, pass NN=10 to sifdecode
pycutermgr.prepareProblem("LUBRIFC", sifOptions=['-param', 'NN=10'])

Specifying variable and constraint ordering
To put nonlinear variables before linear variables set the nvfirst parameter to True and pass it to pycutermgr.prepareProblem().

pycutermgr.prepareProblem("SOMEPROBLEM", nvfirst=True)

To put equality constraints before inequality constraints set the efirst parameter to True.

pycutermgr.prepareProblem("SOMEPROBLEM", efirst=True)

pycutermgr.prepareProblem("SOMEPROBLEM", lfirst=True)

If both efirst and lfirst are set to True, the ordering is a follows: linear equality constraints followed by linear inequations, nonlinear equations, and finally nonlinear inequations.

Problem information
The problem information dictionary is returned by the getinfo() problem interface function. The dictionary has the following entries
name
  problem name
n
  number of variables
m
  number of constraints (excluding bounds)
x
  initial point (1D array of length n)
bl
  1D array of length n with lower bounds on variables
bu
  1D array of length n with upper bounds on variables
nnzh
  number of nonzero elements in the diagonal and upper triangle of sparse Hessian
vartype
  1D integer array of length n storing variable type
  0=real, 1=boolean (0 or 1), 2=integer
nvfirst
  boolean flag indicating that nonlinear variables were placed before linear variables
sifparams
  parameters passed to sifdecode with the sifParams argument to prepareProblem().
  None if no parameters were given
sifoptions
  additional options passed to sifdecode with the sifOptions argument to prepareProblem()
  None if no additional options were given.

Additional entries are available if the problem han constraints (m>0):
nnzj
  number of nonzero elements in sparse Jacobian of constraints
v
  1D array of length m with initial values of Lagrange multipliers
cl
  1D array of length m with lower bounds on constraint functions
cu
  1D array of length m with upper bounds on constraint functions
equatn
  1D boolean array of length m indicating whether a constraint is an equality constraint
linear
  1D boolean array of length m indicating whether a constraint is a linear constraint
efirst
  boolean flag indicating that equality constraints were places before inequality constraints
lfirst
  boolean flag indicating that linear constraints were placed before nonlinear constraints

The names of variables and constraints are returned by the varnames() and connames() problem interface functions.

Usage statistics
The usage statistics dictionary is returned by the report() problem interface function. The dictionary has the following entries
f
  number of objective evaluations
g
  number of objective gradient evaluations
H
  number of objective Hessian evaluations
Hprod
  number of Hessian multiplications with a vector
tsetup
  CPU time used in setup
trun
  CPU time used in run

For constrained problems the following additional members are available
c
  number of constraint evaluations
cg
  number of constraint gradient evaluations
cH
  number of constraint Hessian evaluations

Problem preparation and internal cache organization
The cache ($PYCUTER_CACHE) has one single subdirectory named pycuter holding all compiled problem interafaces. This way problem interface moduels are accessible as pycuter.NAME because $PYCUTER_CACHE is also listed in PYTHONPATH.

$PYCUTER_CACHE/pycuter has a dummy __init__.py file generated by pycutermgr.prepareProblem() which specifies that $PYCUTER_CACHE/pycuter is a Python module. Every problem has its own subdirectory in $PYCUTER_CACHE/pycuter. In that subdirectory problem decoding (with sifdecode) and compilation (with gfortran and Python distutils) take place. pycutermgr.prepareProblem() also generates an __init__.py file for every problem which takes care of initialization when the problem interface is imported.

The actual binary interaface is in _pycuteritf.so. The __init__.py script requires the presence of the OUTSDIF.d file where the problem description is stored. Everything else is neded at compile time only.

Some functions in the _pycuteritf.so module are private (their name starts with an underscore. These functions are called by wrappers defined in problem's __init__.py. An example for this are the sparse CUTEr tools like scons(). scons() is actually a wrapper defined in __init__.py. It calls the _scons() function from the problem's _pycuteritf.so binary interface module and converts its return values to a scipy.sparse.coo_matrix object. scons() returns the scipy.sparse.coo_matrix object for J instead of a NumPy array object. The problem's _pycuteritf binary module is also accessible. If the interface module is imported as rb then the _scons() interface function can be accessed as rb._pycuteritf._scons.

Changes to the original CUTEr

Revision 152

No additional changes with respect to PyCUTEr based on revision 147.

Revision 147

No additional changes with respect to PyCUTEr based on revision 116.

Revision 116

$CUTER/config/all.cf
Added -fPIC to CFlags because Python binary modules are shared libraries linked with the CUTEr library. Therefore the CUTEr library must also be compiled with -fPIC.

cuter2/config/linux.cf
Added -fPIC to FortranFlags for the same reason.

cuter2/common/src/tools/pycuteritf.c
The source code of the binary problem interface.

cuter2/common/src/python/pycutermgr.py
The PyCUTEr problem manager module.

cuter2/common/src/python/udemo.py
An example of PyCUTEr use with an unconstrained problem.

cuter2/common/src/python/cdemo.py
An example of PyCUTEr use with a constrained problem.

Bugs fixed

2013-09-18 - fixed a bug caused by Ubuntu's gcc flag --no-as-needed (the built problems could not be loaded into Python). Pointed out by Jae Hwa Lee, fixed by Felix Lenders.

2013-05-14 - Added isCached() to pycutermgr.py. Closed memory leaks when tuples or dictionaries are returned.

2011-09-01 - fixed a minor bug that caused PyCuter to attempt to create __init__.py in $PYCUTER_CACHE/pycuter before $PYCUTER_CACHE/pycuter was even created. Thanks to Jae Hwa Lee.

Last update: Sep 22 2017