Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2017-06-13

Назначение - поиск приближенных решений задачи размещения предприятий и фабричного ценообразования (Facility location and pricing problem)

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

Область применения - размещение предприятий, складов, ценообразование.

Используемый алгоритм - двухфазный поиск с чередующимися окрестностями, использующий локальный поиск для определения размещения предприятий и локальный поиск по разным окрестностям для нахождения цен при выбранном размещении. Алгоритм опубликован в статье [1].

Для работы программы необходимо сформировать input.txt файл. 
1) Указать число примеров решаемой задачи (integer).

Для каждого из примеров:
2.а) Указать размерность задачи (число возможных мест открытия предприятий, число клиентов, число открываемых предприятий) и параметры метода решения (максимальное число итераций, максимальное время счета в секундах, максимальное число итераций внутреннего VNS-алгоритма, максимальный размер k окрестности k-flip, глубина просмотра окрестностей k-flip); (все integer)
2.б) Указать матрицу транспортных затрат (строки - возможные места открытия предприятий, столбцы - клиенты); (все double)
2.в) Указать бюджеты клиентов. (все double)
В прилагаемом файле Program1.png. приведен тестовый пример. Результаты работы программы выводятся в файл output.txt. В нем выводятся результаты работы (места, где открыты предприятия, цены, значение целевой функции и время работы) по каждой итерации и лучшее найденное решение в конце. Как видно из результатов расчета (файл Program2.png), на втором примере задачи (файл Program1.png), в найденном решении открыты предприятия в местах 0 и 2, и назначена цена 3 на обоих предприятиях. Итоговый доход равен 12. Время работы менее секунды (округление до целых). 

[1] Кочетов Ю., Панин А., Плясунов А. Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и ценообразования. Дискретн. анализ и исслед. опер., 2015, том 22, номер 3 с. 36-54. https://doi.org/10.17377/daio.2015.22.480

Функциональные возможности - программа позволяет находить приближенные решения с малой погрешностью для задачи размещения предприятий и фабричного ценообразования. При размерности до 100 возможных мест открытия предприятий и клиентов, при 5 размещаемых предприятиях алгоритм находит решение с погрешностью не более 1%. Ограничение на размерность задачи отсутствует, но при большей размерности требуется больше временных ресурсов.

Инструментальные средства создания - Microsoft visual studio 2012, c/c++.

 

2017-05-19

SMITH является лабораторной информационной системой со встроенными конвейерами обработки биологических данных. Программа поддерживает деятельность биологической лаборатории начиная с процесса заказа на обработку биологического образца и заканчивая предоставлением готовых к интерпретации данных.

Назначение: управление пользователям, биологическими образцами, конвейерами обработки данных в лаборатории высокопроизводительного секвенирования.  

Область применения: АСУ, АСУ ТП, лабораторная информационная система (ЛИС), обработка данных ChIP-Seq, RNA-Seq, DNA-Seq.

Используемый алгоритм: Пользователь взаимодействует с SMITH для заказа секвенирования, для выбора типа и настроек секвенирования, для добавления описания образцов (в виде ключ-значение) для последующего анализа мета-данных и для отслеживания образцов через интерфейс SMITH. Пользователи также могут собрать образцы в проекты и назначить сотрудникам уровень допуска. Технический персонал взаимодействует с SMITH для сборки проточных ячеек, для ввода идентификаторов реагентов и для отслеживания уровня реагентов.

SMITH помогает в сборке проточных ячеек путем подбора образцов с совместимыми баркодами, для того, чтобы не возникало коллизий баркодов на стадии демультиплексирования. С точки зрения пользователя, наиболее важные функции – загрузка образов и отслеживание образов. Загруженные образцы имеют статус «заказан». Перед запуском секвенатора, генерируется виртуальная проточная ячейка, которую подтверждают лидеры групп. После запуска секвенирования по собранной проточной ячейке автоматически генерируется таблица, необходимая для мультиплексирования. По завершению секвенирования, SMITH автоматически отслеживает новые данные, генерируются и исполняются скрипты, которые производят файлы FASTQ, копируют их в нужные директории на сервере, запускают конвейеры обработки, запускают FastQC и отправляют уведомления пользователям, что их данные доступны для анализа. После этого, образец получает статус «проанализирован».

