High-Performance Solvers for Binary Quadratic Problems

A variety of real-life problems from data science, logistics, telecommunications, finance, etc. can be captured in the mathematical model of so-called linearly constrained binary quadratic problems. "Binary" refers to the domain of the variables, meaning that a variable can only hold the value zero or one. There are no off-the-shelf methods or tools that can solve such problems in a routine way if the number of variables is too large. Real-life problems typically lead to sizes that are out of reach and there is high demand for solvers that can handle these instances. In this project titled "High-Performance Solver for Binary Quadratic Problems" we will develop new methods and tools to solve these problems to optimality for interesting problem sizes. The final result of the project will be a new open-source solver (called BiqBin) for this family of problems which will significantly outperform the state-of-the-art open-source and commercial solvers. We will achieve the project`s goals by exploring one of the recent ideas of mathematical optimization, namely rewriting a constrained binary optimization problem into an unconstrained binary problem. This innovative technique requires the investigation of new ideas for weakening the reformulated problem leading to optimality certificates. We will implement a parallel code and assemble all parts of the code into the new open- source solver BiqBin which will be also available as an online service running on a high- performance computer (HPC). Having such an efficient solver is a main innovation. Various test problems of applications that have been considered in the literature for years may be solved by BiqBin for the first time. One more essential innovative aspect is the interdisciplinary integration of mathematics, high- performance computing and internet technologies, which is a seldom practice in natural and technical sciences. The project team has already demonstrated successful cooperation in the last decade and will strengthen this cooperation by including young researchers from the participating institutions, which are the Department of Mathematics at Alpen-Adria-Universität Klagenfurt (AAU), the Faculty of Information Studies in Novo Mesto (FIŠ) and the Institute of Mathematics, Physics and Mechanics Ljubljana (IMFM). With this project the AAU will keep the leading role in producing academic software for nonlinear optimization, established through the BiqMac solver. The project will also leverage FIŠ its strive towards a leading position in application of high-performance computing in mathematical programming, since it is currently the only academic institution in Slovenia in the area of computer science or mathematics that owns a HPC and has high-performance computing in its research strategy.

A variety of real-life problems from data science, logistics, telecommunications, finance, etc. can be captured in the mathematical model of so-called linearly constrained binary quadratic problems. "Binary" refers to the domain of the variables, meaning that a variable can only hold the value zero or one. There are no off-the-shelf methods or tools that can solve such problems in a routine way if the number of variables is too large. Real-life problems typically lead to sizes that are out of reach and there is high demand for solvers that can handle these instances. In this project titled "High-Performance Solver for Binary Quadratic Problems" we developed new methods and tools to solve these problems to optimality for interesting problem sizes. The final result of the project is a new open-source solver (called BiqBin) for this family of problems which outperforms the state-of-the-art open-source and commercial solvers on several problem classes. We achieved the project's goals by exploring one of the recent ideas of mathematical optimization, namely rewriting a constrained binary optimization problem into an unconstrained binary problem. This innovative technique requires the investigation of new ideas for weakening the reformulated problem leading to optimality certificates. We implemented a parallel code and assembled all parts of the code into the new open-source solver BiqBin which is also available as an online service running on a high-performance computer (HPC) via http://biqbin.eu. One essential innovative aspect is the interdisciplinary integration of mathematics, high-performance computing and internet technologies, which is a not so common practice in natural and technical sciences. The project team, that has already demonstrated successful cooperation in the decade before starting this project, strengthened this cooperation by including young researchers from the participating institutions, which are the Department of Mathematics at Alpen-Adria-Universität Klagenfurt (AAU), the Faculty of mechanical engineering at the University of Ljubljana and the Faculty of Information Studies in Novo Mesto (FIŠ). With this project the AAU will keep the leading role in producing academic software for nonlinear optimization, established through the BiqMac solver. The project has also leveraged FIŠ and the Faculty of mechanical engineering at the University of Ljubljana in their strive towards international visibility in applications of high-performance computing in mathematical programming, since they are two out of a handful academic institutions in Slovenia that own an HPC and have high-performance computing in their research strategy.