This fixes issues #628, #516, #461, #418, #280.

This also adds more consistency with the heuristic version of the code.