Research Initiation: Parallel Computing and Mixed Integer Programming

9410102 Savelsbergh 这项研究的重点是开发一个环境，用于实现基于并行线性规划的混合整数规划分支定界算法。 在此环境中，特别关注分支剪切算法和分支价格算法。分支定界算法和分支定界算法是基于线性规划的分支定界算法的变体。 研究涵盖的主题包括重构、分解、行和列生成、行和列管理、分支、并行架构、细粒度和粗粒度并行、任务分配、通信和同步。 将开发模块化实验代码来测试和评估研究中开发的方法。 开发用于实现混合整数规划的基于分支定界算法的并行线性规划的环境将有助于更好地理解并行计算在数学规划中的适用性。 研究成果还将为针对物流和制造中某些类别的问题实施专用算法提供机会。

9410102 Savelsbergh This research is focused on the development of an environment for the implementation of parallel linear programming based branch- and-bound algorithms for mixed integer programs. Within this environment, special attention is given to branch-and-cut and branch-and-price algorithms. Branch-and-cut and branch-and-price are variants of linear programming based branch-and-bound algorithms. Topics covered in the research include reformulation, decomposition, row and column generation, row and column management, branching, parallel architecture, fine and coarse grain parallelism, task allocation, communication, and synchronization. Modular experimental codes will be developed to test and evaluate the methodologies developed in the research. The development of an environment for implementing parallel linear program based branch-and-bound algorithm for mixed integer programming will result in a better understanding of the applicability of parallel computing for mathematical programming. The research outcome will also open up opportunities for the implementation of special purpose algorithms for certain classes of problems in logistics and manufacturing.