3.7.206. Regret based heuristics

Assume you have a discrete optimisation problem where the sum of some cost variables should be minimised, and where the cost variables typically have holes in their domains. In this context a regret based heuristics first selects among the not yet fixed cost variables, the one with the largest difference between its second smallest value and its smallest value. The idea is to consider first a variable that would cause the biggest increase in cost if it could not be assigned its minimum value.