Fix Tabu Local Searches in max-p

renanxcortes commented 4 years ago

Hello, everyone,

After digging deep into the code (by studying it and adding several print statements) to check what was happening, I managed to understand how each class is linked to each other.

This PR addresses directly https://github.com/pysal/region/issues/32 and https://github.com/pysal/region/issues/31 and fixes both issues.

So, the bugs were happening in the AZPBasicTabu and AZPReactiveTabu and are divided in two: "spatial constraints" and "threshold constraints". I explain here each solution:

Spatial constraints:

modification of assert_feasible (inside util.py) which was not testing appropriately contiguity for initial labels.
creation of boolean_assert_feasible to check spatial feasibility and returning a boolean value for internal usage.
tweak function _make_move from AZPTabu ensuring that the move will not break spatial contiguity (if it brakes, the move is reverted). It now uses the adj argument.

Threshold constraints:

both AZPBasicTabu and AZPReactiveTabu were not taking into consideration the "AllowMove" classes built in azp_util.py. A very important class, which is AllowMoveAZPMaxPRegions that tests for the limit of the threshold were not being used. However, now this was included in the AZPBasicTabu and AZPReactiveTabu inside each _azp_connected_component (you can see that the AZP class uses these classes).
with the previous fix, whenever a new move is meant to be made (with _make_move) this condition (with self.allow_move_strategy) needs to be checked.

Some extra comments:

With these tweaks, Step 3 of AZPBasicTabu can fall into an infinite loop (like in other parts of region). In region, this is solved with an argument stop given by reps_before_termination. Therefore, an additional "if stop brake" statement was added in this step.
I'd like to highlight that the AZPSimulatedAnnealing and default AZP approaches were ok and were not generating unusual results as I was suspecting.
It is possible that the performance will be reduced (only for AZPBasicTabu and AZPReactiveTabu) since now whenever _make_move is called, it checks for spatial contiguity of the regions.

Final comment:

After these fixes, I tried many scenarios and I didn't run into any weird solution. Therefore, I want to work with the Philosophy "Everyone is innocent until proven guilty". That is, I believe that max-p generates feasible solutions and it is innocent now unless someone raises an actual reproducible example with code with any of the issues that this PR attempts to solve. In this case, I'd be happy to help to try to solve it.

Best, Renan

renanxcortes commented 4 years ago

The last commit pushes a notebook (https://github.com/renanxcortes/region/blob/allow_strategy_inside_TabuClasses/region/notebooks/debug_code_MULTIPLE_TESTS.ipynb) showing that the approaches respect both issues in many different random selections and, therefore, reinforcing that these issues are fixed. I performed the tests in parallel.

This notebook can be deleted either in this PR before merging it or later.

sjsrey commented 4 years ago

Excellent work nailing these fixes!

pysal / region