Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках

ЗаголовокМетод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках
Тип публікаціїJournal Article
Рік публікації2019
АвториНоркiн, ВІ
Abbreviated Key TitleDopov. Nac. akad. nauk Ukr.
DOI10.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дного простору.

Ключові словадискретна оптимізація, квазіпорядок, метод гілок та меж, недоміновані розв’язки, частковий порядок