High-Performance Solvers for Binary Quadratic Problems

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.

Schlagworte: binary quadratic problems; semidefinite problems; high-performance computing; optimization software; branch-and-bound.
Kurztitel: Binary Quadratic Programming
Zeitraum: 01.07.2017 - 31.12.2020


MitarbeiterInnen Funktion Zeitraum
Angelika Wiegele (intern)
  • Projektleiter/in
  • 01.07.2017 - 31.12.2020
Melanie Siebenhofer (intern)
  • stud. Mitarbeiter/in
  • wiss. Mitarbeiter/in
  • 01.08.2017 - 30.06.2018
  • 01.11.2018 - 28.02.2019
Nicolo Gusmeroli (intern)
  • wiss. Mitarbeiter/in
  • 01.09.2017 - 31.12.2020
Franz Rendl (intern)
  • wiss. Mitarbeiter/in
  • 01.07.2017 - 31.08.2020
Elisabeth Gaar (intern)
  • wiss. Mitarbeiter/in
  • 01.07.2018 - 30.06.2020


Projekttyp Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp §26
  • Grundlagenforschung
  • 101011 - Graphentheorie
  • 101015 - Operations Research
  • 101016 - Optimierung
  • 101020 - Technische Mathematik
  • 1020 - Informatik
Forschungscluster Kein Forschungscluster ausgewählt
Genderrelevanz 0%
  • Science to Science (Qualitätsindikator: I)
Klassifikationsraster der zugeordneten Organisationseinheiten:
Arbeitsgruppen Keine Arbeitsgruppe ausgewählt


Organisation Adresse
Faculty of information studies, Novo Mesto, Slovenia
Ljubljanska cesta 31A
8000  Novo mesto
Ljubljanska cesta 31A
SI - 8000  Novo mesto
Univerza v Ljubljani, Fakulteta za strojništvo
Aškerčeva cesta 6
1000  Ljubljana
Aškerčeva cesta 6
SI - 1000  Ljubljana
Universität Ljubljana, Institute of Mathematics, Physics and Mechanics
Universität Ljubljana, Institute of Mathematics, Physics and Mechanics
1000  Ljubljana
Universität Ljubljana, Institute of Mathematics, Physics and Mechanics
SI - 1000  Ljubljana