1

问题

我创建了一组基于平面相交袋的多边形。

schermafbeelding 2018-10-11 om 16 50 39

现在我尝试通过组合优化创建以下流形。

schermafbeelding 2018-10-11 om 16 50 51

  • 流形约束最终模型中的每条边都应与两个多边形相关。
  • 优化权重每个多边形都有一个置信权重，模型应该优化到最高的总体置信度
  • 优化简单性向更少的角落优化（同一平面上的更多多边形）

试图

这个想法是用来python-constraint生成可能的解决方案，并通过优化每个多边形上的一些权重来选择最佳拟合scipy.optimize。

但是，尝试了以下操作，python-constraint但无法生成解决方案。

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

我的其他想法是将其建模为 NetworkX 中的图形优化问题，并使用类似min_weighted_vertex_cover. 或者使用 jMetalPy 库，但是我不清楚如何在这些方法中对这个问题进行建模。

问题

我理解这个问题结合了非线性优化和组合满意度问题。我最重要的问题是；

  • 我的方法是正确的还是过于复杂？
  • 是否存在对此类问题进行建模的工具？

最初的问题（和图像）来自我尝试复制的一篇论文https://repository.kaust.edu.sa/handle/10754/627151。在本文中，使用了专有的 Gurobi 求解器。由于许可证，我无法使用此求解器。

4

0 回答 0