ЛЕКЦИЯ 30 (сокр. версия) Курс: Проектирование систем: Структурный подход Каф. Коммуникационные сети и системы, Факультет радиотехники и кибернетики Московский физико-технический институт (университет) / Марк Ш. ЛЕВИН Институт проблем передачи информации, РАН Дек. 3, 2004 ПЛАН: 1.Задача размещения (формулировки как назначения, сопоставление, размещение): *задача о назначении (паросочетаниях), *квадратичная задача о назначении (QAP), *обобщенная задача о назначении (GAP), *сопоставление строк (иллюстрация), *multiple matching (иллюстрация) 2.Список базовых алгоритмических подходов 3.Схема эволюции задач типы размещения 4.Список прикладных областей 5.Базовая библиография (книги и сайты)

Размещение (назначение, сопоставление, позиционирование): ОТОБРАЖЕНИЕ Двухдольный граф a b c d e f g h Множество элементов (персонал, оборудование и др.) Задача размещения (Allocation problem) Позиции

Задача размещения (Allocation problem) Матрица весов c ij a b c d e f g h a b c d e f g h Позиции Размещение (назначение, сопоставление, позиционирование): Множество элементов (персонал, оборудование и др.) Двухдольный граф

Задача размещения (Allocation problem): прикладные примеры элементов и позиций 1.Мальчики -- Девочки (задача о женитьбах) 2.Рабочие – Рабочие позиции 3.Оборудование –Позиции в производственных системах (размещение оборудования) 4.Задания -- Процессоры в многопроцессорных системах 5.Анти-ракеты –Цели в оборонных системах 6.Массивы -- Базы данных в распределенных информационных система Др..

Задача о назначении (Assignment problem AP) a3a3 a1a1 a2a2 anan b1b1 ФОРМУЛИРОВКА (комбинаторная): Элементы (персонал, оборудование, задания): A = { a 1, …, a i, …, a n } Позиции (позиции, процессоры и др.) B = { b 1, …, b j, …. b m } (здесь n = m) Эффективность пары a i и b j : c ( a i, b j ) = {s} - множество перестановок (назначений) элементов A на позиции из множества B: s* =, т.е., элемент a i на позиции s[i] Целевая функция: max n i=1 c ( i, s[i]) Максимум (минимум) сопоставление с весами в взвешенном двухдольном графе b2b2 b3b3 bmbm... ЭЛЕМЕНТЫПОЗИЦИИ

a3a3 a1a1 a2a2 anan b1b1 ДРУГАЯ ФОРМУЛИРОВКА (алгебраическая): Элементы (персонал, оборудование, задания): A = { a 1, …, a i, …, a n } Позиции (позиции, процессоры и др.) B = { b 1, …, b j, …. b m } (здесь n = m) Эффективность пары a i и b j is: c ( a i, b j ) x ij = 1 если a i размещено на позиции b j и 0 в противном случае ( x ij { 0,1 } ) Задача: max n i=1 n j=1 c ij x ij s.t. n i=1 x ij = 1 j n j=1 x ij = 1 i b2b2 b3b3 bmbm... ЭЛЕМЕНТЫПОЗИЦИИ Задача о назначении (Assignment problem AP)

АЛГОРИТМЫ: 1.Полиномиальный точный алгоритм ( O(n 3 ) ) 2.Венгерский метод Др. ДРУГИЕ ВЕРСИИ: 1.Minimum задача 2.Min max задача 3.Многокритериальная задача Др. Задача о назначении (Assignment problem AP)

Квадратичная задача о назначении (Quadratic Assignment Problem QAP) a3a3 a1a1 a2a2 anan b1b1 b2b2 b3b3 bmbm... ЭЛЕМЕНТЫПОЗИЦИИ матрица весов (поток) c ij.... c ij.... b 1 … b j … b n a1…ai…ana1…ai…an матрица расстояний d ij.... d ij.... b 1 … b j … b n b1…bi…bnb1…bi…bn

