Optapy solution stuck

[jonpsy]

Hey community, I'm trying to setup a label assignment. A collection of polygons were grouped into a cluster initially. I apply some soft constraint, but importantly, a hard constraint such that at any point, union of polygons of a cluster should never be a multipolygon (disconnected)

I've went ahead and took ClusterLabel as a problem fact and Polygon as a planning entity.

class Polygon:
      @problem_fact
      cluster_label: ClusterLabel
      geometry: shapely.geometry

#constraints.py 

def valid_polygon(constraint_factory):
     return constraint_factory.for_each(Polygon)\
             .groupby(lambda raw_polygon: raw_polygon.cluster_label.label,
                     ConstraintCollector.to_list(lambda raw_polygon: raw_polygon.geometry)\
              .filter(lambda _, geometry: unary_union(geometry) == MultiPolygon) \
              .penalize(...)

This works but scales horribly. On real life dataset the hard penalty NEVER decreases even after 1 hour. Is there a better approach?

[jonpsy]

Is it because of the ConstraintCollector.to_list which is making it "slow", I don't think that's the issue.... but neverthless it shouldn't be stuck? Or is it perhaps the moves?

[Christopher-Chianelli]

I suspect the main scaling issue has to do with ConstraintCollector.to_list; when ConstraintCollector.to_list is used, OptaPy/OptaPlanner cannot perform incremental score calculation on the collected elements, which massively degrade the performance. As an example, if you use to_list on a list of numbers and then sum them, the to_list approach would be multiple times slower than ConstraintCollectors.sum since it need to readd all the number each time (whereas sum only does the difference).

The way to fix it is to use a Custom ConstraintCollector (which in your case, would implement unary_union in an incremental way), which is not currently supported in OptaPy.

Moves can also have a major performance impact, but it hard to tell without benchmarking (and OptaPy doesn't support custom moves yet).

What is the score calculation speed reported by the solver? Ideally it should be above 1000 score calculations/sec (the higher the better).

[jonpsy]

best score (-5hard/0soft), score calculation speed (7/sec) I got this

[jonpsy]

But I get score calculation speed as 5/sec even when I use a very trivial groupby => sum => penalize soft constraint. So I doubt that's the issue? Note: Soft constraint value was decreasing over time. But the hard constraint was stuck forever

[Christopher-Chianelli]

Then it is definitely the performance of the constraints that is causing the issue. 7/sec is extremely low. You need to rewrite your constraints to improve performance. Looking at shapely, it appears to be a C library. Ironically for OptaPy, this is extremely bad, since it need to do many transfers between Java -> CPython -> C and C -> CPython -> Java per score calculation. With pure Python code, we can translate all the constraints into Java (and thus do not incur a transfer cost). Unfortunately, the transfer cost is extremely large (it makes constraints 100 times slower). To improve speed, do @constraint_provider(function_bytecode_translation=BytecodeTranslation.NONE) on your constraint provider (which change it from many transfers to 1 transfer, which should be faster, but still significantly slower than pure Java)