Nowadays, pretty much every computer is capable of parallel processing, i.e., it has multiple CPU cores. My personal laptop has eight of them, my working server 20, even my smartphone is a four-core device. The biggest computers that we can think of are “super-computers”, which feature some hundreds of thousands of CPUs. There is an important difference, however, between super-computers and “standard” parallel computers: The former are so-called distributed memory devices, the latter usually have shared memory. In a shared-memory device, all parallel threads have direct access to one single (shared) RAM memory, providing each thread the same view of data at all times. In distributed memory systems, in which individual computing nodes are connected via network cables, this is not the case. Or is it?
As a matter of fact, in modern super-computers, each individual computing node is itself a shared memory, multi-core system – embedded in a much larger distributed memory network. This observation brought together some of the leading expert teams in parallelization of optimization software. The group of Professor Dr. Yuji Shinano at Zuse Institute Berlin has been leading the field of Mixed-Integer Programming (MIP) solving on super-computers for the last few years. They developed the so-called UG framework for external parallelization of MIP solvers, which so far they used together with the open source solver SCIP. On the other hand, the developer team of the FICO Xpress Optimizer has recently presented an innovative way of parallelizing MIP solvers, which has led to tremendous improvements in the scalability of the recently released version 8.0 of the FICO Xpress Optimizer.
The joint scientific project on “ParaXpress” that takes place within the research campus MODAL in Berlin, aims at bringing together the power of external parallelization on distributed systems and internal parallelization on shared memory systems. At the International Congress on Mathematical Software 2016, Dr. Berthold from FICO presented how the new parallelization of the Xpress Optimizer can solve hard MIP problems twice as fast. Prof. Shinano from ZIB showed that combining Xpress’ internal parallelization with UG’s external parallelization enables us to solve some of the world’s hardest MIP problems on thousands of CPUs within a few minutes. ParaXpress is an academic research project that has just taken its first steps. In the near future, we aim at harvesting the power of hundreds of thousands of CPUs on one of the world’s largest supercomputers to solve previously unsolved MIP problems from the MIPLIB challenge set.
Timo Berthold is one of the main developers of the FICO Xpress Optimizer. He is a leading expert in computational mixed integer programming and has published more than forty scientific papers in this field.