Research Initiation: Parallel Computing and Mixed Integer Programming

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

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.