Функциональные возможности: 

  • Загрузка образцов
  • Аннотирование образцов
  • Анализ образцов
  • Отслеживание образцов
  • Разделение на проекты
  • Отслеживание директорий с данными
  • Контроль качества
  • Политика безопасности
  • Хранилище реагентов
  • Доступ по ролям
  • Виртуальные проточные ячейки
  • Совместимость индексов
  • Уведомления по email

Програма расчитана на нагрузки в 2-3 эксперимента высокопроизводительного секвенирования. Объем данных одного эксперимента - 40 Гб. Время обработки одного эксперимента 20-36 часов.

Инструментальные средства создания - SMITH была разработана с использованием технологии Java Enterprise и среды разработки NetBeans 7.3. SMITH запускается на сервере приложений Java EE (например, Glassfish). Apache Maven используется как инструмент управления зависимостями.

Архитектура SMITH подразделяется на веб-уровень, срединный уровень и системно-информационный уровень, следуя парадигме Model-View-Controller (MVC). Веб-интерфейс предоставляется средствами Java Server Faces (JSF) и PrimeFaces. Сервлет Faces, который является частью технологии JSF, играет роль контроллера и координирует информационный обмен между пользователем и моделью через набор представлений. Модель основана на технологии JSF Managed Beans – взаимодействующие модули, которые связаны с информационной системой, которая основана на Hibernate с базой MySQL. Отображаемые сообщения выделены в отдельный ресурс для простой интернационализации.

Публикация:

Venco F, Vaskin Y, Ceol A, Muller H.  SMITH: a LIMS for handling next-generation sequencing workflows. BMC Bioinformatics. 2014;15 Suppl 14:S3. doi: 10.1186/1471-2105-15-S14-S3.

2017-05-19

Сервисы GMQL - система с формами доступа к базам биологических данных, основанная на геномном SQL-подобном языке GMQL. Создание веб-сервиса происходит автоматически на основе параметризованного запроса. После исполнения запроса пользователю доступны средства визуализации данных в виде графиков, таблиц или аннотаций в геномном браузере.

Назначение: доступ к базам данных высокопроизводительного секвенирования.

Область применения: биоинформатика, биология, геномика, базы данных, биологические лаборатории.

Используемый алгоритм: Каждый сервис состоит из параметризированного запроса на геномном языке GMQL, короткого описания функций сервиса и формы с параметрами, которые задает пользователь. Детальное описание с биологическими аспектами доступно для нескольких выделенных запросов. Также, для большинства запросов доступны параметры по умолчанию для того, чтобы новые пользователи смогли опробовать сервисы.

Сервисы GQML поддерживают два типа параметров, вводимых пользователем:

  • Файловый тип. Файлы, которые загружает пользователь
  • Текстовый тип. Любое текстовое значение

Файлы, которые задаются, как входные параметры, загружаются в формате BED и содержат геномные регионы. Сервисы GMQL загружают файлы, конвертируют их во внутренний формат GMQL, выполняют запросы с использованием этих внутренних данных, сохраняют выходные данные и затем удаляют временные данные на сервере. Таким образом, файлы сохраняются на сервере только во время выполнения запроса. Если пользователь задает несколько файлов, то они загружаются на сервер как несколько образцов одного набора данных.

Значения текстовых параметров вставляются напрямую в текст запроса. Например, сервис, который осуществляет выборку образцов из репозитория ENCODE по клеточной линии, используя параметр «cell». Параметр «cell» может принимать различные значения (например, K562, H1-hESC, GM12878, и т.д.), которые соответствуют значениям клеточных линий в репозитории ENCODE. Пользователь выбирает значение параметра и запрос выполняется с этим значением. Для удобства пользователя доступно авто-заполнение значений. Значения подставляются из мета-данных, собранных по всему репозиторию, по мере того, как пользователь печатает в поле параметра.

