FATCOP: A Fault Tolerant Condor-PVM Mixed Integer Programming Solver

Abstract

We describe FATCOP, a new parallel mixed integer program solver written in PVM. The implementation uses the Condor resource management system to provide a virtual machine composed of otherwise idle computers. The solver di ers from previous parallel branch-and-bound codes by implementing a general purpose parallel mixed integer pro- gramming algorithm in an opportunistic multiple processor environment, as opposed to a conventional dedicated environment. It shows how to make e ective use of resources as they become available while ensuring the program tolerates resource retreat. The solver performs well on test problems arising from real applications, and is particularly useful for solving long-running hard mixed integer programming problems.