High-performance solver for binary quadratic problems
Many problems in combinatorial optimization can be formulated as constrained binary quadratic problems(BQPs),which are in genera lNP hard. We present a method for ﬁnding exact solutions of large-scale linearly constrained binary quadratic programming problems. Our exact solution method combines parallelization techniques and exact penalty method approach to obtain optimal solutions of problems of sizes that are due to their size unsolvable by existing method sand tools. We use exact penalty method to ﬁrst eﬃciently transform constrained BQP into an instance of max-cut. The obtained problem is then solved by parallel branch-and-bound algorithm that uses SDP based relaxations and is implemented using MPI (distributed memory parallel model) on supercomputer HPC located at Faculty of Mechanical Engineering of the University of Ljubljana. We will present numerical results and demonstrate how to submit a graph instance to new opensource parallel solver BiqBin for (BQPs) which is available as an online service.
2018
2018-07-19 10:21:04
1033
high-performance computing, combinatorial optimization, max-cut problem
visoko zmogljivo računalništvo, kombinatorična optimizacija, problem maksimalnega prereza
Timotej
Hrga
70
Janez
Povh
70
Angelika
Wiegele
70
UDK
4
519.8(045)
COBISS_ID
3
16150811
OceCobissID
13
16150299