Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
High-performance solver for binary quadratic problems
ID
Hrga, Timotej
(
Author
),
ID
Povh, Janez
(
Author
),
ID
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.
Image galllery
Abstract
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.
Language:
English
Keywords:
high-performance computing
,
combinatorial optimization
,
max-cut problem
Typology:
1.12 - Published Scientific Conference Contribution Abstract
Organization:
FS - Faculty of Mechanical Engineering
Year:
2018
Number of pages:
Str. 309
PID:
20.500.12556/RUL-101999
UDC:
519.8(045)
COBISS.SI-ID:
16150811
Publication date in RUL:
19.07.2018
Views:
1509
Downloads:
0
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
Record is a part of a monograph
Title:
ISMP 2018
Place of publishing:
Bordeaux
Publisher:
University of Bordeaux
Year:
2018
COBISS.SI-ID:
16150299
Secondary language
Language:
Slovenian
Keywords:
visoko zmogljivo računalništvo
,
kombinatorična optimizacija
,
problem maksimalnega prereza
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back