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 zib.de. Participation is free of charge.
|28. July 2021||First draft of schedule online.|
|16. February 2021||Announcement of the Second International UG Workshop 2021.|
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.
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.
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.
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.
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.
|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)
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.
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.
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:
More generally, we wish to
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