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

点击翻译按钮获取中文摘要

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.