First International UG Workshop 2019

Workshop on Parallel Algorithms in Tree Search and Mathematical Optimization

Date: January 14 - 16, 2019
Place: Zuse Institute Berlin, Germany
Organizer: Zuse Institute Berlin

News

23. October 2018 Please also notice the related follow-up workshop on High-Performance Business Computing also held at ZIB.
8. November 2018 The preliminary list of speakers includes: Jonathan Eckstein, Tristan Gally, Kibaek Kim, Ted Ralphs, Daniel Rehfeldt, Yuji Shinano and Jean-Paul Watson

About the UG Workshop

We are happy to announce our upcoming UG Workshop from January 14 to 16, 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.

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.

Registration

The workshop will take place at ZIB-Hörsaal, Takustr 7, 14195 Berlin - Steglitz-Zehlendorf

No registration fees apply but travel expenses need to be covered by participants.

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

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

Organizers

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