TeamAmalgam/kodkod — pull request #40 by mhyee (2013-07-23 20:48:40+00:00)
Title: Implement PartitionedGuidedImprovementAlgorithm

This pull request fixes #32.

* Boundary finding is included and the boundary constraints are used
* Partitions are split only at the first Pareto point
* There is no recursive splitting
* This works for any number of objectives
* Single-objective problems are special-cased
* Threads are managed by a ThreadPoolExecutor
* Tasks are created up front, but only submitted to the thread pool if all their dependencies have been met

Issues open for discussion:
* Currently the algorithm is hard-coded to PGIA. I haven't actually tested this beyond a handful of models. I plan on running these through our performance workers, after a bit of refactoring and cleanup.
* The boundary finding seems to help in some cases, but most of the time it hurts. I'm leaving it in for now so it's easier to merge in #29. Also, #29 might actually outweigh the overhead, in which case we'll keep it.
* There is no recursive splitting. Only the first Pareto point is used to split the space. More splitting might improve performance, but might also add overhead because of the number of tasks. Adding this would require significant changes, so I want to merge this in first before even attempting that.

I don't intend to merge this in right away. I still have some refactoring and cleanup I want to do (which I'll document here), and some tests I want to run. However, I'm sending this pull request now so people can start looking over it.

In particular, when reviewing, please look out for any concurrency issues, and how the dependencies and scheduling are implemented.

Reviewers: @AtulanZaman @cpkleynhans @joseph2625