• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Статья
Multidimensional frontier visualization based on optimization methods using parallel computations

Afanasiev A., Krivonozhko V., Lychev A. et al.

Journal of Global Optimization. 2019. P. 1-12.

Глава в книге
Three-Dimensional Visualization for Multidimensional Analysis and Performance Management of Socio-Economic Systems

Afanasiev A., Krivonozhko V., Lychev A. et al.

In bk.: 2019 IEEE 21st Conference on Business Informatics (CBI). Vol. 1. M.: IEEE Computer Society, 2019. P. 57-64.

Темы КР и ВКР

Темы КР и ВКР для студентов МП Системы больших данных

 

базовая кафедра ИППИ РАН «Высокопроизводительные вычисления» зав. каф. д.ф.-м.н.,

проф., А.П. Афанасьев

 

1.

Реализация методов решения задач конечномерной и динамической оптимизации в среде распределённых вычислений.

 

The implementation of solving methods for  finite-dimensional and dynamic optimization problems in a distributed computing environment.

 

руководитель А.П. Афанасьев.

 

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

The problem of adapting known algorithms for solving finite-dimensional optimization tasks of high dimensionality and optimal control problems on multiprocessor computer systems and distributed computer systems with subsequent design and implementation of software-algorithmic complex Is a topical. The transition to computing in a distributed environment poses fundamentally new challenges associated with the effective organization of calculations in the system consisting of heterogeneous architecture and performance of computers, which can leave or enter the computational space at arbitrary times. Therefore, one of the most important tasks of the project is to conduct theoretical and experimental research of efficiency of the developed software to construct and study models of computing.

Литература:

1. Афанасьев А.П. Продолжение траекторий в оптимальном управлении  М.: Эдиториал УРСС, 2005. с. 263

2. S.V. Emelyanov, A.P. Afanasiev, Y.R. Grinberg, V.E. Krivtsov,

B.V. Peltsverger, O.V. Sukhoroslov, R.G. Taylor, V.V. Voloshinov Distributed Computing and Its Applications. Felicity Press, Bristol,USA, 2005.ISBN: 0-931265-10-2, 298p.

3. A.P. Afanas’ev, S. M. Dzyuba, I. I. Emelyanova Analitical  and numerical investigation for the problem of optimal control of nonlinear system via quadratic criteria // Procedia Computer Science YSC 2015. 4th International Young Scientists Conference on Computational Science  Volume XXX, 2015, Pages 1–9

 

 

2.

Имитационное моделирование вычислительных ресурсов и распределенных вычислительных инфраструктур. 

 

Simulation of computing resources and distributed computing environments.

 

руководитель О.В. Сухорослов

 

