U.S.-France Cooperative Research: Highly Parallel Branch- and-Bound Algorithms for Solving Optimization Problems (with INRIA)

美法合作研究：解决优化问题的高度并行分支定界算法（与 INRIA 合作）

• 批准号: 9512014
• 负责人: Shantanu Dutt
• 金额: $ 2.7万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-03-01 至 2001-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9512014&HistoricalAwards=false
• 关键词: U.S.; France; Cooperative; Research; Highly

This three-year award will support U.S.-France cooperative research in numeric computation with researchers Shantanu Dutt, Vipin Kumar at the University of Minnesota and Catherine Roucairol at the Rocquencourt campus of INRIA (the French National Institute for Research in Computer Science and Applied Mathematics). The objectives of their research are to develop highly parallel branch-and-bound algorithms for solving combinatorial optimization problems (COPs) and software for optimization computations on parallel computers. Branch-and-bound algorithms are used widely in solving combinatorial optimization problems that appear in a variety of applications like computer vision, robot motion planning, and integer programming and computer-aided design of very large scale integrated circuits. These problems take a long time to solve. The U.S. investigators propose to develop time and memory efficient techniques for solving these problems using parallel processing. The U.S. investigators bring to this research their expertise in parallel computing and techniques for solving COPs using distributed memory machines and workstation clusters. This is complemented by the French investigator's expertise in operations research and her work on branch-and-bound algorithms techniques suitable for shared-memory multiprocessors.

这个为期三年的奖项将支持美法在数值计算方面的合作研究，合作研究人员包括明尼苏达大学的shanantanu Dutt、Vipin Kumar和法国国家计算机科学与应用数学研究所（INRIA） rocqucourt校区的Catherine Roucairol。他们的研究目标是开发用于解决组合优化问题（COPs）的高度并行分支定界算法和用于并行计算机上优化计算的软件。分支定界算法广泛用于解决组合优化问题，这些问题出现在计算机视觉、机器人运动规划、整数规划和超大规模集成电路的计算机辅助设计等各种应用中。这些问题需要很长时间才能解决。美国研究人员建议开发时间和内存效率的技术来解决这些问题，使用并行处理。美国研究人员将他们在并行计算和使用分布式内存机器和工作站集群解决cop问题的技术方面的专业知识带入了这项研究。此外，这位法国研究人员在运筹学方面的专业知识，以及她在适用于共享内存多处理器的分支定界算法技术方面的工作，也为她的研究提供了补充。