Crème: Coin-OR Relaxation Method

Crème is an implementation of the randomized thermal relaxation method to find a feasible solution of the Maximum Feasible Subsystem (MaxFS) problem. The MaxFS problem consists, given a Linear Programming problem


generally infeasible, in finding a feasible subsystem containing a maximum number of inequalities.

The algorithm is described in the paper

  1. Amaldi, P. Belotti, R. Hauser, Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem. In M. Jünger, V. Kaibel (ed.), Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 8-10, 2005, pages 249-264, 2005.

Download, installation and usage

Crème is found on the COIN-OR project page. It can be downloaded with Subversion -- see also some instructions on using svn. Run the command:

svn co creme-trunk

to get the source code of the trunk version (the only version available for now). Please read the INSTALL file for instructions on how to obtain them.

In general, the trunk version of Crème is subject to changes that might make it unstable or incorrect at times. In order to be up-to-date with such changes, you may run the command svn update within the Creme directory. A stable version of Crème will be available soon, and will only be changed for bug fixes. A stable release will be available at This release is not subject to change, and can also be downloaded as a tar ball.

To install Crème, plese refer to general installation instructions for COIN-OR projects.

The impatient may want to issue the following commands:

svn co creme-trunk
cd creme-trunk
mkdir build
cd build
../configure -C
make test
make install

The above commands place the executable file creme in the Creme/build/bin/ directory, libraries in Creme/build/lib/, and include files in Creme/build/include/. An alternative directory can be specified with the --prefix option of configure. For instance, when replacing "../configure -C" above with

../configure -C --prefix=/usr/local

the executable will be installed in /usr/local/bin/, the libraries in /usr/local/lib/, and the include files in /usr/local/include/. Crème is run as follows:

creme myinstance.bz2

where myinstance.bz2 is a bzip2'ed file (.bz2) containing number of inequalities and of variables of the infeasible system, coefficients of matrix A, and elements of the right-hand side vector b. A definition of the file format is available here.

You may also specify a set of options to tweak the performance of Crème. You can visualize them by simply running


at the command line.


A user manual will be available soon, with explanations on most options available in Crème. Doxygen documentation is also still unavailable, and when complete it will be generated by running

make doxydoc

from the same build/ directory where you ran configure, make, and make install. Documentation in both html and LaTeX format can be found in the Doc/ subdirectory. Fire up your browser and take a look at Doc/html/index.html for documentation of Crème.

Crème is maintained by Pietro Belotti (creme@…).

Web page:

Crème does not have any dependency. If you want to be able to make changes to Crème, download BuildTools.

External resources: Coin-OR, Eclipse Public License.

Improve this page, report a bug, contribute to Crème

As an open-source code, contributions to Crème are welcome. To submit a contribution, please follow the COIN-OR guidelines.

In order to report a bug, use the ticket system. All you need to do is

  1. Register and login,
  2. Create a ticket.

In order to ensure that your ticket is addressed in a timely fashion, please try to be as exhaustive as you can in the bug report, for instance by reporting what version of Crème you have downloaded and what operating system you are using, and again by attaching the model/data files with which the crash occurred.


  • Pietro Belotti (FICO)
Last modified 4 years ago Last modified on Sep 14, 2013 11:14:19 AM