Research Initiation: Parallel Computing and Mixed Integer Programming

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

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.