  The article presents and evaluates a scalable algorithm for validating
solutions of linear programming problems on cluster computing systems. The main
idea of the method is to generate a regular set of points (validation set) on a
small-radius hypersphere centered at the point of the solution under
validation. The objective function is calculated for each point of the
validation set that belongs to the feasible region. If all these values are
less than or equal to the value of the objective function at the point under
validation, then this point is the correct solution. The parallel
implementation of the VaLiPro algorithm is performed in C++ through the
parallel BSF-skeleton, which encapsulates all aspects related to the MPI-based
parallelization of the program. We provide the results of large-scale
computational experiments on a cluster computing system to study the
scalability of the VaLiPro algorithm.
