Solvers

The built-in solvers differ only in how they represent and refine the polyblock representation. TreePOA is the default choice, while BasePOA and BalancedPOA are simpler flat-array implementations kept for reference and comparison.

polyblocks.tree

TreePOA(lower, upper, upper_obj)

Bases: ABPolyblock

An implementation of POA which stores polyblock vertices in a tree.

Rather than storing the current vertices V alone, this solver keeps the whole tree of refinements the search has produced, with V as its leaves. The representation is compressed: a cut replaces a vertex by copies differing from it in one component, so a node need only record the component its cut modified and that component's new value, with the root holding the initial upper point. A vertex is recovered by descending from the root and tracing these modifications at each node.

In return, each node bounds both the region and objective of its subtree, so a search can rule out the whole subtree without visiting its leaves. POA's searches over V thus become descents rather than scans:

• projection_pairs finds the maximal vertex by descending through the highest-objective child at each step, using descents on disjoint subtrees to return up to PROJECTED_VERTICES distinct leaves
• new_vertices collects the vertices above a projection by recursing from the root, entering a child only when its component clears the projection and its objective attribute clears the incumbent.
• best_bound is read off the root, whose objective attribute is the maximum over all vertices.

Under a positive delta the depth of the tree is bounded independently of how many vertices it holds, so a descent costs O(dim * depth) against the O(len(V)) of a flat array.

Pruned nodes are not removed eagerly, as repairing every index is expensive for large trees. Instead, their objective attributes are used to keep them out of both tree traversals for free. update rebuilds the tree every REBUILD_GAP updates, removing childless nodes and those which can no longer improve the incumbent.

Attributes:

Name	Type	Description
REBUILD_GAP	int	Number of updates between tree rebuilds, which prunes redundant nodes.
PROJECTED_VERTICES	int	Maximum number of vertices projected per iteration.

polyblocks.naive

BasePOA(lower, upper, upper_obj)

Bases: ABPolyblock

A naive implementation of POA which directly stores polyblock vertices in dynamic arrays.

BalancedPOA(lower, upper, upper_obj)

Bases: BasePOA

A variant of the naive POA implementation which uses balanced anchors.