BIP solver for homogenization does not scale well

[fredericpoitevin]

The function bip_ilp uses the GNU Linear Programming Kit library implemented in cvxopt to solve the constrained optimization problem of minimizing the amount of elements discarded from a binary matrix A.

In our case, A is typically of size number of atoms m times number of structures n, resulting in a set of m*n constraints (one for each element, roughly) making the problem scale as (m*n)**2, despite very sparse matrices.

The limit of this is hit very fast, several options need to be investigated:

• implement the binary integer program from scratch, taking advantage of the sparsity of the constraints
• use a completely different approach, such as hierarchical clustering of A.
• applying the BIP to hierarchical subsets, for example the chains first, then for each chain the residues, and finally the atoms within residues