Abstract <p>This paper presents a parallel application software package for solving integer linear programming problems. The software is developed using a Master–Worker architecture and is intended for distributed-memory systems. A key feature of the package is a configuration-oriented approach to the branch-and-cut method. Each worker process that solves a part of a single branching tree is assigned a configuration that defines a set of parameters: the cut-generation method, the branching-variable selection strategy, the order of traversing the search tree, and the presence or absence of reductions. A subset of workers is allocated to evaluate the effectiveness of existing configurations and to compile their ranking. Test results demonstrate solution scalability. A comparative analysis with similar open-source solutions is provided.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Configuration-Adaptive Parallel Solver for Integer Programming Problems

  • M. A. Bezel,
  • A. Yu. Gorchakov,
  • D. S. Klyanchin

摘要

Abstract

This paper presents a parallel application software package for solving integer linear programming problems. The software is developed using a Master–Worker architecture and is intended for distributed-memory systems. A key feature of the package is a configuration-oriented approach to the branch-and-cut method. Each worker process that solves a part of a single branching tree is assigned a configuration that defines a set of parameters: the cut-generation method, the branching-variable selection strategy, the order of traversing the search tree, and the presence or absence of reductions. A subset of workers is allocated to evaluate the effectiveness of existing configurations and to compile their ranking. Test results demonstrate solution scalability. A comparative analysis with similar open-source solutions is provided.