Title :
On local elimination algorithms for sparse discrete optimization problems
Author :
Lemtyuzhnikova, D. ; Sviridenko, A. ; Shcherbina, O.
Author_Institution :
Tavrian Nat. Univ., Simferopol, Ukraine
Abstract :
We discuss local elimination algorithms that compute global information using local computations. Results of benchmarking show real computational capabilities of block elimination algorithms combined with SYMPHONY solver. Strategies for parallelizing a sequential local elimination algorithm for sparse discrete optimization problems are analyzed. We propose to use hybrid Master-Worker scheme where Worker processors (GPUs) solve concurrently subproblems corresponding to super-nodes of extended elimination tree that are generated by a single master process (CPU).
Keywords :
multiprocessing systems; optimisation; parallel algorithms; trees (mathematics); CPU; GPU; SYMPHONY solver; block elimination algorithms; extended elimination tree; global information; hybrid master-worker scheme; local computations; local elimination algorithms; parallel strategies; real computational capabilities; sequential local elimination algorithm; single master process; sparse discrete optimization problems; worker processors; decomposition; discrete optimization; elimination; local algorithms; nonserial dynamic programming;
Conference_Titel :
Problems of Cybernetics and Informatics (PCI), 2012 IV International Conference
Conference_Location :
Baku
Print_ISBN :
978-1-4673-4500-2
DOI :
10.1109/ICPCI.2012.6486427
