Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld
Distributed solving of Mixed-Integer Programs with GLPK and Thrift
OR 2016 (Springer Verlag, pp. 599-605)
Abstract
| Branch-and-bound algorithms for Mixed-Integer Programs (MIP) are studied for over 40 years, see for example Achterberg, Koch, and Martin (2005), Benichou et al. (1971), or Linderoth and Savelsbergh (1999). Object-oriented frameworks for parallel branch-and-bound algorithms like ALPS (Xu, Ralphs, Ladányi, Saltzmann, 2005), ParaSCIP (Shinano, Achterberg, Berthold, Heinz, Koch, 2011), and PICO (Eckstein, Phillips, Hart, 2001) are well known. Our aim is to develop a powerful yet easy-to-use parallel MIP-solver by combining open-source tools or frameworks that are platform independent and free of charge so that even small companies come to the benefit of an optimization suite. Licences of commercial solvers like CPLEX or GUROBI are often not affordable for small companies. Our tool combines the Gnu Linear Programming Kit (GLPK) and the remote procedure call framework Thrift. To make our development independent of the GLPK-development, we use the GLPK-solvers as independently running processes. So we are able to profit from further development and algorithmic progress of GLPK in future. We describe how to combine these technologies to get an optimization suite for midsized problems and evaluate the power of our tool by solving some benchmark data from Chu and Beasley (1998) and MIPLIB 2003 (Achterberg, Koch, and Martin, 2003). |