Квадратичная задача о назначении (Quadratic Assignment Problem QAP) Базовая (потоковая) Формулировка Квадратичной Задачи о Назначении Назначение элементов { i | i {1,…,n} } на позиции { p(i) }, где p - перестановка номеров {1,…,n }, Множество всех возможных перестановок - = { p }. Рассматриваются две матрицы n на n : (i)матрица потока (или полезности ) C, где элемент (i,j) представляет поток между элементами (например, оборудованием) i и j, (ii)матрица расстояния D, где элемент (i,j) ( p(i), p(j) ) представляет Расстояние между позициями p(i) и p(j). Таким образом, задача QAP записывается так: max n i=1 n j=1 c ij d p(i)p(j) p

Квадратичная задача о назначении (Quadratic Assignment Problem QAP) АЛГОРИТМЫ: 1.Метод ветвей и границ 2.Методы релаксации (сведения к непрерывным моделям) (Relaxation approach) 3.Жадные алгоритмы 4.Генетические алгоритмы (эволюционные вычисления) 5.Мета-эвристики (локальная оптимизация, гибридные схемы и др.) БАЗОВЫЕ КНИГИ: 1.P.M. Pardalos, H. Wolkowicz, (Ed.), Quadratic Assignment and Related Problems. American Mathematical Society, E. Cela, The Quadratic Assignment Problem. Kluwer, САЙТЫ: 1.Quadratic assignment Problem Library:

Многокритериальная квадратичная задача о назначении Multi-objective (multicriteria) Assignment Problem (Quadratic Assignment Problem): Элементы в матрице весов (потоки): вектора АЛГОРИТМЫ: 1.Метод ветвей и границ 2.Метод релаксации (Relaxation approach) 3.Жадные алгоритмы 4.Мета-эвристики (локальная оптимизация, гибридные схемы и др.) 5.Многокритериальная эволюционная оптимизация (Multi-objective evolutionary optimization)

Обобщенная задача о назначениях (Generalized Assignment Problem GAP) ОТОБРАЖЕНИЕ (один-много) ДВУХДОЛЬНЫЙ ГРАФ a b c d e f g h Позиции (агенты, процессоры) Множество элементов (заданий и др.) Ресурсы

Обобщенная задача о назначении (Generalized Assignment Problem GAP) a3a3 a1a1 a2a2 anan b1b1 ФОРМУЛИРОВКА (алгебраическая): Элементы (персонал, оборудование, задания): A = { a 1, …, a i, …, a n } Позиции (позиции, процессоры и др.) B = { b 1, …, b j, …. b m } (здесь n = m) Эффективность пары a i и b j : c ( a i, b j ) x ij = 1 если a i размещено на позиции b j и 0 в противном случае ( x ij { 0,1 } ) Задача: max n i=1 n j=1 c ij x ij s.t. n i=1 r ik x ij R j j ( R k - это ресурс агента k ) n j=1 x ij = 1 i b2b2 b3b3 bmbm... ЭЛЕМЕНТЫ (задания) ПОЗИЦИИ (агенты, процессоры ) РЕСУРСЫ { R k } ij k as j (1…m) one-many

Обобщенная задача о назначении (GAP) (много общих ресурсов) a3a3 a1a1 a2a2 anan b1b1 ФОРМУЛИРОВКА (алгебраическая): Элементы (персонал, оборудование, задания): A = { a 1, …, a i, …, a n } Позиции (позиции, процессоры и др.) B = { b 1, …, b j, …. b m } (здесь n = m) Эффективность пары a i и b j : c ( a i, b j ) x ij = 1 если a i размещено на позиции b j и 0 в противном случае ( x ij { 0,1 } ) Задача: max n i=1 n j=1 c ij x ij s.t. m j=1 n i=1 r ik x ij R k k ( K общих ресурсов) n j=1 x ij = 1 i b2b2 b3b3 bmbm... ЭЛЕМЕНТЫ (задания) ПОЗИЦИИ (агенты как процессоры и др.) РЕСУРСЫ { R jk } ij k (1…K) one-many

