Combinatorial optimization

[themmes]

Hi there, thanks for sharing this library, it seems potentially very useful for the problem I try to solve. First of I am not too sure if the library is actually made for this type of problem, but I assume it is.

I created a set of polygons based on bag of plane intersection.

Now I try to create the following manifold by combinatorial optimization.

The idea was to use python-constraint to generate possible solutions and select the best fitting by optimization of some weights on each polygon with scipy.optimize.

So far I came up with this:

import constraint
problem = constraint.Problem()
problem.addVariables(range(len(polygons)), [True, False])

for idx, polygon in enumerate(polygons):
    edge_adjacent_polygons = [polygon[a][b]['polygon'] for a, b in polygon.edges()]
    if all([len(adjacent_polygons) > 2 for adjacent_polygons in edge_adjacent_polygons]):
        for adjacent_polygons in edge_adjacent_polygons:
            problem.addConstraint(lambda *adjacent_polygons: sum(adjacent_polygons) == 2, adjacent_polygons)
    elif any([len(adjacent_polygons) == 2 for adjacent_polygons in edge_adjacent_polygons]) & \
        all([len(adjacent_polygons) >= 2 for adjacent_polygons in edge_adjacent_polygons]):
        problem.addConstraint(lambda idx: idx == True, [idx])
    else:
        problem.addConstraint(lambda idx: idx == False, [idx])

However, so far this generates 0 solutions in problem.getSolutions(). I suspect I have misunderstood how I could add the combinatorial constraints to the model. It is important polygons are chosen in such a way every edge is incident to two (and only two) polygons (polygon[a][b]['polygon'] points to a list of polygon ids the edge is incident to).

I really hope you can help me, I understand programming solvers like this is really hard and programming a custom one for my project seems beyond the scope. I think your solver is the only one that gets at least close to what I need to solve this.

Thanks in advance!