This talk introduces the solver QuBowl, which solves maximum-cut and quadratic unconstrained binary optimization (QUBO) problems to proven optimality. We describe key components, such as cutting planes, and also discuss parallelization. QuBowl was able to solve several maximum-cut and QUBO instances for the first time to optimality and is currently leading the Mittelmann QUBO benchmark.

The Ubiquity Generator (UG) Framework was initially developed to parallelize advanced branch-and-bound based solvers. With the introduction of version 1.0, UG transitioned into a high-level task parallelization framework, enabling the parallelization of a broad range of state-of-the-art solvers. This framework facilitates the integration of multiple algorithmic implementations into a parallel solver. This presentation will highlight several success stories where UG has been utilized to solve previously intractable instances of Mixed Integer Programming, Steiner Tree, Quadratic Assignment, and Quadratic Unconstrained Binary Problems, as well as to set new benchmarks for Shortest Vector Problem instances. Finally, the most recent developments in the UG Framework will be discussed.

The Quadratic Assignment Problem (QAP) consists of assigning nodes to an equal number of facilities, where the cost associated with each assignment is quadratic. This classical NP-hard problem remains challenging to solve optimally, and several instances in QAPLIB are still open.
This talk will present our advancements in tackling huge scale QAPs using a parallel branch-and-bound method equipped with the Ubiquity Generator framework (UG) and implemented in our solver, ParaQapNB, which utilizes over 100,000 cores. The efficacy of this approach relies heavily on the integrated lower bounding procedures. We employed the Lagrangian and doubly nonnegative (Lagrangian-DNN) relaxation and the Newton-bracketing method to obtain strong and accurate lower bounds. New features of UG, such as Enhanced Checkpoint and Huge Checkpoint File Split, help to efficiently utilize a massive number of cores and manage large branch-and-bound trees. We will present some preliminary numerical results from ParaQapNB, including the tai30a, sko42, and tho40 instances from QAPLIB, which were solved for the first time.

Domain-independent dynamic programming (DIDP) is a recently proposed model-based paradigm for combinatorial optimization based on dynamic programming (DP). In DIDP, similar to mathematical programming, a user formulates a combinatorial optimization problem as a declarative DP model and then solves the formulated model by calling a general-purpose solver. The currently developed DIDP solvers are based on heuristic search algorithms studied in the artificial intelligence community. In this work, we develop parallel DIDP solvers using parallel heuristic search algorithms. First, we empirically confirm that the multi-thread versions of our parallel DIDP solvers outperform commercial multi-thread mixed-integer programming and constraint programming solvers in multiple combinatorial optimization problems. Then, we develop distributed parallel DIDP solvers using the Message Passing Interface. Our experimental evaluation demonstrates the high scalability of the parallel DIDP solvers in a massively parallel distributed environment.