An Adaptive Algorithm for Solving the Axial Three-Index Assignment Problem

Abstract

In this paper, a probabilistic modification of the minimal element algorithm for solving the axial three-index assignment problem is suggested. Its general idea is to extend the basic greedy-type algorithmic schemes using transition to a probabilistic setup based on variables randomization. The minimization of an objective function is replaced by the minimization of its expectation. The algorithm is implemented in three stages as follows. At the first stage, a motion in the set of random variables is defined. At the second stage, an inequality that expresses the local improvement condition is solved. At the third stage, the probabilities are recalculated, which represents an “adaptation” process. The second stage reveals a feature of the algorithm: the resulting solution depends on the “qualities” of the element itself and also on possible losses of its choice.