Обобщенная задача о назначении (Generalized Assignment Problem GAP) АЛГОРИТМЫ: 1.Метод ветвей и границ 2.Метод релаксации 3.Эвристики (жадные алгоритмы и др.) 4.Генетические алгоритмы (эволюционные вычисления) 5.Мета-эвристики (локальная оптимизация, гибридные схемы и др.) РАСШИРЕНИЯ: 1.Многокритериальные случаи 2.Неопределенность 3.Др. (зависимость между частями задачи, Зависимость от времени и др.)

Сопоставление строк (String matching) СЛУЧАЙ 2-Х СЛОВ: A ABBDX A DACXZ Строка (слово) 1 Строка (слово) 2 Z B DAB Образы (PATTERNS): XZ

A = { a 1, … a n }B = { b 1, … b m } C = { c 1, … c k } ПРИМЕР: 3-сопоставление (3-х дольный граф) Задача сопоставления на k-дольном графе (Multiple matching problem, Lecture 17-18)

АЛГОРИТМЫ: 1.Переборные алгоритмы (метод ветвей и границ и др.) 2.Эвристики (e.g., жадные алгоритмы, различные методы локальной оптимизации и др.) 3.Мета-эвристики включая гибридные схемы 4.Морфологический подход ВЕРСИИ: 1.Динамическая (много-стадийная) задача (сопоставление траекторий / трасс целей) 2.Задача с ошибками в данных 3.Задача с неопределенностью (вероятностные оценки, размытые множества) Др. Задача сопоставления на k-дольном графе (Multiple matching problem, Lecture 17-18)

Использование задачи о назначении для определения скоростей частиц (Lecture 17-18) КАДР 1КАДР 2КАДР 3 ПРОСТРАНСТВО СКОРОСТЕЙ ПРИЛОЖЕНИЯ (среда газа/жидкости): 1.Физические эксперименты 2.Наука о климате (анализ облаков и др.) 3.Химические процессы 4.Биотехнология Источники: 1.PIV системы 2.Фотографии со спутников 3.Электронные микроскопы и др.

