High-performance solver for binary quadratic problems
Hrga, Timotej (Author), Povh, Janez (Author), Wiegele, Angelika (Author)

This document has no files.
This document may have a phisical copy in the library of the organization, check the status via COBISS. Link is opened in a new window

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 finding 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 first efficiently 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.

Keywords:high-performance computing, combinatorial optimization, max-cut problem
Tipology:1.12 - Published Scientific Conference Contribution Abstract
Organization:FS - Faculty of Mechanical Engineering
Number of pages:Str. 309
COBISS.SI-ID:16150811 Link is opened in a new window
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
AddThis uses cookies that require your consent. Edit consent...

Record is a part of a monograph

Title:ISMP 2018
Publisher:University of Bordeaux
COBISS.SI-ID:16150299 This link opens in a new window
Place of publishing:Bordeaux

Secondary language

Keywords:visoko zmogljivo računalništvo, kombinatorična optimizacija, problem maksimalnega prereza

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:


Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
There are no comments!