Многомерная проблема назначения

Многомерная задача назначения (MAP) — это фундаментальная задача комбинаторной оптимизации , предложенная Уильямом Пирскалла . ^{[ 1 ]} Эту проблему можно рассматривать как обобщение линейной задачи о назначениях . ^{[ 2 ]} На словах проблему можно описать так:

Экземпляр проблемы имеет несколько агентов (т. е. параметр мощности ) и ряд характеристик работы (т. е. параметр размерности ), таких как задача, машина, временной интервал и т. д. Например, агенту можно назначить выполнение задачи. X, на машине Y, в течение интервала времени Z. Любой агент может быть назначен для выполнения задания с любой комбинацией уникальных характеристик задания за определенную стоимость . Эти затраты могут варьироваться в зависимости от назначения агента комбинации характеристик работы — конкретной задачи, машины, временного интервала и т. д. Проблема состоит в том, чтобы минимизировать общую стоимость назначения агентов так, чтобы назначение агентов каждой характеристике работы было или инъективная функция функция «один к одному» от агентов к заданной характеристике работы.

Альтернативно, описав проблему с помощью теории графов:

Задача многомерного назначения состоит в нахождении во заданного размера , взвешенном многодольном графе паросочетания в котором сумма весов ребер минимальна. ^{[ 3 ]}

Формальное определение

В литературе можно встретить различные постановки этой проблемы. Используя функции затрат, $D$ – проблема назначения размерностей (или $D$ –MAP ) можно сформулировать следующим образом:

Данный

D

наборы,

A

и

J_{1},\ldots J_{D-1}

, одинакового размера, вместе с массивом стоимости или многомерной весовой функцией

C

:

A\times J_{1}\times \ldots \times J_{D-1}\rightarrow \mathbb {R} _{+}

, находить

D-1

перестановки

\pi _{d}

: А →

J_{d}

такая, что функция полной стоимости :

\sum _{a\in A}C(a,\pi _{1}(a),\ldots ,\pi _{D-1}(a))

сведен к минимуму. ^{[ 4 ]}

Параметры задачи

Задача многомерного назначения (MAP) имеет два ключевых параметра, определяющих размер экземпляра задачи :

Параметр размерности  $D$
Параметр мощности  $N=|A|$ , где $|A|$ обозначает количество элементов в $A$ .

Размер массива затрат

Любой проблемный экземпляр MAP с параметрами $D,N$ имеет свой конкретный массив затрат $C$ , который состоит из $N^{D}$ параметры стоимости/веса для конкретного экземпляра $C(a,a_{1},\ldots ,a_{D-1})$ . $N^{D}$ — размер массива затрат.

Количество возможных решений

Допустимая область или пространство решений MAP очень велико. Число $K$ возможных решений (размер экземпляра MAP) зависит от параметров MAP $D,N$ . Конкретно, $K=(N!)^{D-1}$ . ^{[ 2 ]}

Вычислительная сложность

Проблема вообще NP-сложная . Другими словами, не существует известного алгоритма решения этой задачи за полиномиальное время, поэтому для решения экземпляров задачи даже умеренного размера (на основе параметров размерности и мощности) может потребоваться длительное время вычислений. ^{[ 5 ]}

Приложения

Проблема нашла применение во многих областях:

Ссылки

