Project: High-Performance Solvers for Binary Qua...
Master data
| High-Performance Solvers for Binary Quadratic Problems | |
| Description: | A linearly constrained binary quadratic problem (BQP) is an elegant mathematical model having binary decision variables, a non-convex quadratic objective function and linear constraints. It captures a variety of real life problems from data science, logistics, telecommunications, finance etc. However, it is difficult to solve (NP hard) in theory and practice, requiring algorithmic ingenuity and substantial computing resources, even for instances of small size. But with the emergence of high-performance computing (HPC) accompanied by recent advances in optimization theory, a new avenue for solving at least medium size problems is now open. We propose a project whose main goal and innovation is creating the best open-source solver for BQP, which (i) will outperform all state-of-the-art solvers; (ii) will be fully parallelized; (iii) will be available as an online service running on the high-performance computer (HPC) Rudolf owned by the Faculty of Information Studies in Novo Mesto (FIS) and (iv) will be scalable to any HPC. The methodology of the project will focus on new and efficient transformations of BQP into unconstrained binary problems. This is done in the spirit of exact penalty methods but retaining discreteness of the variables. Novel relaxations based on semidefinite programming, sum-of-squares and moment approximations will be explored. Moreover, we will design new heuristics for BQP and assemble all parts of the code efficiently in a Branch & Bound based solver called BiqBin. All algorithms will be coded to run in parallel to achieve best performance on HPC infrastructure leading to an innovative tool for solving a large and interesting class of optimization problems. The project bridges the gap between mathematical optimization and HPC, fields which have rarely interacted so far to common benefit. It is aligned with the European Exascale Software Initiative which highlights the need for optimization algorithms that scale to the exascale level and with the recent European Commission Memo which encourages the development of new HPC software and services to address scientific challenges. The project is a natural continuation of previous cooperation between the project partners in the area of mathematical optimization. The principal investigator from the Alpen-Adria-Universität Klagenfurt (Angelika Wiegele) with the surrounding group is well recognized for contributions of algorithms and academic software for hard optimization problems (the bundle method, the boundary point method, BiqMac). Researchers from Slovenia (Janez Povh, Igor Klep, Drago Bokal, Borut Luzar) have vast expertise and experience in mathematical modeling, designing heuristics, implementing the results in other scientific fields and working with HPC. |
| Keywords: | binary quadratic problems; semidefinite problems; high-performance computing; optimization software; branch-and-bound. |
| Short title: | Binary Quadratic Programming |
| Period: | 01.07.2017 - 30.06.2021 |
| Contact e-mail: | angelika.wiegele@aau.at |
| Homepage: | http://www.biqbin.eu |
Employees
| Employees | Role | Time period |
|---|---|---|
| Angelika Wiegele (internal) |
|
|
| Melanie Siebenhofer (internal) |
|
|
| Nicolo Gusmeroli (internal) |
|
|
| Franz Rendl (internal) |
|
|
| Elisabeth Gaar (internal) |
|
|
| Muamer Hrncic (internal) |
|
|
| Miriam Köberl (internal) |
|
|
Assignment
| Organisational unit | ||||
|---|---|---|---|---|
|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Categorisation
| Project type | Research funding (on request / by call for proposals) |
| Funding type | §26 |
| Research type |
|
| Subject areas | |
| Research Cluster | No research Research Cluster selected |
| Gender aspects | 0% |
| Project focus |
Classification raster of the assigned organisational units:
|
| working groups | No working group selected |
Cooperations
| Organisation | Address | ||
|---|---|---|---|
University of Novo Mesto, Faculty of information studies
|
SI - 8000 Novo mesto |
||
University of Ljubljana, Faculty of Mechanical Engineering
|
SI - 1000 Ljubljana |
||
University Ljubljana, Institute of Mathematics, Physics and Mechanics
|
SI - 1000 Ljubljana |
Research activities
| Projects | No related projects |
| Publications |
|
| Events | No related events |
| Lectures |
|