Имитационное моделирование активно используется в исследованиях распределенных систем, заменяя натурные эксперименты и позволяя воспроизводимым образом сравнивать между собой различные методы (например, алгоритмы планирования задач). В данной работе объектом моделирования являются распределенные вычислительные инфраструктуры, состоящие из нескольких автономных ресурсов различного типа (кластеров, гридов, облаков, персональных компьютеров). Для реалистичного моделирования таких инфраструктур требуется хорошо моделировать отдельные ресурсы, их планировщики, нагрузку и доступность, а также передачу данных по сети. Для данных целей предлагается использовать SimGrid (http://simgrid.gforge.inria.fr/), фреймворк для создания симуляторов распределенных систем. Требуется улучшить имеющиеся или реализовать новые модели ресурсов (например, кластер с планировщиком и внутренним потоком заданий, облачная инфраструктура), а также интегрировать их в единую модель. Возможны отдельные подтемы и работа в команде.

Simulation is actively used in studies of distributed systems, replacing full-scale experiments and allowing a reproducible way to compare various methods (for example, task scheduling algorithms). In this project, the modeled distributed computing infrastructure consists of several autonomous resources of various types (clusters, grids, clouds, personal computers). For realistic modeling of such infrastructures, it is required to model well individual resources, their schedulers, load and availability, and data transmission over the network. For these purposes, it is suggested to use SimGrid (http://simgrid.gforge.inria.fr/), a framework for creating simulators of distributed systems. You need to improve existing or implement new resource models (for example, a cluster with a scheduler and internal job flow, a cloud infrastructure), and integrate them into a distributed infrastructure model. Individual subtopics and teamwork are possible.

Литература:

Casanova H., Giersch A., Legrand A., Quinson M., Suter F.: Versatile, scalable, and accurate simulation of distributed applications and platforms. Journal of Parallel and Distributed Computing 74(10), 2899-2917 (2014). https://hal.inria.fr/hal-01017319/document

 

 

3.

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

 

Simulation and comparative study of task scheduling algorithms for distributed computing environments.

 

руководитель О.В. Сухорослов

 

Планирование выполнения задач в распределенных системах в постановках, представляющих практический интерес, является NP-полной задачей. За последнее десятилетие было предложено множество алгоритмов планирования, основанных на различного рода (мета)эвристиках и ориентированных на различные классы приложений (bag of tasks, parallel job, workflow) и систем. При этом недостаточно хорошо изучен вопрос об области применимости и сравнительной эффективности данных алгоритмов в различных ситуациях. В данной работе предлагается реализовать на базе существующего симулятора наиболее известные алгоритмы и сравнить их друг с другом путем проведения имитационных экспериментов для различных типов приложений и систем. Возможны отдельные подтемы и работа в команде.

The problem of scheduling tasks in distributed systems, in statements of practical interest, is an NP-complete problem. Over the last decade, a lot of scheduling algorithms based on various kinds of (meta)heuristics and targeted to different classes of applications (bag of tasks, parallel jobs, workflows) and systems have been proposed. At the same time, the question of the scope of applicability and comparative efficiency of these algorithms in various situations is not well studied. In this project, it is proposed to implement the known scheduling algorithms on the basis of the existing simulator and compare them with each other by carrying out simulation experiments for various types of applications and systems. Individual subtopics and teamwork are possible.

Литература:

1. Сухорослов О.В., Назаренко А.М. Сравнительная оценка методов планирования приложений в распределенных вычислительных средах //Программные системы: теория и приложения, 2017, 8:1(32), с. 63–81. https://www.researchgate.net/publication/317065627 

2. Nazarenko A., Sukhoroslov O. An Experimental Study of Workflow Scheduling Algorithms for Heterogeneous Systems.  In: Malyshkin V. (eds) Parallel Computing Technologies. PaCT 2017. Lecture Notes in Computer Science, vol 10421. Springer, Cham, 2017, pp. 327-341. https://www.researchgate.net/publication/317258605

 

 

4.

Реализация онлайн-сервиса для автоматизации многовариантных расчетов в облаках. 

 

Implementation of online service for automation of parameter sweep computations in clouds.

 

руководитель О.В. Сухорослов

 

Многовариантные расчёты являются важным классом приложений, которые состоят из большого числа вычислительных задач, определённых на множестве входных параметров и запускаемых с различными значениями данных параметров. Необходимость такого рода вычислений возникает во многих областях науки и техники. Например, при создании новых лекарств необходимо провести отбор наиболее перспективных молекул из сотен тысяч кандидатов путём компьютерного моделирования взаимодействия каждой молекулы с белком-мишенью. При проектировании новых изделий необходимо выполнить подбор оптимальных значений их параметров (например, профиль и угол атаки крыла самолёта), выполнив моделирование поведения изделия для различных вариантов.

На базе платформы Everest реализован универсальный вычислительный сервис ParameterSweep [1], автоматизирующий проведение многовариантных расчётов на подключенных к платформе вычислительных ресурсах. Данный сервис поддерживает декларативный формат описания расчёта в виде так называемого план-файла, не требующий от пользователя реализации каких-либо дополнительных программ помимо расчётного модуля. Также был создан прототип сервиса AutoTuner для автоматизации решения смежного класса задач - автоматической настройки параметров программ [2]. Особенностью этого сервиса является выбор исследуемых значений параметров с помощью различных алгоритмов оптимизации и эвристик.

В данной работе предполагается дальнейшее развитие данных сервисов по следующим направлениям:

• Объединение и расширение функционала сервисов ParameterSweep и AutoTuner

• Поддержка запуска вычислений на динамически выделяемых ресурсах облачных провайдеров (Amazon Web Services, Google Cloud Platform, Microsoft Azure)

• Оценка и оптимизация стоимости проведения расчётов в облаке.

Parameter sweep calculations are an important class of applications that consist of a large number of computational tasks defined on a set of input parameters and executed with different values of these parameters. The need for such calculations arises in many areas of science and technology. For example, when creating new drugs, it is necessary to select the most promising molecules from hundreds of thousands of candidates by computer simulation of the interaction of each molecule with a target protein. When designing new technical systems, it is necessary to select the optimal values of their parameters (for example, the profile and the angle of attack of the wing of the aircraft), by modeling the behavior of the system for various options.

On the base of the Everest platform, the generic ParameterSweep service [1] is implemented, which automates the execution of parameter sweep experiments on the distributed computing resources connected to the platform. This service supports a declarative format for describing the calculation in the form of a so-called plan file, which does not require the user to implement any additional programs besides the calculation module. Also, a prototype of the AutoTuner service was created to automate the solution of a similar class of tasks - automatic tuning of program parameters [2]. A specific feature of this service is the choice of the investigated parameter values using various optimization algorithms and heuristics.

In this project, the further development of these services is proposed in the following areas:

• Integration and expansion of the functionality of the ParameterSweep and AutoTuner services

• Support for running computations on dynamically allocated resources of cloud providers (Amazon Web Services, Google Cloud Platform, Microsoft Azure)

• Evaluation and optimization of the cost of conducting computations in the cloud

Литература:

1. Volkov S., Sukhoroslov O. A Generic Web Service for Running Parameter Sweep Experiments in Distributed Computing Environment. Procedia Computer Science, Volume 66, 2015, pp. 477-486. https://www.researchgate.net/publication/284899158 

2. Oleg Sukhoroslov, Sergey Volkov and Alexander Afanasiev. Program Autotuning as a Service: Opportunities and Challenges // Proceedings of the 9th International Conference on Utility and Cloud Computing (UCC '16). ACM, 2016, pp. 148-155. https://www.researchgate.net/publication/311615283

 

5.

Создание отказоустойчивого проекта добровольных распределенных вычислений.

 

Creating a fault-tolerant voluntary distributed computing project.

 

руководитель И.И. Курочкин

 

Рассматривается подход по созданию вычислительного приложения для научных расчетов и разворачиванию проекта распределенных вычислений на основе грид-системы без использования собственной вычислительной инфраструктуры. Существует несколько платформ для организации распределенных вычислений: Globus, HTCondor, но самой распространенной на текущий момент является BOINC. На базе платформы BOINC развернуто около 100 проектов добровольных распределенных вычислений, к которым подключены около 16 миллионов устройств по всему миру. Суммарная вычислительная мощность компьютеров добровольцев превосходит вычислительную мощность современных суперкомпьютеров. При разворачивании и сопровождении проекта добровольных распределенных вычислений важнейшими аспектами являются масштабирование и отказоустойчивость серверной части проекта. Предлагается на основе существующей платформы BOINC развернуть проект распределенных вычислений с повышенными требованиями к отказоустойчивости.

An approach to creating computing applications for scientific calculations and deployment distributed computing project based on a grid system without using its own computing infrastructure is discussed. There are exist several frameworks for organizing distributed computing: Globus, HTCondor, but the most common at the moment is BOINC. On the basis of the BOINC platform deployed about 100 projects for voluntary distributed computing is connected to around 16 million devices worldwide. The total computing power of volunteers exceeds the computational power of modern supercomputers. Deploying and support of the project of the voluntary distributed computing the most important aspects are the scalability and fault tolerance the server part of the project. Is proposed on the basis of an existing platform to deploy a BOINC distributed computing project with high demands on fault tolerance.

Литература:

1.boinc.berkeley.edu

2.boincstats.com

3.Trilce Estrada, Michela Taufer, David P. Anderson. Performance Prediction and Analysis of BOINC Projects: An Empirical Study with EmBOINC // Journal of Grid Computing. -2009. - V. 7. - P. 537–555

4. Peter Kacsuk. SZTAKI Desktop Grid (SZDG): A Flexible and Scalable Desktop Grid System // Journal of Grid Computing. - 2009. -V. 7 - P. 439–461

 

 6.

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

 

Development of a load balancing system for the umbrella distributed computing project.

 

руководитель И.И. Курочкин

 

В рамках распределенных вычислений, представляющих собой способ решения трудоемких вычислительных задач с использованием компьютеров, объединенных в вычислительную систему, особый интерес представляют добровольные вычисления. Это распределенные вычисления с использованием добровольно предоставленных вычислительных ресурсов. В качестве платформы организации проектов распределенных вычислений предлагается BOINC, как самая распространенная платформа для добровольных распределенных вычислений. Организация зонтичного проекта распределенных вычислений дает возможность одновременно проводить ряд небольших численных экспериментов. Под зонтичным проектом подразумевается проект, в котором есть несколько независимых вычислительных приложений. В качестве примера действующего зонтичного проекта добровольных распределенных вычислений предлагается проект World Community Grid медицинской тематики, который поддерживает корпорация IBM. Для такого типа проектов распределенных вычислений особую роль играет скорость получения результата и эффективное использование имеющихся распределенных ресурсов. Одним из способов повышения эффективности работы грид-систем является разработка и настройка системы балансировки нагрузки.

Within distributed computing, which is a way of solving complicated computational problems using the computers connected in a computer system, of particular interest are voluntary computing. This distributed computing using volunteered computer resources. As a platform of organization of the distributed computing projects BOINC is proposed as the most common platform for volunteer distributed computing. The umbrella organization of the distributed computing project gives an opportunity to carry out a number of small numerical experiments. Under the umbrella project is a project in which there are several independent computing applications. As an example, the current umbrella project of the voluntary distributed computing is proposed for the project World Community Grid medical subjects, which supports the IBM Corporation. For this type of distributed computing projects, a special role is played by the speed of obtaining results and efficient use of available distributed resources. One of the ways to improve the efficiency of grid systems is the development and configuration of load balancing.

Литература:

1.      boinc.berkeley.edu

2.      www.worldcommunitygrid.org

3.      Krallmann J. On the design and evaluation of job scheduling systems / J. Krallmann, U. Schwiegelshohn, R. Yahyapour // Lecture Notes in Computer Science. –  1999. – Vol. 1659. – P. 17-42.

4.      R. Naik. Instantaneous Utilization Based Scheduling Algorithms for Real Time Systems / R. Naik, R.R. Manthalkar // International Journal of Computer Science and Information Technologies. – 2011. – Vol. 2 (2). – P. 654-662.

 

 7.

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

 

Development of a service for training deep neural networks on a cloud platform.

 

руководитель И.И. Курочкин

 

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

Предлагается интегрировать инструмент по обучению глубокой нейронной сети в облачную платформу Everest как сервис. Предполагается, что к сервису по обучению глубокой нейронной сети будут подключены гетерогенные вычислительные ресурсы.

Methods of computer learning have found application in the field of detection and classification and segmentation of objects based on deep neural networks. A deep neural network is a neural network, which thus has a number of layers, in which selective methods of learning cease to be effective. To train such networks, a number of methods have been developed, for example, the use of special activation functions, optimization methods, the creation of additional links between the corresponding layers, allowing to avoid fading errors. In tasks that require working with images, and in particular in problems of image storage, detection and classification of objects on the image, segmentation, expansion of applications of convolutional neural networks found.

It is proposed to integrate a tool for training a deep neural network into the Everest cloud platform as a service. It is assumed that heterogeneous computing resources will be connected to the training service for a deep neural network.

Литература:

1. He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: CVPR. (2016)

2. P. Sermanet, D. Eigen, X. Zhang, M. Mathieu, R. Fergus, and Y. LeCun. Overfeat: Integrated recognition, localization and detection using convolutional networks. CoRR, abs/1312.6229, 2013

3. R. Girshick, J. Donahue, T. Darrell, and J. Malik. Rich feature hierarchies for accurate object detection and semantic segmentation. 2014.

4. C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna. Rethinking the inception architecture for computer vision. arXiv preprint arXiv:1512.00567, 2015.

 

 

8.

Создание open source аналога блокчейна AlgoRand.

Open source realisation of the blockchain technology AlgoRand.

 

Руководитель А.С. Тарасов

 

Основной проблемой развития криптотехнологий является малая пропускная способность блокчейна по сравнению с централизованными решениями. В силу этого Algorand имеет шансы перехватить пальму первенства у таких блокчейнов как Bictoin и Ethereum.

Профессором MIT Сильвио Микали предложена схема блокчейна с потенциально очень высокой пропускной способностью, основанная на случайном выборе участников подписывающих блок транзакций. 

В данный момент разрабатывается прориетарное решение для такого блокчейна  фирмой Toda. 

Нами предполагается, что для успешного массового внедрения технологии, она должна быть эффективно верифицирована сообществом и должно существовать несколько реализаций одного протокола. Это все можно реализовать только при open-source подходе.

The main problem of the development of the cryptotechnologies is the low bandwidth of the blockchain compared to the centralized solutions. Because of this, Algorand has a chance to intercept the palm of such blockchains like Ethereum and Bictoin.

The MIT Professor Silvio Micali scheme is proposed blockchain with a very high throughput, based on random selection of participants.

Currently developing proprietary software for this blockchain firm Toda.

We anticipate that the successful mass adoption of the technology, it needs to be effectively verified by the community, and there must be multiple implementations of the same Protocol. This all can only be realized with an open-source approach. 

Литература:

https://arxiv.org/abs/1607.01341

https://www.todachain.com/

 

 

9.

Поиск оптимальной формы Гёмбеца методами нелинейной оптимизации.

Search for optimal shape of Gömböc my non-linear optimization methods.

 

Руководитель А.С. Тарасов

 

В 1999 году Томасом Хейлсом была решена знаменитая гипотеза Кеплера ( так же известная как 18-ая проблема Гильберта часть 3) при помощи массированнного перебоа графов и решения системы нелинейных уравнений для каждого из графов.

В 2009 году похожим методом Олегом Мусиным и Алексеем Тарасовым была решения задача Таммеса для N=13. 

 

Развивая этот подход можно решить ряд сложных задач дискретной геометрии.

В частности:

1. Найти Гёмбёц содержащий менее 1000 граней

2. Найти многогранник описанный вокруг единичной сферы с заданным числом граней и имеющим минимальный объем (обобщение гипотезы додекаэдра).

3. Найти многогранник вписанный в единичную сферу с заданным числом вершин и имеющим максимальный объем.

In 1999, Thomas Hales solved a famous conjecture of Kepler ( also known as the 18th problem of Hilbert part 3) with massive enumeration of graphs and solving systems of nonlinear equations for each of the graphs.

In 2009 a similar method Oleg Musin and Tarasov Alexey was the solution of the task of Tammes for N=13.

 

Building on this approach can solve number of difficult problems in discrete geometry.

In particular:

1. Find Gambar containing less than 1000 faces

2. Find a polyhedron circumscribed around a unit sphere with a given number of faces and with a minimum amount of (a generalization of the hypothesis of a dodecahedron).

3. Find a polyhedron inscribed in a unit sphere with a given number of vertices and having maximum volume.

Литература:

https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%9A%D0%B5%D0%BF%D0%BB%D0%B5%D1%80%D0%B0

http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n3-p01.pdf

https://en.wikipedia.org/wiki/Tammes_problem

https://arxiv.org/abs/1002.1439

https://ru.wikipedia.org/wiki/%D0%93%D1%91%D0%BC%D0%B1%D1%91%D1%86

https://arxiv.org/abs/math/9811079

https://en.wikipedia.org/wiki/Dodecahedral_conjecture

 

 

10.

Создание мультимодальной системы поиска оптимального маршрута.

 

Algorithm for optimal route on multimodal transport network.

 

Руководитель А.С. Тарасов

 

Основной экономией транспортных перевозок крупных логистических компаний является экономия на порожних плечах.

Грузовикам небольшим компаний после каждого выполненного рейса обычно приходится возвращаться назад пустым, иногда при удаче подбирая попутный груз. В результате доля порожнего пробега маленьких компаний колеблется в районе 40-50%.

Для крупных компаний эта величина составляет 25-40%, что дает существеннную выгоду. 

Использование автоматической системы планирования маршрутов на основании методой целочисленной линейной оптимизации позволяет снизить коэффициент порожнего пробега отдельной компании на 10-15 процентных пунктов. 

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

Разработка этого проекта включат в себя две существенно сложные технологические части.

1. Сбор различных данных : структура заказов, тарифы различных компаний. Здесь будут использоваться веб-технологии и методы машинного обучения.

2. Решение задачи методами дискретной линейной оптимизации.

 

 

11.

Сравнение различных способов оценки константы Хоффмана для систем с большим числом неравенств 

 

Comparison of different ways to estimate the Hoffman constant for systems with a large number of inequalities

 

руководитель В.В. Волошинов

 

В теории оптимизации и соответствующих вычислительных методах важное значение имеет результат впервые опубликованных Аланом Хоффманом в 1952 году и с тех пор известный как «теорема Хоффмана» или «лемма Хоффмана» [1]. Установлено, что для для любого множества Q из конечномерного пространтсва Rn, заданного системой линейных ограничений  Q = {x∈Rn: aiTx ≦ bi, i∈I}, существует число С (т. н. «константа Хоффмана»), зависящее только от векторов коэффициентов при переменных {ai, i∈I} (а не от правых частей, bi), которое позволяет для любого конечномерного вектора x∈Rn оценить расстояние до множества Q как величину, пропорциональную просто вычисляемой характеристики нарушения указанных линейных неравенств: например, dist(Q,x) ≦ С max{[aiTx - bi]+, i∈I} или dist(Q,x) ≦ С sum{[aiTx - bi]+, i∈I}) . 

Этот результат имеет важное значение, как для теории оптимизации (в т.ч. - нелинейных задач [2], так и для численных методов при анализе устойчивости решений систем уравнений [3,5]). 

Несмотря на относительно несложный способ доказательства существования константы Хоффмана (см., например, [1, 6]), вычисление ее значения (или, хотя бы, верхней оценки) является нетривиальной задачей [3, 4, 5]. Известные схемы вычислений носят переборный характер. При одной формулировке поиск значения C сводится к построению всех крайних точек некоторого многогранного множества. При другой — вычисление C сводится к задаче глобальной максимизации выпуклой квадратичной функции на выпуклом множестве решений системы выпуклых линейных или квадратичных неравенств. 

В работе нужно будет сравнить различные способы вычисления (или верхней оценки) константы Хоффмана для больших систем линейных неравенств (|I|>>1). Для вычислений можно применять пакеты языка Python SciPy, Pyomo; пакет анализа систем линейных неравенств (с возможностью работать в режиме параллельных вычислений), http://cgm.cs.mcgill.ca/~avis/C/lrslib/; решатель задач математического программирования с полилинейными функциями SCIP, http://scip.zib.de/

Литература:

1. Hoffman A.J. On approximate solutions of systems of linear inequalities. J. Res. Nat.Bur. Stundards, 1952, vol. 49. p. 263-265

2. Левитин Е.С., Милютин А.А., Осмоловский Н.П. Теория условий высших порядков в гладких задачах на экстремум с ограничениями // В сборнике:  "Теоретические и прикладные вопросы оптимального управления", Новосибирск, из-во "Наука", Сибирское отделение, 1985, с. 4-40., http://milyutin.ru/papers.html

3. Güler O., Hoffman A., Rothblum U. Approximations to solutions to systems of linear inequalities // SIAM Journal on Matrix Analysis and Applications. 1995 Apr, 16(2), pp. 688-696. https://doi.org/10.1137/S0895479892237744

4. Белоусов Е.Г. О вычислении точных констант Липшица и Хоффмана для системы линейных неравенств // Всетник ТГУ, т.4, вып.4, 2000, с. 416-417, https://cyberleninka.ru/article/n/o-vychislenii-tochnyh-konstant-lipshitsa-i-hoffmana-dlya-sistemy-lineynyh-neravenstv

5. Zheng, X.Y. and Ng, K.F. Hoffman’s least error bounds for systems of linear inequalities // Journal of Global Optimization, 2004, 30(4), pp. 391-403.

6. Волошинов В.В. Теорема Хоффмана об оценке расстояния до множества решений линейной системы (неравенств и/или равенств). Материал к лекциям по курсу "Технологии оптимизационного моделирования", http://distcomp.ru/drupal/ru/staff/vladimirv/TOM_2013

7. D. Avis, lrs: A revised implementation of the reverse search vertex enumeration algorithm. G. Kalai, G.M. Ziegler (Eds.), Polytopes — Combinatorics and Computation, Oberwolfach Seminars, vol. 29, Birkhäuser-Verlag (2000), pp. 177-198

 

 

12.

Сравнение эффективности симплекс-метода и метода внутренней точки для задач линейного программирования большой размерности.

 

Comparison of the efficiency of the simplex- and the interior point method for linear programming problems of large dimension.

 

руководитель В.В. Волошинов

 

Понятие задач линейного программирования было предложено более 80 лет назад Л.В. Канторовичем в СССР в конце 30х годов и Г.Б. Данцигом в США (открытые публикации в конце 40х годов прошлого века). До настоящего времени - это очень важный для практических приложений класс задач. Традиционно для их решения применяется специальный численный метод, т. н. Симплекс-метод  [1, 2, 3]. Несмотря на недостатки, проявляющиеся для специально подобранных задач, этот метод до сих пор является стандартом де-факто для библиотек численных методов (пакетов, решателей) задач линейного программирования. В середине 70х годов, работы Хачияна в СССР, а затем Кармаркара в США положили начало новому классу численных методов решения нелинейных задач математического программирования, т. н. методов внутренней точки (Interior Point Methods). Эти методы установили «полиномиальную сложность» приближенного решения задач линейного и выпуклого программирования [4]. По сравнению с симплекс-методом, для задач линейного программирования, метод внутренней точки совершает меньше итераций, но каждая итерация вычислительно более трудна, чем шаг симплекс метода. В работе предлагается провести ряд вычислительных экспериментов по практическому сравнению эффективности указанных методов на задачах большой размерности (десятки тысяч переменных и ограничений). Для этого предлагается использовать решатели: Ipopt (Coin-OR Interior Point OPTimizer), [5], https://projects.coin-or.org/Ipopt; CLP (Coin-OR LP), https://projects.coin-or.org/Clp; SoPlex (Sequential object-oriented simPlex).

Литература:

1. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А.И. Штерна, - М.;Наука, 1990. - 488с.

2. Муртаф Б. Современное линейное программирование. М. Мир, 1984, 224 с.

3. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: Изд-во «Факториал Пресс», 2003. — 352 с.

4. Нестеров Ю.Е. Введение в выпуклую оптимизацию / Под ред. Б.Т. Поляка, С.А. Назина. - М.: МЦНМО, 2010. - 280 с.

5. Andreas Wächter, Lorenz T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming //  Mathematical Programming, 2006, Vol. 106, no. 1, pp. 25-57. https://doi.org/10.1007/s10107-004-0559-y