^ Jump up to: ^а ^б Пирскалла, Уильям П. (1968). «Письмо в редакцию — проблема многомерного назначения». Исследование операций . 16 (2). ИНФОРМ: 422–431. дои : 10.1287/опре.16.2.422 .
^ Jump up to: ^а ^б ^с Каммердинер, Алла; Семенов, Александр; Пасилиао, Эдуардо (2021). «Многомерная задача назначения для разрешения многочастных объектов». arXiv : 2112.03346 [ cs.DM ].
^ Нату, Шардул; Дата, Кетан; Наги, Ракеш (2020). «Лагранжева эвристика с ускорением на графическом процессоре для многомерных задач назначения с разложимыми затратами» . Параллельные вычисления . 97 : 102666. doi : 10.1016/j.parco.2020.102666 . ISSN 0167-8191 . S2CID 221667518 .
^ Карапетян, Даниил; Гутин, Григорий (01.06.2011). «Эвристика локального поиска для многомерной задачи назначения» (PDF) . Журнал эвристики . 17 (3): 201–249. дои : 10.1007/s10732-010-9133-3 . ISSN 1572-9397 . S2CID 3446729 .
^ Нгуен, Дюк Мань; Ле Тхи, Хоай Ан; Фам Динь, Тао (12 октября 2012 г.). «Решение многомерной задачи о назначениях методом перекрестной энтропии». Журнал комбинаторной оптимизации . 27 (4): 808–823. дои : 10.1007/s10878-012-9554-z . ISSN 1382-6905 . S2CID 254658376 .
^ Пур, Обри Б. (1994). «Формулировка многомерного назначения задач ассоциации данных, возникающих в результате отслеживания нескольких целей и нескольких датчиков» . Вычислительная оптимизация и приложения . 3 (1): 27–57. дои : 10.1007/BF01299390 . S2CID 33848795 .
^ Пуштазери, Жан-Франсуа; Ренсинг, Пол Э.; Либлинг, Томас М. (1996). «Отслеживание элементарных частиц вблизи их первичной вершины: комбинаторный подход». Журнал глобальной оптимизации . 9 (1): 41–64. дои : 10.1007/BF00121750 . S2CID 2002168 .
^ Каммердинер Алла Р.; Герерро, Андре Н. (2019). «Комбинаторная оптимизация на основе данных для сенсорной оценки опасностей падения» . Анналы исследования операций . 276 (1–2): 137–153. дои : 10.1007/s10479-017-2585-1 . ISSN 0254-5330 . S2CID 254223885 .

[Pier68-1] Jump up to: ^а ^б Пирскалла, Уильям П. (1968). «Письмо в редакцию — проблема многомерного назначения». Исследование операций . 16 (2). ИНФОРМ: 422–431. дои : 10.1287/опре.16.2.422 .

[Pasi21-2] Jump up to: ^а ^б ^с Каммердинер, Алла; Семенов, Александр; Пасилиао, Эдуардо (2021). «Многомерная задача назначения для разрешения многочастных объектов». arXiv : 2112.03346 [ cs.DM ].

[3] Нату, Шардул; Дата, Кетан; Наги, Ракеш (2020). «Лагранжева эвристика с ускорением на графическом процессоре для многомерных задач назначения с разложимыми затратами» . Параллельные вычисления . 97 : 102666. doi : 10.1016/j.parco.2020.102666 . ISSN 0167-8191 . S2CID 221667518 .

[4] Карапетян, Даниил; Гутин, Григорий (01.06.2011). «Эвристика локального поиска для многомерной задачи назначения» (PDF) . Журнал эвристики . 17 (3): 201–249. дои : 10.1007/s10732-010-9133-3 . ISSN 1572-9397 . S2CID 3446729 .

[5] Нгуен, Дюк Мань; Ле Тхи, Хоай Ан; Фам Динь, Тао (12 октября 2012 г.). «Решение многомерной задачи о назначениях методом перекрестной энтропии». Журнал комбинаторной оптимизации . 27 (4): 808–823. дои : 10.1007/s10878-012-9554-z . ISSN 1382-6905 . S2CID 254658376 .

[6] Пур, Обри Б. (1994). «Формулировка многомерного назначения задач ассоциации данных, возникающих в результате отслеживания нескольких целей и нескольких датчиков» . Вычислительная оптимизация и приложения . 3 (1): 27–57. дои : 10.1007/BF01299390 . S2CID 33848795 .

[7] Пуштазери, Жан-Франсуа; Ренсинг, Пол Э.; Либлинг, Томас М. (1996). «Отслеживание элементарных частиц вблизи их первичной вершины: комбинаторный подход». Журнал глобальной оптимизации . 9 (1): 41–64. дои : 10.1007/BF00121750 . S2CID 2002168 .

[8] Каммердинер Алла Р.; Герерро, Андре Н. (2019). «Комбинаторная оптимизация на основе данных для сенсорной оценки опасностей падения» . Анналы исследования операций . 276 (1–2): 137–153. дои : 10.1007/s10479-017-2585-1 . ISSN 0254-5330 . S2CID 254223885 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]