Research Initiation: Parallel Computing and Mixed Integer Programming

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

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.