Результаты поиска по 'декомпозиция':
Найдено статей: 22
  1. Лемтюжникова Д.В.
    Параллельное представление локального элиминационного алгоритма для ускорения решения разреженных задач дискретной оптимизации
    Компьютерные исследования и моделирование, 2015, т. 7, № 3, с. 699-705

    Алгоритмы декомпозиции являются методами решения NP-трудных задач дискретной оптимизации (ДО). В этой статье демонстрируется один из перспективных методов, использующих разреженность матриц, — локальной элиминационный алгоритм в параллельной интерпретации (ЛЭАП). Это алгоритм структурной из декомпозиции на основе графа, который позволяет найти решение поэтапно таким образом, что каждый последующих этапов использует результаты предыдущих этапов. В то же время ЛЭАП сильно зависит от порядка элиминации, который фактически является стадиями решения. Также в статье рассматриваются древовидный и блочный тип распараллеливания для ЛЭАП и необходимые процессы их реализации.

    Ключевые слова: дискретная оптимизация, добровольные вычисления, локальный элиминационный алгоритм, параллельные вычисления, разреженные задачи, элиминационное дерево.
    Lemtyuzhnikova D.V.
    Parallel representation of local elimination algorithm for accelerating the solving sparse discrete optimization problems
    Computer Research and Modeling, 2015, v. 7, no. 3, pp. 699-705

    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.
    Views (last year): 1.
  2. Смирнов С.А., Волошинов В.В.
    Предварительная декомпозиция задач дискретной оптимизации для ускорения алгоритма ветвей и границ в распределенной вычислительной среде
    Компьютерные исследования и моделирование, 2015, т. 7, № 3, с. 719-725

    В работе рассматриваются возможности реализации крупноблочных схем метода ветвей и границ для решения частично целочисленных задач линейного программирования. В качестве основы берется пакет оптимизации с открытым исходным кодом CBC. Анализируется возможность использования пакета для реализации крупноблочной схемы метода ветвей и границ. Система реализуется с использованием языка Erlang. Проводятся численные эксперименты на основе задачи о коммивояжере, показывающие заметное ускорение распределенной схемы решения задачи по сравнению с единичным однопоточным экземпляром пакета.

    Ключевые слова: метод ветвей и границ, крупнозернистый параллелизм.
    Smirnov S.A., Voloshinov V.V.
    Pre-decomposition of discrete optimization problems to speed up the branch and bound method in a distributed computing environment
    Computer Research and Modeling, 2015, v. 7, no. 3, pp. 719-725

    The paper presents an implementation of branch and bound algorithm employing coarse grained parallelism. The system is based on CBC (COIN-OR branch and cut) open-source MIP solver and inter-process communication capabilities of Erlang. Numerical results show noticeable speedup in comparison to single-threaded CBC instance.

    Keywords: branch and bound algorithm, coarse grained parallelism.
    Views (last year): 2. Citations: 2 (RSCI).
Pages: « first previous

Indexed in Scopus

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 RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Website Copyright © 2009–2025 Institute of Computer Science