Parallel representation of local elimination algorithm for accelerating the solving sparse discrete optimization problems

 pdf (238K)

The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). In this article one of the promising ways to exploit sparse matrices — local elimination algorithm in parallel interpretation (LEAP) are demonstrated. That is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEAP heavily depends on elimination ordering which actually provides solving stages. Also paper considers tree- and block-parallel for LEAP and required realization process of it comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.

Keywords: discrete optimization, volunteer computing, local elimination algorithm, parallel computing, sparse problems, elimination tree
Citation in English: Computer Research and Modeling, 2015, vol. 7, no. 3, pp. 699-705

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the List of Russian peer-reviewed journals publishing the main research results of PhD and doctoral dissertations.

International Interdisciplinary Conference "Mathematics. Computing. Education"

The journal is included in the RSCI