Список алгоритмов для задач типа назначения / размещения 1.полиномиальные алгоритмы (венгерский метод, методы на основе потоковых подходов и др.) 2.Методы на основе линейного программирования 3.epsilon-приближенные полиномиальные методы 4.корректирующие алгоритмы 5.Метод ветвей и границ 6.метод динамического программирования 7.эволюционные и генетические алгоритмы 8.Схема декомпозиции Бендерса 9.Методы локальной оптимизации как различные эвристики (Tabu-поиск, метод отжига, гибридные схемы и др.) 10.Методы многокритериального анализа (функция полезности, Метод Аналитических, методы порогов сравнимости) 11.методы на основе имитационного моделирования 12.полихедральные методы (polyhedral methods) 13.Иерархические подходы включая морфологический подход 14.метод на основе задачи о выполнимости ограничений ("constraint satisfaction problem«) 15.подходы на основе размытых множеств 16.алгоритмические подходы на основе баз знаний 20.подходы на основе нейронных сетей

Блок-диаграмма задач типа размещения Базовая задача назначении Квадратичная задача о назначении ПЛЮС: матрица расстояний для позиций Обобщенная задача о назначении ПЛЮС: ресурсы для позиций Обобщенная квадратичная задача о назначении Многокрит. квадратичная задача Многокрит. обобщенная задача Многокрит. обобщенная квадратичная задача Многокритериальная задача О назначении ПЛЮС: многокритериальное описание ПЛЮС: матрица расстояний для позиций ПЛЮС: ресурсы для позиций ПЛЮС: много- критери- альное описание

1.размещение оборудования (layout) в производственных системах 2.размещение ресурсов в инвестиционных мероприятиях 3.размещение оборудования в управлении сетью поставок (supply chain management ) 4.размещение задач маршрутизации 5.размещение при проектировании больших интегральных схем (layout in VLSI design) 6.размещение при пространственном проектировании зданий 7.размещение в архитектурном планировании 8.размещение служб быстрого реагирования в чрезвычайных ситуациях 9.размещение буферов накопления в производственных системах 10.размещение операций техобслуживания 11.размещение операций контроля (тестирования) 12.размещение операций балансировки в сборочных линиях 13.размещение (распределение) человеко-машинных функций 14.формирование (оптимизация) портфеля финансовых инструментов (акций и др.) 15.назначение проектных задач Прикладные области для задач типа размещения

16.распределение ресурсов в больших коллективах 17.размещение ресурсов дорожной полиции 18.распределение крови в донорской системе 19.распределение статей между рецензентами 20.назначение в спорте 21.динамическое распределение памяти в вычислительных системах 22.размещение заданий в распределенных информационных / компьютерных системах 23.размещение задач в виртуальных организациях 24.размещение информации (документы, массивы) в информационных системах 25.распределение пропускных способностей в коммуникационных сетях 26.размещение ресурсов в Интернет 27.размещение ресурсов в инфраструктурах электронного бизнеса (e-business infrastructure) 28.проектирование стандартов 29.сопоставление траекторий (трасс) целей (в много-радарных системах) 30.размещение надежности между компонентами системы 31.задачи назначения в экспериментальной физике высоких энергий 32.locomotive assignment to train-segments Прикладные области для задач типа размещения

33.задачи назначения / размещения в университетах (назначение студентов на экзамены, назначение преподавателей на курсы, назначение аудиторий для лекций, и др.) 34.назначение частиц / точек (для сопоставление частиц) в системах particle image velocimetry (PIV) Для измерений в механике потоков 35.управление персоналом (размещение / назначение персонала, размещение заданий, распределение ролей) 36.распределение комнат между людьми 37.назначение прав (в социальных сетях (social networks for social choice and welfare), для участников электронного финансового рынка (electronic financial markets) 38.размещение дискретных ресурсов 39.назначение частот / каналов в мобильных радио системах 40.назначение сот (cells) к коммутаторам (switches) в сотовых мобильных сетях (cellular mobile networks) 41.размещение допусков в производственных системах 42.размещение wavelength на деревьях колец (rings) в оптических коммуникационных сетях Прикладные области для задач типа размещения

43.размещение в медицинских организациях: (1) Размещение хирургов по операционным, (2) allocation of inpatient resources, (3) размещение персонала, (4) размещение оборудование в госпитале, (5) размещение кроватей, (6) размещение органов для трансплантации, (7) размещение пациентов и др. 44.размещение узких мест в производственных системах 45.размещение трафика в транспортных и коммуникационных/компьютерных сетях 46.иерархическое размещение задач в сетях 47.динамическое размещение ресурсов в много-проектных исследования 48.размещение экологического оборудования 49.иерархическое размещение банковского оборудования

Базовые книги и сайты для задачи о размещении (Allocation/ Location Problems) BASIC BOOKS: 1.M.S. Daskin, Networks and Discrete Location. Models, Algorithms, and Applications. Wiley, G.Y. Handler, P.B. Mirchandrani, Location on Networks: Theory and Algorithms. MIT Press, E. Minieka, Optimization Algorithms for Networks and Graphs. Marcel Dekker, P.B. Mirchandrani, R.L. Francis, (Eds.), Discrete Location Theory, Wiley, P.M. Pardalos, H. Wolkowicz, (Ed.), Quadratic Assignment and Related Problems. American Mathematical Society, E. Cela, The Quadratic Assignment Problem. Kluwer, M.I. Rubinshtein, Optimal Grouping of Interconnected Objects, Nauka, (in Russian), D. Gusfield, R.W. Irwing, The Stable Marriage Problem: Structure and Algorithms, The MIT Press, J. Aoe, (Ed.), Computer Algorithms: String Pattern Matching Strategies. IEEE CS Press, A.I. Barros, Discrete and Fractional Programming Techniques for Location Models. Kluwer, SITES: 1.Dictionary of Algorithms and Data Structure (NIST): 2.OR-Library by J.E. Beasley: 3.Quadratic Assignment Problem Library: