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

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

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.