A random search algorithm intended to solve discrete optimization problems is considered. We outline the main components of the algorithm, and then describe it in more detail. We show how the algorithm can be implemented on parallel computer systems. A performance analysis of both serial and parallel versions of the algorithm is given, and related results of solving test problems are discussed.