Tabu search when noise is present: An illustration in the context of cause and effect analysis

In the field of combinatorial optimization, it may be possible to more accurately represent reality through stochastic models rather than deterministic ones. When randomness is present in a problem, algorithm designers face new difficulties which complicate their task significantly. Finding a proper mathematical formulation and a fast evaluation of the objective function are two major issues. In this paper we propose a new tabu search algorithm based on sampling and statistical tests. The algorithm is shown to perform well in a stochastic environment where the quality of feasible solutions cannot be computed easily. This new search principle is illustrated in the field of cause and effect analysis where the true cause of an undesirable effect needs to be eliminated. A set of n potential causes is identified and each of them is assumed to be the true cause with a given probability. The time to investigate a cause is a random variable with a known probability distribution. Associated with each cause is the reward obtained if the cause is really the true cause. The decision problem is to sequence the n potential causes so as to maximize the expected reward realized before a specified time horizon.