Если запрос осуществляется к коллекции с публичными данными, то пользователь имеет возможность оценить количества образцов, которые будут выбраны. Для этого пользователь задает параметры, сервисы GMQL находят запросы выборки и запускают их с заданными параметрами. Это необходимо, чтобы оценить количество выбранных образцов перед запуском вычислительно требовательных запросов.

Сервисы GMQL запускаются асинхронно, то есть пользователь может запустить несколько запросов одновременно. Запросы передаются на исполнение вычислительному ядру, основанном на Hadoop, и используют внутренние репозитории с данными. Результат, который предоставляет вычислительное ядро, передается обратно сервисам GMQL, которые осуществляют дополнительные вычисления, например, для отображения графиков.

Необработанные данные, полученные после выполнения каждого запроса, представляют собой архив с файлами, содержащими геномные участки. Для того, чтобы предоставить пользователю информацию о содержании этих архивов и файлов, сервисы GMQL осуществляют дополнительную обработку данных и выводят отчеты в трех форматах:

  • Форматом по умолчанию является стандартный выходной формат GMQL – геномные участки в формате GTF (индексация с 0), мета-данные и технические детали выполнения запроса.
  • Формат CSV сохраняет все регионы (индексация с 1) с мета-данными всего образца, которые добавляются к каждому региону. Этот формат может быть использован для дальнейшей работы с регионами программным способом.
  • Формат BED содержит только геномные регионы (индексация с 1), без мета-данных.

Полученные в результате геномные участки могут быть визуализированы в геномном браузере IGB. Сервисы GMQL используют скриптовый язык IGB и веб-соединение IGB. Геномный браузер IGB должен быть запущен на компьютере пользователя, тогда ссылка, которая доступна в отчете, генерируемом после запуска сервисов, автоматически перенаправит полученные данные в браузер IGB. Данные будут автоматически скачаны с сайта GMQL и загружены в геномный браузер, как треки аннотаций.

Функциональные возможности

  • Структурированный доступ к базам данных высокопроизвоидетльного секвенирования
  • Автозаполнение параметров
  • Загрузка пользовательских файлов
  • Асинхронный запуск сервисов
  • Генерация результатов в форматах BED, BedGrpah
  • Генерация выходных графиков и таблиц (распредеоение участков, тепловая карта участков и т.д.)
  • Расширение новыми сервисами с подстветкой синтаксиса для языка GMQL

Сервисы GMQL рассчитаны на обработку коллекций данных объемом до 400Гб. Среднее время выполнения одного из 26-ти встроенных веб-сервисов составляет 5 минут.

Инструментальные средства создания - приложение на фреймворке Django, которое запускается с помощью HTTP-сервера и WSGI сервера Python. Связанные модули Python указаны в файле requirements.txt. Редактируемые переменные окружения безопасности (максимальный размер загружаемого файла, максимальное время выполнения запроса и т.д.) находятся в файле настроек.

 

2017-05-17

Назначение Проведение расчетов по моделированию релаксационных процессов в высокотемпературной плазме. Моделирование неустойчивостей в плазме, излучения в турбулентной плазме. Моделирование перспективных установок управляемого термоядерного синтеза (УТС).
Область применения Физика управляемого термоядерного синтеза. Физика ускорителей. Промышленные плазменные технологии. 
Используемый алгоритм Динамика плазмы описывается системой уравнений, состоящей из уравнения Власова и уравнений Максвелла. Уравнение Власова решается методом частиц в ячейках, уравнения Максвелла - с помощью метода конечных разностей во временной области.

По заданным пользователем плотности и температуре плазмы, а также параметрам пучка (энергия, плотность, температура) генерируется распределение частиц в расчетной области. Расчетная область (ячейки и частицы) распределяются между узлами суперЭВМ, содержащими графические ускорители. На каждом временном шаге рассчитывается движение модельных частиц, по ним вычислчется распределение тока в области и происходит перерасчет поля. Один раз в течение нескольких шагов происходит выдача указанных пользователем величин (тока, плотности, поля и др.) на диск.

