Research Initiation: Parallel Computing and Mixed Integer Programming

研究发起：并行计算与混合整数规划

• 批准号: 9410102
• 负责人: Martin Savelsbergh
• 金额: $ 9万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-15 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9410102&HistoricalAwards=false
• 关键词: Research; Initiation; Parallel; Computing; Mixed

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.

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