Open stepankonrad opened 5 years ago
Hi @stepankonrad,
thanks for contributing! You're absolutely right, a 0-objective would cause a 0-division - shame on me :/ Good point about negative costs. Though I always assumed costs are nonnegative, in general I see no issues with actually using negative costs...
On the modelling side, the best possible solution is adding a bias pushing the global minimum to 0 or above. Otherwise, there's all sorts of stuff that could go wrong (think sequences 20 -> 10 -> 0 -> -10 -> -20 or 10 -> -10). After considering some cases, I would propose the following to stick as close as possible to the previous meaning of the termination criterion: let's use the following:
/* avoid nondecreasing objective */
if(newest_val >= oldest_val)
return true;
/* in order to support negative costs, handle the magnitudes only */
const _s_t<COSTTYPE, SIMDWIDTH> max_val = std::max(
oldest_val, newest_val);
const _s_t<COSTTYPE, SIMDWIDTH> min_val = std::min(
oldest_val, newest_val);
/* avoid 0-division when objective stays constant */
const _s_t<COSTTYPE, SIMDWIDTH> improv =
(max_val - min_val) / (static_cast<_s_t<COSTTYPE, SIMDWIDTH>(0.5) *
(std::abs(max_val) + std::abs(min_val)));
return (improv < m_improv_threshold);
This would gracefully handle negative costs by biasing the expected loss the average. Does it solve you problem?
Hi @dthuerck, this happens for example if the graph doesn't have any edges. Is this the right way to terminate? Can the cost go below 0? Best, Stepan