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.
翻译:文章提出并评估了用于验证集束计算系统线性编程问题解决方案的可缩放算法。 方法的主要理念是生成一组常规点( 校验集), 以位于正在验证的解决方案点的小型半射线超光谱为核心。 目标函数是针对属于可行区域的验证集的每个点计算的。 如果所有这些值都低于或等于所验证点的客观函数值, 那么这个点就是正确的解决办法。 VaLiPro算法的平行实施通过平行的 BSF- skeleton 在C++ 中进行, 包含与程序基于 MPI 的平行化相关的所有方面。 我们提供了一组计算系统中大规模计算实验的结果, 以研究VaLiPro算法的可扩展性。