UG

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.

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.

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.

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.

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.

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.

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)

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.

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.