header

CoMISo - Constrained Mixed-Integer Solver

CoMISo - 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 University, which emerged from our Mixed-Integer 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, 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.

If you decide to use the CoMISo solver in your research, please cite the accompanying publication Practical Mixed-Integer 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 us.

Features (NEW Version 1.1!)

  • Less Dependencies! Only two header libraries needed for using the constrained mixed-integer solver (GMM++ and Eigen3)

  • Efficient re-solve of constrained systems! Re-solve constrained system using updated (system and/or constraint) right hand sides!

  • /NSolver -- simple non-linear solver c++ interfaces for:

  • /EigenSolver -- interface for large-scale eigenvalue problems ARPACK

  • /Solver -- several interfaces for common linear system solvers:

    • sparse Cholesky (Cholmod, LDLT), SpareQR, TAUCS, UMFPACK and of course the interfaces for Constrained and Constrained Mixed-Integer Problems -- CoMISo!

History

19-07-2013 : Due to popular demand, we now supply Build Instructions for Windows

16-11-2012 : Major Update: Version 1.1 (more features, less dependencies)

16-11-2010 : COMISO - Updated Release (new features, performance increase)

16-11-2010 : HarmonicExample-Plugin - Minor Update (Namespace COMISO_GMM)

19-05-2010 : Minor Memory Leak fixed in CholmodSolver.cc. Thanks Ashish Myles.

Download

The Constrained Mixed-Integer Solver as well as the exemplary OpenFlipper Plugin are available via GIT server:

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 easy-to-use-and-install, pre-built packages. For example Ubuntu based platforms can use

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

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.

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), 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 |Bx-b|2

1) The factored approach, BTBx=BTb.

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, b0x0+...+bnxn=bn+1. The constraints are eliminated directly from the B_ matrix before BTB is formed.

2) The quadratic approach, Ax=a.

Here one supplies the n x n system matrix A=BTB and the right hand-side a=BTb. 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 BTB 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.

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

  1. how to incorporate the external solver into the OpenFlipper environment and
  2. 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 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.

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

Feedback

We are grateful for feedback! Please send suggestions, patches, bug reports, questions and comments to us.

footer
Disclaimer Home Visual Computing institute RWTH Aachen University