Constrained Mixed-Integer Solver

This is the project page of the Constrained Mixed-Integer Solver (short CoMISo) developed at the Computer Graphics Group of the RWTH Aachen, which emerged from our Mixed-Integer Quad Meshing 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, non-positive 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.

An accompanying publication is in the making and will appear on this site in the near future. Until then, if you decide to use the CoMISo solver in your research, please use the Mixed-Integer Quadrangulation bibtex entry below to properly reference the solver.

@article{1531383,
 author = {Bommes, David and Zimmer, Henrik and Kobbelt, Leif},
 title = {Mixed-integer quadrangulation},
 journal = {ACM Trans. Graph.},
 volume = {28},
 number = {3},
 year = {2009},
 issn = {0730-0301},
 pages = {1--10},
 doi = {http://doi.acm.org/10.1145/1531326.1531383},
 publisher = {ACM},
 address = {New York, NY, USA},
}

Note: The CoMISo solver library is being released under the GPL license, for commercial use contact Henrik Zimmer or David Bommes.

This software package consists of

the CoMISo solver library and

an OpenFlipper demo plugin,

see the following sections for Installation and Usage tips.

Release

News [16 Nov. 2009]

Minor compability changes have taken place: Namespace changed to COMISO, MISolverDialog files renamed to have a "UI" at the end: MISolverDialogUI.

CoMISo Solver

2009-08-25 Initial Release

subversion: # svn co http://www.openflipper.org/svnrepo/CoMISo/trunk/CoMISo CoMISo

Username/Password: anonymous/anonymous

tar.gz package : CoMISo.tar.gz

Example OpenFlipper Plugin

2009-08-25 Initial Release

subversion: # svn co http://www.openflipper.org/svnrepo/CoMISo/trunk/Plugin-HarmonicExample Plugin-HarmonicExample

Username/Password: anonymous/anonymous

tar.gz package : Plugin-HarmonicExample.tar.gz

Installing

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
Boost C++ Libraries
LAPACK - Linear Algebra Package

Note your operating system might already provide easy-to-use-and-install, pre-built packages. For example Ubuntu based platforms can use

# apt-get install libgmm-dev libboost-dev libblas-dev libsuitesparse-dev

to get the necessary packages.

On Windows or Macintosh systems the corresponding packages usually need to be manually downloaded and installed.

Downloading

The Constrained Mixed-Integer Solver is available both as a tar.gz package

CoMISo.tar.gz

as well as via svn (anonymous/anonymous)

# svn co http://www.openflipper.org/svnrepo/CoMISo/trunk/CoMISo CoMISo

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 stand-alone package.

1) Building CoMISo stand-alone

Having extracted the packages into the your directory of choice (DIR), now enter the CoMISo subdirectory

# cd DIR/CoMISo

create a build directory

# make build

enter build directory

# cd build

configure cmake, create make files

# cmake ..
( alternatively use graphical interface: # cmake-gui .. , first click configure until nothing is red, then click generate )

build the library and the examples

# 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/

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/

Building the example OpenFlipper plugin - HarmonicExample-Plugin

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 HarmonicExample-Plugin.tar.gz to the OpenFlipper root

2) re-build OpenFlipper and the plugin is added/built automatically

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 to minimizing |Bx-b|²

1) The factored approach, B^TBx=B^Tb. Here one supplies a usually overdetermined m x (n+1) row-matrix (B|b) with the rows being the m linear equations of the system, b₀*x₀+...+b_n*x_n=b_n+1. The constraints are eliminated directly from the B matrix before B^TB is formed.

2) The quadratic approach, Ax=a . Here one supplies the n x n system matrix A=B^TB and the right hand-side a=B^Tb. 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^TB and the right hand-side 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.

Application Example - HarmonicExample-Plugin

The provided examples 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 OpenFlipper-Plugin: HarmonicExample-Plugin, is provided, showing

A) how to incorporate the external solver into the OpenFlipper environment and

B) a demo application utilizing the CoMISo solver.

The Plugin sets up a simple Laplace equation system on an input mesh (with boundaries).
To demonstrate the constraint-elimination, 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 iso-lines to pass through the selected vertex. Multiple/none or all vertices can be selected.

Feedback

We are grateful for feedback! Please send suggestions, patches, bug reports, questions and comments to Henrik Zimmer or David Bommes

[Home] [Top]

[Disclaimer]