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

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.

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.

The Participants

Foto by F. Schlösser

Schedule

At the end of each talk we plan 5 to 10 minutes time for questions and discussion. Click on the talk titles to display abstracts. LH short for lecture hall. SR short for seminar room.

Monday, January 14

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.

Tuesday, January 15

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

Wednesday, January 16

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

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

Funding

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