Parascip tree

First International UG Workshop 14-16 January 2019:

The Ubiquity Generator (UG) is a generic framework for parallelizing branch-and-bound-based solvers. It has been used to create high-performance parallelizations of the mixed-integer programming solver SCIP, CPLEX (deprecated), Xpress, NUOPT, and the two-stage mixed integer stochastic programming solver PIPS-SBB. In the framework, the solvers are abstracted as a base solver. The SCIP Optimization Suite contains the UG parallelizations of SCIP for both shared and distributed memory computing environments, namely FiberSCIP and ParaSCIP.

The capability and flexibility of UG has been demonstrated on several occasions. The biggest computation conducted with ParaSCIP so far has harnessed 80,000 cores on the supercomputer TITAN at Oak Ridge National Laboratory. The results showed the capability of UG to handle up to 80,000 MPI (Message Passing Interface) processes. A UG parallelization of Xpress demonstrated that UG can parallelize multi-threaded base solvers, and the UG parallelization of PIPS-SBB proved that UG can parallelize distributed-memory base solvers. Both solvers have the potential to use over a million CPU cores to solve a single instance in a hybrid parallelization scheme combining UG and base solver parallelization.

The framework architecture allows the parallelization of any branch-and-bound code, but usually requires some extension of the base solver. However, if a parallel solver for a specific problem is developed within the SCIP by adding user-defined plugins, the customized SCIP solver can be parallelized with minimal efforts. Two of the most successful problem-specific parallelizations are SCIP-Jack, a solver for the Steiner tree problem in graphs and its variants, and SCIP-SDP, a solver for mixed-integer semi-definite programming.


The goals of this workshop:

  • showcase current applications of UG,
  • collect feedback from current and potential users on requirements for future features,
  • give hands-on tutorials on how to use the UG framework to parallelize your own branch-and-bound code and how to improve its performance.

More generally, we wish to

  • discuss open questions at the interface of high-performance computing and tree search algorithms, as well as
  • discuss challenges and best practices for sustainably developing, distributing, and maintaining research software.

In this sense, the workshop is also open to a wider audience of researchers and software developers working in this area.


Submission and Registration:

If you want to attend the workshop, please write to by November 30, 2018, and let us know if you are planning to give a talk.


Please visit the workshop homepage for more information.