UG
Ubiquity Generator framework
Ubiquity Generator framework
Date: January 14 - 16, 2019
Place: Zuse Institute Berlin, Germany
Organizer: Zuse Institute Berlin
| 16. January 2019 | Last day of the workshop. |
| 14. January 2019 | Beginning of the workshop. |
| 03. January 2019 | Finalization of schedule. |
| 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 |
| 07. December 2018 | The preliminary schedule is now online. |
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:
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 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.
Foto by F. Schlösser
| Time | Place | Speaker | Detailed Information | |
|---|---|---|---|---|
| 09:30 | LH |
Ambros Gleixner Yuji Shinano | Opening | |
| 09:40 | LH | Yuji Shinano |
Ubiquity Generator (UG) Framework: Introduction
The Ubiquity Generator (UG) Framework is a software framework to parallelize existing state-of-the-art branch-and-bound based solvers.
In this talk, the development history of UG, the concept behind the framework, basic features and how UG works are presented.
On top of that some UG related software will be introduced, such as the UG synthesizer (UGS) and ug[SCIP,*] which are plugin based software libraries for general purpose parallel branch-and-bound.
| slides |
| 10:30 | Foyer | Coffeebreak | ||
| 10:50 | LH | Ice Breaker | ||
| 11:20 | LH | Ted Ralphs |
Assessing Effectiveness of (Parallel) Branch-and-bound Algorithms
This talk focuses both on the challenges of achieving good performance when parallelizing an MILP solver and on the challenges of assessing that performance. Performance measurement for parallel solvers presents many challenges, especially since parallel solvers must be assessed both on their raw performance and on their scalability. We describe the challenges associated with performing "traditional" analyses for both scalability and performance, including that of choosing an appropriate test
set. This is particularly difficult in the case of parallel MILP both because solvers may have much different strengths and because we typically require instances to be solvable on a single core, which may be unrealistic. We focus on methods by which solvers with disparate capabilities can still be compared in terms of scalability and performance, as well as on methods by which unsolvable instances can still be incorporated into test sets. We also propose some new methods of assessing
scalability and visualizing computational comparison data.
| |
| 12:30 | Foyer | Group photo | ||
| 12:40 | Campus | Lunch | ||
| 14:30 | LH | Tristan Gally |
Parallelizing SCIP-SDP via the UG framework
SCIP-SDP is a plugin for SCIP to extend it to mixed-integer semidefinite programming (MISDP) and is currently one of the fastest solvers for MISDP, which has applications in, e.g., combinatorial optimization, mechanical engineering, statistics, and optimal power flow. SCIP-SDP supports two types of algorithms for solving MISDPs, a nonlinear branch-and-bound approach and an LP-based cutting plane approach. Apart from allowing to distribute the branch-and-bound tree among different solver instances, the parallelization via the UG framework also allows to dynamically choose between both algorithms during the racing ramp-up phase. During this talk, we will introduce mixed-integer semidefinite programming and compare the different solution approaches implemented in SCIP-SDP before discussing the parallelization and presenting numerical results demonstrating its success.
| slides |
| 15:15 | LH | Timotej Hrga |
Parallel Branch and Bound Algorithm for the Stable Set problem
Over the past decades a vast number of algorithms have been proposed to solve problems in combinatorial optimization either approximately or up to optimality. But despite the availability of high-performance infrastructure in recent years only a small number of these algorithms have been considered from the standpoint of parallel computation. We present a method for solving specific NP-hard combinatorial optimization problem that combines techniques from semidefinite optimization and efficient implementation using high performance computing. We will review the most important aspects of the Branch-and-Bound scheme and present a method for finding exact solutions of Stable Set problem, the problem of finding the independent set in the graph with the maximum cardinality. We use parallel Branch-and-Bound algorithm that applies Lovász theta function as upper bound to efficiently approximate original problem using semidefinite relaxation. Depending on the sparsity of the graph combination of two SDP solvers is used to compute solutions of the obtained relaxations. The result is the new open-source highperformance solver BiqBin. We will present numerical experience with the proposed algorithm and show scalability and efficiency of it.
| |
| 16:00 | Foyer | Coffeebreak | ||
| 16:30 | LH | Yasumi Ishibashi |
ParaNUOPT:Parallelization of NUOPT using UG
The current processor has multiple processor cores for performance improvement and power saving. Also with the advent of cloud computing service, it is possible to easily create a many-core environment. In response to such changes in the environment, We need to develop high speed parallel MIP solver. In this talk I report performance evaluation of parallelization of NUOPT using UG on AWS.
| |
| 17:00 | LH | Utz-Uwe Haus |
Using distributed solvers in UG
We discuss challenges of using solvers that are using distributed computation themselves inside the UG distributed parallelization framework. A proposal for dynamic resource allocation by UG and experiences in using that to run multiple MPI-parallelized Concorde solvers will be presented.
| slides |
| 19:30 | Dinner in the city centre; Restaurant Nolle at S-Bahnstation Friedrichstraße. We meet at 18:25 in the foyer at ZIB and go by public transport. |
| Time | Place | Speaker | Detailed Information | |
|---|---|---|---|---|
| 09:30 | LH | Tim Hasler |
Software preservation, OPUS and exemplary plans for UG | |
| 10:00 | LH | Bogdan Zavalnij |
About some problems arising from large scale parallelization of NP class combinatorial problems The large scale parallelization of any branch and bound algorithm usually leads to the problem of uneven distribution. The difference between subproblems in time complexity can be of several magnitudes thus leading to impractical solution. One obvious, but not always easy, method to tackle with this problem is by trying to estimate the size of the search tree. I would like to show that in order to do this we need to differentiate between problems of finding a solution and proving the non-existence of a solution. In other words the difference between NP-hard and NP-complete problem class. I would like to demonstrate the above theoretical thoughts by an example of the maximum clique and k-clique search problem. As an interesting fact I would like to show why a superlinear speedup in some algorithms is bad for us, and how can we avoid it. | slides |
| 10:30 | Foyer | Coffeebreak | ||
| 10:50 | LH | Jonathan Eckstein |
Parallel Branch and Bound from the Connection Machine CM-5 to PEBBL 2.0
In 1992, I created the “CMMIP” parallel branch-and-bound code for mixed-integer programming on the Connection Machine CM-5.
It lacked cutting planes and modern incumbent heuristics (which were largely unknown at the time), but could attain very high parallel relative efficiencies.
I describe some implementation strategies in this code, and how they were generalized and improved in the PEBBL object-oriented parallel branch-and-bound framework which I subsequently developed in conjunction with researchers at Sandia National Laboratories.
PEBBL has exhibited relative efficiencies of up to 89% for large search trees explored on 8K processor cores, and over 90% on 6K cores.
An essentially unique feature of these codes is the use of the “rendezvous” algorithm in the load balancing scheme, permitting scalability without adding levels to the control hierarchy.
I will also discuss other key features of PEBBL and how to implement PEBBL applications.
The talk will close with a discussion of the changes and new features in the upcoming 2.0 release of PEBBL and an invitation to future collaborations.
We plan for PEBBL 2.0 to support multi-level parallelism in which large groups of processors collaborate on individual subproblem operations such as bounding and branch selection.
| |
| 12:00 | LH | Takanori Maehara |
Learning NUOPT MILP Solver for Racing Ramp-Up Phase
The racing ramp-up phase is the feature of parallel branch and bound framework UG. Several parameters compete simultaneously on the ramp-up phase, and its winner is chosen for parallel branch and bound to distribute the nodes. This gives a certain impact on the performance of parallel branch and bound and implemented in several modern MILP parallel solver.
On the other hand, machine learning tools, such as the binary classification, are proven to be useful to find good parameters for branch and bound. We discuss how much they are useful for prediction of "winner" in the racing ramp-up phase.
| |
| 12:30 | Campus | Lunch | ||
| 14:30 | LH | Jean-Paul Watson |
Parallelization of Decomposition Solvers for Stochastic Programming: Software, Algorithms, and Challenges We discuss our experience with and challenges in developing scalable parallel decomposition solvers for stochastic programming problems, emphasizing the scenario-based progressive hedging (PH) algorithm. Following a brief introduction to our open source PySP software library, we will discuss scalability challenges to date and how we are working to address them – including through the use of asynchronous variants of the core PH algorithm. Co-Authors: David L. Woodruff, Jonathan Eckstein | |
| 15:15 | LH | David L. Woodruff |
BBPH - Branch and Bound that uses Progressive Hedging as a sub-problem solver for Solve Multi-Stage Stochastic Mixed Integer Programs Progressive hedging (PH), though an effective heuristic for stochastic mixed integer programs (MIPs), is not guaranteed convergence in the integer case. Here, we propose BBPH, a branch and bound algorithm that uses PH within each node that, given enough time, will always converge to an optimal solution. Computational results are presented. Co-authors: Jason Barnett, Jean-Paul Watson | slides |
| 15:40 | LH | Kibaek Kim |
A Scalable Decomposition Approach for Stochastic Mixed-Integer Programs
Stochastic mixed-integer programming (SMIP) is a large-scale optimization problem with continuous and discrete variables. In particular, the number of discrete variables increases with the number of scenarios. We present a dual (scenario) decomposition of stochastic mixed-integer programming, which leads to a parallel algorithm that can run on high performance computing (HPC) clusters. The dual decomposition is based on the Lagrangian relaxation of SMIP with respect to the scenario coupling constraints (i.e., nonanticipativity constraints) and only provides a Lagrangian bound without guarantee to find a primal feasible solution. We develop a scalable branching method on top of the dual decomposition in order to find a global optimum of SMIP. In this talk we will also present numerical results by using SIPLIB test instances on Argonne’s HPC cluster.
| slides |
| 16:10 | Foyer | Coffeebreak | ||
| 16:30 | LH | Daniel Rehfeldt |
ug[SCIP-Jack, MPI]: A massively parallel Steiner tree solver
The Steiner tree problem in graphs is one of the fundamental (NP-hard) combinatorial optimization problems and commonly arises in practical applications as one of many variants. The general-purpose solver SCIP-Jack can solve the classic Steiner tree problem as well as 11 related problems to optimality. Furthermore, SCIP-Jack comes with shared and distributed parallelization extensions by means of the UG framework. This talk will shortly introduce SCIP-Jack and will go on to describe the adaptations necessary to efficiently parallelize SCIP-Jack by UG. The resulting solver ug[SCIP-Jack,MPI] has been able to solve several well-known Steiner tree instances for the first time to optimality.
| slides |
| 17:15 | LH | Lluis Miquel Munguia |
Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to optimize MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this talk, we present two different parallelizations of Branch & Bound (B&B), implemented both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks,
PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been sucessfully applied to other MIP solvers.
| slides |
| Time | Place | Speaker | Detailed Information | |
|---|---|---|---|---|
| 09:30 | SR | Yuji Shinano |
Ubiquity Generator Framework: Current Status via a Scip Application Example
In this talk, the current status of parallel MIP solvers instantiated by UG, that is, ParaSCIP and ParaXpress will be presented.
These are running quite stable on supercomputers up to 43,000 cores, and have also been used with up to 80,000 cores.
Additionally, an introduction will be given on how to develop UG applications and ug[SCIP,*] applications.
| slides |
| 10:30 | Foyer | Coffeebreak | ||
| 10:50 | SR | Programming session: bring your own code, start your own UG project, ... | ||
| 12:30 | Campus | Lunch | ||
| 14:30 | SR | Programming session: bring your own code, start your own UG project, ... | ||
| 15:45 | SR |
Ambros Gleixner Yuji Shinano | Closing and Announcements | |
| 16:00 | Foyer | Coffeebreak and open end |
