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 problemAx ≤ b,
generally infeasible, in finding a feasible subsystem containing a maximum number of inequalities.
The algorithm is described in the paper
- 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
svn co https://projects.coin-or.org/svn/Creme/trunk 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 https://projects.coin-or.org/svn/Creme/releases/0.0.1. 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 https://projects.coin-or.org/svn/Creme/trunk creme-trunk cd creme-trunk mkdir build cd build ../configure -C make 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:
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
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.
Resources and links
Crème is maintained by Pietro Belotti (creme@…).
Web page: https://projects.coin-or.org/Creme/wiki
Crème does not have any dependency. If you want to be able to make changes to Crème, download BuildTools.
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
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)