Реализация алгоритма Алгоритм реализован на графических ускорителях (GPU) с помощью технологии CUDA.
Протетирован на графических ускорителях Nvidia Tesla M2090, Nvidia Kepler K40, Nvidia Pascal P100.

Функциональные возможности

1) Декопмозиция расчетной области

2) асинхронная пересылка частиц

3) расчет электромагнитного поля

4) расчет излучения плазмы

5) учет влияния малых примесей в плазме

6) диагностика плазменных величинТребования к аппаратно-программному обеспечению:
ОС Linux, CUDA 6.0, GPU cc 1.3

7) расчетные сетки до 1 млрд. узлов, до 100 Гб памяти, до 500 GPU

Алгоритм опубликован в:
1. Вшивков В.А., Вшивков К.В., Дудникова Г.И.  Алгоритмы решения задачи взаимодействия лазерного импульса с плазмой//Вычислительные технологии. Том 2, номер 6, 2001.

2. A.V.Snytnikov. Supercomputer simulation of plasma electron heat conductivity decrease due to relativistic electron beam relaxation//Procedia Computer Science.

3. A.V. Snytnikov, M.A. Boronina, E.A. Mesyats, A.A. Romanenko. A technology for the design of hybrid supercomputer simulation codes for relativistic particle electrodynamics.//Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва).– М.: Изд-во МГУ, 2015. – 844 с

2017-05-16

Назначение: Получение проектных решений по размещению единиц технологического оборудования (например, в цехах промышленного предприятия).
Область применения: крупные производственные предприятия (нефтехимические, машиностроительные и др.).
Используемый алгоритм: В работе рассматривается задача размещения габаритных объектов на линии с запрещенными зонами. Задача является NP-трудной. Предлагается алгоритм поиска приближенного решения, состоящий из двух этапов. На первом этапе, с помощью алгоритма последовательно-одиночного размещения, находится очередное допустимое разбиение объектов по областям, в которых допускается расположение объектов. На втором – объекты переставляются в указанных областях с целью минимизации суммарной стоимости связей.  

Описание постановки задачи, ее свойств, модели, предложенного алгоритма, а также интерфейс разработанного программного приложения и способы его настройки и установки – в файле “Инструкция по работе с программой” (Instruction.pdf).

Функциональные возможности:

  1. Ведение справочника тестируемых задач.
  2. Работа с реальными или синтетическими данными.
  3. Возможность копирования одной задачи в другую.
  4. Возможность визуализации результатов решений задач.
  5. Хранение информации по решаемым задачам в базе данных.
  6. Возможность выгрузки полученных результатов для последующего анализа.
  7. Объем обрабатываемых данных зависит от версии MS SQL Server 2000. При использовании MS SQL Server 2000 Personal Edition ограничения на объем базы данных до 2 ГБ.

Инструментальные средства создания: Алгоритм реализован в среде разработки Borland C++ Builder 6.0. Хранение первоначальных данных и результатов решений задач организовано в виде базы данных (БД), созданной на основе MS SQL Server 2000.

Публикации:

  1. Забудский Г.Г., Веремчук Н.С. Алгоритм приближенного решения задачи Вебера на линии с запрещенными зонами // Дискрет. анализ и исслед. операций. 2016. Т. 23, № С. 82-96. (An Algorithm for Finding an Approximate Solution to the Weber Problem on a Line with Forbidden Gaps // Journal of Applied and Industrial Mathematics, 2016, Vol. 10, No. 1, pp. 136-144. Pleiades Publishing, Ltd., 2016. Original Russian Text G.G. Zabudskii, N.S. Veremchuk, 2016, published in Diskretnyi Analiz i Issledovanie Operatsii, 2016, Vol. 23, No. 1, pp. 82-96. DOI: 10.1134/S1990478916010154)
  2. Gennady Zabudsky, Natalia Veremchuk. About Local Optimum of the Weber Problem on Line with Forbidden Gaps // Proc. DOOR 2016, Vladivostok, Russia, September 19-23, 2016. CEUR-WS. 2016. Vol. 1623. P. 115-124. CEUR-WS.org, online http://ceur-ws.org/Vol-1623/paperco17.pdf