Development of a method to linearize the quadratic assignment problem
| Autor: | Elias Munapo |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
Quadratic assignment problem Computer science 020209 energy 0211 other engineering and technologies Energy Engineering and Power Technology 02 engineering and technology Upper and lower bounds Industrial and Manufacturing Engineering квадратична задача про призначення Koopmans and Beckmann formulation Linearization Management of Technology and Innovation 021105 building & construction 0202 electrical engineering electronic engineering information engineering T1-995 Industry Electrical and Electronic Engineering линейная двоичная форма Technology (General) постановка Купманса-Бекмана Branch and bound Applied Mathematics Mechanical Engineering квадратичная задача о назначениях HD2321-4730.9 Computer Science Applications Dynamic programming linear binary form лінійна двійкова форма quadratic assignment problem Control and Systems Engineering Simulated annealing Heuristics Cutting-plane method |
| Zdroj: | Eastern-European Journal of Enterprise Technologies; Vol. 2 No. 4 (110) (2021): Mathematics and Cybernetics-applied aspects; 54-61 Eastern-European Journal of Enterprise Technologies; Том 2 № 4 (110) (2021): Математика и кибернетика-прикладные аспекты; 54-61 Eastern-European Journal of Enterprise Technologies; Том 2 № 4 (110) (2021): Математика та кібернетика-прикладні аспекти; 54-61 Eastern-European Journal of Enterprise Technologies, Vol 2, Iss 4 (110), Pp 54-61 (2021) |
| ISSN: | 1729-3774 1729-4061 |
| Popis: | The paper presents a new powerful technique to linearize the quadratic assignment problem. There are so many techniques available in the literature that are used to linearize the quadratic assignment problem. In all these linear formulations, both the number of variables and the linear constraints significantly increase. The quadratic assignment problem (QAP) is a well-known problem whereby a set of facilities are allocated to a set of locations in such a way that the cost is a function of the distance and flow between the facilities. In this problem, the costs are associated with a facility being placed at a certain location. The objective is to minimize the assignment of each facility to a location. There are three main categories of methods for solving the quadratic assignment problem. These categories are heuristics, bounding techniques and exact algorithms. Heuristics quickly give near-optimal solutions to the quadratic assignment problem. The five main types of heuristics are construction methods, limited enumeration methods, improvement methods, simulated annealing techniques and genetic algorithms. For every formulated QAP, a lower bound can be calculated. We have Gilmore-Lawler bounds, eigenvalue related bounds and bounds based on reformulations as bounding techniques. There are four main classes of methods for solving the quadratic assignment problem exactly, which are dynamic programming, cutting plane techniques, branch and bound procedures and hybrids of the last two. The QAP has application in computer backboard wiring, hospital layout, dartboard design, typewriter keyboard design, production process, scheduling, etc. The technique proposed in this paper has the strength that the number of linear constraints increases by only one after the linearization process. В статье представлен новый действенный метод линеаризации квадратичной задачи о назначениях. В литературе существует огромное количество методов, которые используются для линеаризации квадратичной задачи о назначениях. Во всех этих линейных формулировках значительно увеличивается как количество переменных, так и количество линейных ограничений. Квадратичная задача о назначениях (КЗН) является хорошо известной задачей, в которой множество объектов назначается множеству расположений таким образом, что затраты являются функцией расстояния и потока между объектами. В этой задаче затраты связаны с размещением объекта в определенном месте. Цель состоит в том, чтобы свести к минимуму назначение каждого объекта определенному месту. Существует три основные категории методов решения квадратичной задачи о назначениях. К этим категориям относятся эвристические методы, ограничивающие методы и точные алгоритмы. Эвристические быстро дают почти оптимальные решения квадратичной задачи о назначениях. Пять основных типов эвристических методов включают методы построения, методы ограниченного перечисления, методы улучшения, методы имитации отжига и генетические алгоритмы. Для каждой сформулированной КЗН может быть рассчитана нижняя граница. Существуют границы Гилмора-Лоулера, границы собственных значений и границы, основанные на переформулировках в качестве методов ограничения. Существует четыре основных класса методов для точного решения квадратичной задачи о назначениях, а именно динамическое программирование, методы секущих плоскостей, методы ветвей и границ и гибриды последних двух. КЗН находит применение в проводке задней панели компьютера, планировке больниц, дизайне мишени для игры в дартс, дизайне клавиатуры типа пишущей машинки, производственных процессах, планировании и т.д. Преимуществом метода, предложенного в данной статье, является то, что в результате процесса линеаризации количество линейных ограничений увеличивается только на единицу У статті представлено новий дієвий метод лінеаризації квадратичної задачі про призначення. У літературі існує величезна кількість методів, які використовуються для лінеаризації квадратичної задачі про призначення. У всіх цих лінійних формулюваннях значно збільшується як кількість змінних, так і кількість лінійних обмежень. Квадратична задача про призначення (КЗП) є добре відомою задачею, в якій множина об'єктів призначається множині розташувань таким чином, що витрати є функцією відстані і потоку між об'єктами. У цій задачі витрати пов'язані з розміщенням об'єкта в певному місці. Мета полягає в тому, щоб звести до мінімуму призначення кожного об'єкта певному місцю. Існує три основні категорії методів вирішення квадратичної задачі про призначення. До цих категорій відносяться евристичні методи, обмежуючі методи і точні алгоритми. Евристичні швидко дають майже оптимальні рішення квадратичної задачі про призначення. П'ять основних типів евристичних методів включають методи побудови, методи обмеженого перерахування, методи поліпшення, методи імітації відпалу і генетичні алгоритми. Для кожної сформульованої КЗП може бути розрахована нижня межа. Існують межі Гілмора-Лоулера, межі власних значень і межі, засновані на переформулюваннях в якості методів обмеження. Існує чотири основні класи методів для точного вирішення квадратичної задачі про призначення, а саме динамічне програмування, методи січних площин, методи гілок і меж і гібриди останніх двох. КЗП знаходить застосування в проводці задньої панелі комп'ютера, плануванні лікарень, дизайні мішені для гри в дартс, дизайні клавіатури типу друкарської машинки, виробничих процесах, плануванні і т. д. Перевагою методу, запропонованого в даній статті, є те, що в результаті процесу лінеаризації кількість лінійних обмежень збільшується тільки на одиницю |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|