Ubiquity Generator framework

Second International UG Workshop 2021

Workshop on Parallel Algorithms in Tree Search and Mathematical Optimization

Date: October 1, 2021
Place: Zuse Institute Berlin, Germany
Organizer: Zuse Institute Berlin

Right before this workshop, the 5th ZIB-RIKEN-IMI-ISM MODAL Workshop on Optimization, Data Analysis and HPC in AI is taking place.


23. August 2021

For late registration requests please send a mail to schloesser at Participation is free of charge.

28. July 2021 First draft of schedule online.
16. February 2021 Announcement of the Second International UG Workshop 2021.


Click on the talk titles to display abstracts.

Friday, October 1

Time Place Speaker Detailed Information
09:00 Yuji Shinano

UG Version 1.0

Ubiquity Generator (UG) framework has been developed over 10 years as beta versions always. One reason is that the UG should generalize enough to parallelize many solvers before it has the major version. We have developed a generalized UG as the UG version 1.0. UG is redefined as a high-level task parallelization framework since it is not only for Branch-and-bound based solvers. In this talk, we will present success stories of parallel solvers instantiated by the UG and what comes with the generalized UG. We are planning to include UG version 1.0 in SCIP Optimization Suite 8.0.

10:00 Coffeebreak
10:15 Nariaki Tateiwa

Configurable Massively Parallel Solver for Lattice Problems

Lattices are useful to construct various cryptographic systems, including post-quantum cryptography. The security of lattice-based cryptography relies on the hardness of the shortest vector problem (SVP). Currently, SVP is considered to be computationally hard for both classical and quantum computers. In this talk, I introduce a flexible framework CMAP-LAP to solve SVP based on a generalized UG. We develop CMAP-LAP to interact with various algorithms for SVP, which works on a large-scale distributed system. We also implement powerful checkpoint-and-restart functionality, which is vital to SVPs since they require millions of core hours. We explain the extended features of CMAP-LAP based on the generalized UG and evaluate the performance of our solver via numerical experiments on the large-scale computer.

11:00 Koichi Fujii

ParaQapNB : Massively Parallelized DNN-based Branch-and-bound QAP solver

We report our progress on the project for solving large scale quadratic assignment problems (QAPs). Our main approach to solve QAPs is a parallel branch-and-bound method. Combining with Ubiquity Generator framework (UG), our QAP solver can run effectively in massively parallel environments.

Our QAP solver is different from general MIP branch-and-bound solver on some points. It takes more time to solve each node, generate more than 2 nodes at branching, and so on. Since UG has focused on scaling general MIP solver, we need to add some features to UG such as self-splitting ramp-up or heavy checkpointing.

In this talk, we describe their details and present some preliminary numerical results including QAPLIB open instances tai30a and sko42, which we solved for the first time.

11:45 Coffeebreak
12:00 Yuji Shinano

Progress in parallel MIP solvers instantiated by UG

In this talk, we will present the latest status of ParaSCIP, FiberSCIP, and ParaXpress which are parallel MIP solvers instantiated by the generalized UG, and what is coming with UG version 1.0.

12:45 Daniel Rehfeldt

ug[SCIP-Jack,*]: A parallel solver for Steiner tree and related problems

The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization and computer science. The current state-of-the-art solver for SPG (and several related problems) is SCIP-Jack. This talk discusses key components of SCIP-Jack, with a focus on the latest algorithmic developments. Furthermore, the parallelization of SCIP-Jack by means of the UG framework is disscussed. Finally, we provide recent computational results, both for the sequential and parallel versions of SCIP-Jack.

13:30 Lunchbreak
14:30 Stephen J. Maher

Large-scale parallelisation for the Benders' decomposition framework in SCIP

Parallel computing is commonly used to "speed-up" the Benders' decomposition algorithm. While the traditional application of parallel computing for Benders' decomposition involves concurrently solving cut generating subproblems, this can introduce significant overhead and idle time when encountering difficult master problems. This limitation can be overcome by parallelising the tree search when employing the branch-and-cut version of the Benders' decomposition algorithm. However, the limited availability of general Benders' decomposition frameworks makes such parallel algorithms ad hoc. The UG framework provides a valuable opportunity to parallelise the tree-search when employing the Benders' decomposition framework that is available in SCIP. This talk will discuss the current challenges and aims in combining shared and distributed memory parallisation when deploying the Benders' decomposition algorithm.

15:00 Utz Uwe Haus

ParaConcorde – a status update

With UG 1.0 offering general-purpose infrastructure to build distributed solvers around problem-specific subsolvers we are presenting an overview of our HPC TSP solver project, ParaConcorde. It is based on the well-known Concorde TSP solver, ported to use MPI for internal communication. Given that parallel Concorde scaling quickly is limited by the number of subproblems solved (which is actually a feature in successful TSP solvers) we are proposing to embed this Concorde/MPI into the UG framework to create an environment in which many differently parameterized subsolvers cooperate (and compete). Each subsolver can be run on a differently sized subsets of the available nodes according to subproblem difficulty, and can be preempted by UG in a global B&B strategy.(joint work with Y. Shinano)

15:45 Coffeebreak
16:00 Ted Ralphs

Duality and Meaning in (Parallel) Computation

In this talk, we discuss notions of duality arising in algorithms for discrete optimization and explore how such notions are related. We then describe how these notions can be exploited to better interpret the results of computations and discuss the implications for parallelization of algorithms. The specific applications we have in mind are explainability in discrete optimization, automated theorem proving, and machine learning, but the concepts apply more broadly.

16:45 Tim Hasler

Tales from the workbench of the HPO Navi project

In the HPO Navi project we aimed on providing the development of research software with a more structured framework. To this end we envisioned a workflow from the development area in a git repository over the publication in the institutional repository up to the software homepage and finally to the long term archive. We strictly used free and open source tools prevalent in the community to enable others to implement an at least similar workflow. In this talk we will present some of the results and point out to particular worthy problems we encountered.


About the UG Workshop

We are happy to announce our upcoming UG Workshop on October 1, 2021.

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.

This workshop has several goals:

  • 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.


The workshop will be mixed format between online and in-person events. The latter will take place at Zuse Institute Berlin, Takustr 7, 14195 Berlin - Steglitz-Zehlendorf

Accommodation And Travel Information

You can find some travel and accomodation hints on the ZIB Contact page or here (search for districts "Zehlendorf" and "Steglitz" for nearby locations).


The workshop is organized by Yuji Shinano and Franziska Schlösser

Previous Workshop

First International UG Workshop 2019


This research has been supported by the German Research Foundation (DFG) within the project HPO-NAVI:
Nachhaltige Archivierungs- und Veröffentlichungs-Infrastrukturen für High Performance Optimization (ID 391087700).

The core development of the UG framework is conducted as part of the Research Campus MODAL funded by the German Federal Ministry of Education and Research (BMBF grant numbers 05M14ZAM, 05M20ZBM).