4551
правка
Компоновка схемы: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
== Основные результаты == | == Основные результаты == | ||
Неограниченное оптимальное положение единичной размещаемой вершины, связанной с фиксированными вершинами, может быть найдено за линейное время как медиана смежных позиций [8]. Минимизация неограниченной функции HPWL для нескольких размещаемых вершин может быть сформулирована в виде линейной программы [7, 10]. Для каждого | Неограниченное оптимальное положение единичной размещаемой вершины, связанной с фиксированными вершинами, может быть найдено за линейное время как медиана смежных позиций [8]. Минимизация неограниченной функции HPWL для нескольких размещаемых вершин может быть сформулирована в виде линейной программы [7, 10]. Для каждого <math>e_k \in E_h \;</math> добавляются переменные <math>U_k \;</math> и <math>L_k \;</math> для обозначения верхней и нижней границ. Стоимость <math>e_k \;</math> (только по размерности x) равна разности между <math>U_k \;</math> и <math>L_k \;</math>. Для каждого <math>U_k(L_k) \;</math> имеется <math>p_k \;</math> ограничений в виде неравенств, требующих, чтобы его значение не было больше (меньше) позиции каждой вершины <math>i \in C_k \;</math>. Гиперграф с n вершинами и m гиперребрами представлен линейной программой с n + 2m переменными и 2P ограничениями. | ||
Линейное программирование не отличается высокой масштабируемостью, а интеграция отслеживания ограничений в процесс оптимизации весьма сложна. Также применяются такие подходы, как нелинейная оптимизация и методы на основе разбиения. | Линейное программирование не отличается высокой масштабируемостью, а интеграция отслеживания ограничений в процесс оптимизации весьма сложна. Также применяются такие подходы, как нелинейная оптимизация и методы на основе разбиения. | ||
