A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers

详细信息    查看全文

• 关键词：Mixed integer programming ; Distributed memory parallelization
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9725
• 期：1
• 页码：308-316
• 全文大小：709 KB
• 参考文献：1.Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007)
  2.Achterberg, T., Wunderling, R.: Mixed integer programming: Analyzing 12 years of progress. In: Jünger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization - Festschrift for Martin Grötschel, pp. 449–481. Springer, Heidelberg (2013)CrossRef
  3.Bussieck, M.R., Ferris, M.C., Meeraus, A.: Grid-enabled optimization with GAMS. IJoC 21(3), 349–362 (2009)MathSciNet CrossRef MATH
  4.Eckstein, J., Hart, W.E., Phillips, C.A.: Pebbl: an object-oriented framework for scalable parallel branch and bound. Math. Program. Comput. 7(4), 429–469 (2015). http://​dx.​doi.​org/​10.​1007/​s12532-015-0087-1 MathSciNet CrossRef MATH
  5.FICO Xpress-Optimizer. http://​www.​fico.​com/​en/​Products/​DMTools/​xpress-overview/​Pages/​Xpress-Optimizer.​aspx
  6.Laundy, R., Perregaard, M., Tavares, G., Tipi, H., Vazacopoulos, A.: Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study. INFORMS J. Comput. 21(2), 304–313 (2009)MathSciNet CrossRef MATH
  7.Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization. Wiley, New York (1988)CrossRef MATH
  8.Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving hard MIPLIB2003 problems with ParaSCIP on supercomputers: An update. In: 2014 IEEE International Parallel Distributed Processing Symposium Workshops (IPDPSW), pp. 1552–1561, May 2014
  9.Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP - a parallel extension of SCIP. In: Bischof, C., Hegering, H.G., Nagel, W.E., Wittum, G. (eds.) Competence in High Performance Computing 2010, pp. 135–148. Springer, Heidelberg (2012)
  10.Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving open MIP instances with ParaSCIP on supercomputers using up to 80,000 cores. In: Proceedings of 30th IEEE International Parallel & Distributed Processing Symposium, to appear (2016)
  11.Shinano, Y., Achterberg, T., Fujie, T.: A dynamic load balancing mechanism for new ParaLEX. Proc. ICPADS 2008, 455–462 (2008)
  12.Shinano, Y., Heinz, S., Vigerske, S., Winkler, M.: FiberSCIP - a shared memory parallelization of SCIP. Technical Report ZR 13–55, Zuse Institute Berlin (2013)
  13.Sun, Y., Zheng, G., Jetley, P., Kalé, L.V.: ParSSSE: An adaptive parallel state space search engine. Parallel Process. Lett. 21(3), 319–338 (2011)MathSciNet CrossRef MATH
  14.Xu, Y., Ralphs, T.K., Ladányi, L., Saltzman, M.: Alps version 1.5.2 (2015)
  
• 作者单位：Yuji Shinano (17)
  Timo Berthold (18)
  Stefan Heinz (18)
  
  17. Zuse Institute Berlin, Berlin, Germany
  18. Fair Isaac Germany GmbH, Berlin, Germany
  
• 丛书名：Mathematical Software ¨C ICMS 2016
• ISBN：978-3-319-42432-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9725

文摘

The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. It has been used to develop ParaSCIP, a distributed memory, massively parallel version of the open source solver SCIP, running on up to 80,000 cores. In this paper, we present a first implementation of ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important difference between SCIP and Xpress is that Xpress provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show preliminary computational results for running a first version of ParaXpress on 6,144 cores in parallel.