CoMISo  Constrained MixedInteger Solver
CoMISo  Constrained MixedInteger Solver
This is the project page of the Constrained MixedInteger Solver (short CoMISo) developed at the Computer Graphics Group of the RWTH Aachen University, which emerged from our MixedInteger Quadrangulation project.
This software provides a convenient tool for setting up and solving linear systems stemming from quadratic energies subject to linear equality constraints as well as to integer constraints. Basically only the system matrix, the constraints and the variables to be rounded are provided to the solver which returns a properly indexed solution vector. This drastically minimizes the programmer's effort as a proper elimination of the constraints and the necessary reindexing is taken care of internally. The difference to popular constraining techniques such as Lagrangian Multipliers, which require no reindexning (but unfortunately result in larger, nonpositive semidefinite systems), is that CoMISo efficiently eliminates the constraints from the system matrix, yielding a smaller system while at the same time preserving positive semidefiniteness.
The solver together with example code to get you started can be found below.
If you decide to use the CoMISo solver in your research, please cite the accompanying publication Practical MixedInteger Optimization for Geometry Processing.
Here is a link to CoMISo's mailing list.
License
The CoMISo solver library is released under the GPL license, for commercial use contact Henrik Zimmer or David Bommes.
Features (NEW Version 1.1!)

Less Dependencies! Only two header libraries needed for using the constrained mixedinteger solver (GMM++ and Eigen3)

Efficient resolve of constrained systems! Resolve constrained system using updated (system and/or constraint) right hand sides!

/NSolver  simple nonlinear solver c++ interfaces for:

/EigenSolver  interface for largescale eigenvalue problems ARPACK

/Solver  several interfaces for common linear system solvers:
History
19072013 : Due to popular demand, we now supply Build Instructions for Windows
16112012 : Major Update: Version 1.1 (more features, less dependencies)
16112010 : COMISO  Updated Release (new features, performance increase)
16112010 : HarmonicExamplePlugin  Minor Update (Namespace COMISO_GMM)
19052010 : Minor Memory Leak fixed in CholmodSolver.cc. Thanks Ashish Myles.
Download
The Constrained MixedInteger Solver as well as the exemplary OpenFlipper Plugin are available via GIT server:

CoMISo Solver
 GIT repository: git clone recursive https://graphics.rwthaachen.de:9000/CoMISo/CoMISo.git

Example OpenFlipper Plugin
 SVN repository: svn co http://www.openflipper.org/svnrepo/CoMISo/trunk/PluginHarmonicExample PluginHarmonicExample
Installation CoMISo library
Prerequisites
Building and using the CoMISo package is made simple by using the automated build system cmake. However, additional to a reasonable C++ development environment the following packages are required:
 GMM++  A generic matrix library
 CHOLMOD  A stable sparse Cholesky solver (contained in SuiteSparse)
 BLAS  Basic linear algebra subprograms
 LAPACK  Linear Algebra Package
Note: your operating system might already provide easytouseandinstall, prebuilt packages. For example Ubuntu based platforms can use
# aptget install libgmmdev libblasdev libsuitesparsedev
to get the necessary packages.
on a Windows System
On Windows or Macintosh systems the corresponding packages usually need to be manually downloaded and installed.
 Download: Build instructions for Windows
Unpacking
Extract (check out) the package into a directory of your choice (DIR). For integration with OpenFlipper, it is advantageous to unpack into the OpenFlipper library directory (e.g. /home/user/OpenFlipper/libs/) this way the solver is build automatically when building OpenFlipper
# tar xfvz CoMISo.tar.gz /home/user/OpenFlipper/libs/
Building
The CoMISo library can be built to be integrated with the OpenFlipper framework or as a standalone package.
1) Building CoMISo standalone
Having extracted the packages into the your directory of choice (DIR), perform
# cd DIR/CoMISo
mkdir build && cd build && cmake ..
make
the shared library libCoMISo.so can now be found under
DIR/CoMISo/build/Build/lib/CoMISo/
and the examples can be found under
DIR/build/Build/bin/
NOTE!: on some systems the SPQR library from SuiteSparse is not available as shared library libspqr.so by default and will cause linking problems. If you do not need it, it can be disabled by the flag SUITESPARSE_SPQR_VALID in the cmake interface.
2) Building CoMISo for OpenFlipper integration
Having extracted the packages into the OpenFlipper libs directory (/home/user/OpenFlipper/libs/), the package will automatically be build together with OpenFlipper:
# cd /home/user/OpenFlipper/build
make
the shared library libCoMISo.so can now be found under
/home/user/OpenFlipper/build/Build/lib/OpenFlipper/
Usage
To get acquainted with the functionality of the solver, the example programs (/DIR/CoMISo/Examples/) are a good start.
There are two different types of solver approaches for minimizing Bxb^{2}
1) The factored approach, B^{T}Bx=B^{T}b.
Here one supplies a, usually overdetermined, m x (n+1) rowmatrix (Bb_) with the rows being the m linear equations of the system, b_{0}x_{0}+...+b_{n}x_{n}=b_{n+1}. The constraints are eliminated directly from the B_ matrix before B^{T}B is formed.
2) The quadratic approach, Ax=a.
Here one supplies the n x n system matrix A=B^{T}B and the right handside a=B^{T}b. I.e. the partial derivatives of the quadratic energy. Here the constraints are eliminated directly from the A matrix.
Basically the difference consists in whether B^{T}B and the right handside are formed by the user or by the solver, and at what stage the constraints are eliminated.
Both solver approaches and other functions of the library are demonstrated in the examples.
HarmonicExamplePlugin  the example OpenFlipper plugin
The provided examples (above) already demonstrate the basic functionality of the solver and how to write applications using it.
To give an example for the integration of the CoMISo library into external software projects, an OpenFlipperPlugin: HarmonicExamplePlugin, is provided, showing
 how to incorporate the external solver into the OpenFlipper environment and
 a demo application utilizing the CoMISo solver.
Functionality
 The Plugin sets up a simple Laplace equation system on an input mesh (with boundaries).
 To demonstrate the constraintelimination, the vertices on each boundary of the mesh are constrained to have the same value. Furthermore, to shown simple linear constraints, the boundaries are constrained to have values differing by 5.
 Integer constraints can be added by selecting vertices of the mesh. The values of all selected vertices will be rounded to the closest integers by the solver, forcing some harmonic isolines to pass through the selected vertex. Multiple/none or all vertices can be selected.
Building the example OpenFlipper plugin  HarmonicExamplePlugin
Provided that the CoMISo has been installed and integrated into OpenFlipper as explained above, this step is now very easy.
1) download and unpack the HarmonicExamplePlugin.tar.gz to the OpenFlipper root
2) rebuild OpenFlipper and the plugin is added/built automatically
Feedback
We are grateful for feedback! Please send suggestions, patches, bug reports, questions and comments to David Bommes.