1

Problem

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

schermafbeelding 2018-10-11 om 16 50 39

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

schermafbeelding 2018-10-11 om 16 50 51

  • Manifold constraint each edge in the final model should be incident to two polygons.
  • Optimize weight each polygon has a confidence weight, the model should optimize towards highest overal confidence
  • Optimize simplicity Optimize towards less corners (more polygons in the same plane)

Attempt

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.

However, tried the following with python-constraint and it is not able to generate solutions.

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])

Other ideas I had were to model this as a graph optimization problem in NetworkX and using something like min_weighted_vertex_cover. Or using the jMetalPy library, however it is unclear to me how to model this problem in these approaches.

Question

I understand this problem combines non-linear optimization and a combinatorial satisfaction problem. My most important questions are;

  • is my approach correct or overcomplicated?
  • does a tool exist to model such a problem?

The original problem (and images) are from a paper I try to replicate https://repository.kaust.edu.sa/handle/10754/627151. In the paper the proprietary Gurobi solver is used. I cannot use this solver due to license.

Community
  • 1
  • 1
Tom Hemmes
  • 2,000
  • 2
  • 17
  • 23
  • Reading this answer https://stackoverflow.com/a/26314315/4925208, makes me feel like there exists no open source python MINLP solver. – Tom Hemmes Oct 15 '18 at 12:47
  • The paper states that they are using a plain linear MIP model (solved with Gurobi). In that case you don't need any MINLP functionality. – Erwin Kalvelagen Oct 15 '18 at 13:25
  • @ErwinKalvelagen thanks for correcting me there, that should make the search easier. Do you have suggestions for this problem? – Tom Hemmes Oct 16 '18 at 08:50
  • I would try to organize things such that it is easy to use different solvers. The performance of different MIP solvers on the same model can differ dramatically. – Erwin Kalvelagen Oct 16 '18 at 14:50

0 Answers0