TestAnt: An ant colony system approach to sequential testing under precedence constraints

We consider the problem of minimum cost sequential testing (diagnosis) of a series (or parallel) system under precedence constraints. We model the problem as a nonlinear integer program. We develop and implement an ant colony algorithm for the problem. We demonstrate the performance of this algorithm for special type of instances for which the optimal solutions can be found in polynomial time. In addition, we compare the performance of the ant colony algorithm with a branch and bound algorithm for randomly generated general instances of the problem. The ant colony algorithm is particularly effective as the problem size gets larger.

► The sequential testing of a series system under precedence constraints is considered.
► A nonlinear integer model is provided.
► An ant colony algorithm is developed to solve the problem.
► A branch and bound algorithm is developed to obtain exact optimal solutions.
► The performance of the ant colony algorithm is demonstrated through randomly generated instances.