Заголовок | Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках |
Тип публікації | Journal Article |
Рік публікації | 2019 |
Автори | Норкiн, ВІ |
Abbreviated Key Title | Dopov. Nac. akad. nauk Ukr. |
DOI | 10.15407/dopovidi2019.01.016 |
Номер видання | 1 |
Розділ | Інформатика та кібернетика |
Нумерація сторінок | 16-22 |
Дата публікації | 01/2019 |
Мова | Англійська |
Анотація | У роботi метод гiлок i меж/оцiнок (B&B-метод) поширюється на задачi пошуку недомiнованих елементiв у частково або квазiупорядкованій множині. B&B-метод застосовується до задач оптимiзацiї, де допустима множина сама визначається сiмейством квазiпорядкiв. Структура узагальненого B&B-методу є стандартною: вiн включає в себе розбиття на пiдзадачi, оцiнювання пiдзадач i вiдбраковування пiдзадач, але оцiнки пiдзадач вiдрiзняються, вони можуть бути множинами. Для оцiнювання пiдзадач метод використовує впорядкування множин у такому сенсi. Одна множина “менша або дорiвнює” iншій, якщо для будьякого елемента першої множини iснує “бiльший або рiвний” елемент у другiй. У B&B-методi розбиття застосовується до пiдзадач з недомiнованими верхнiми оцiнками. Пiдзадачi з малими верхнiми оцiнками (менше деякої нижньої оцiнки) видаляються. Встановлено збiжнiсть методу до множини всiх недомiнованих елементiв. Прискорення по вiдношенню до переборного пошуку досягається за рахунок групової оцiнки елементiв вихiдного простору. |
Ключові слова | дискретна оптимізація, квазіпорядок, метод гілок та меж, недоміновані розв’язки, частковий порядок |