B&B method for discrete partial order and quasiorder optimizations
The paper extends the Branch and Bound (B&B) method to find all nondominated points in a partially or quasiordered space. The B&B method is applied to the so-called constrained partial/quasi order optimization problem, where the feasible set is defined by a family of partial/quasi order co...
Збережено в:
| Опубліковано в: : | Доповіді НАН України |
|---|---|
| Дата: | 2019 |
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/150463 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | B&B method for discrete partial order and quasiorder optimizations / V.I. Norkin // Доповіді Національної академії наук України. — 2019. — № 1. — С. 16-22. — Бібліогр.: 13 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-150463 |
|---|---|
| record_format |
dspace |
| spelling |
Norkin, V.I. 2019-04-07T11:52:41Z 2019-04-07T11:52:41Z 2019 B&B method for discrete partial order and quasiorder optimizations / V.I. Norkin // Доповіді Національної академії наук України. — 2019. — № 1. — С. 16-22. — Бібліогр.: 13 назв. — англ. 1025-6415 DOI: doi.org/10.15407/dopovidi2019.01.016 https://nasplib.isofts.kiev.ua/handle/123456789/150463 519.6 The paper extends the Branch and Bound (B&B) method to find all nondominated points in a partially or quasiordered space. The B&B method is applied to the so-called constrained partial/quasi order optimization problem, where the feasible set is defined by a family of partial/quasi order constraints. The framework of the generalized B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are setvalued. For bounding, the method uses a set ordering in the following sense. One set is "less or equal" than the other set if, for any element of the first set, there is a "greater or equal" element in the second one. In the B&B method, the partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points is established. The acceleration with respect to the enumerative search is achieved through the group evaluation of elements of the original space. У роботі метод гілок і меж/оцінок (B&B-метод) поширюється на задачі пошуку недомінованих елементів у частково або квазіупорядкованій множині. B&B-метод застосовується до задач оптимізації, де допустима множина сама визначається сімейством квазіпорядків. Структура узагальненого B&B-методу є стандартною: він включає в себе розбиття на підзадачі, оцінювання підзадач і відбраковування підзадач, але оцінки підзадач відрізняються, вони можуть бути множинами. Для оцінювання підзадач метод використовує впорядкування множин у такому сенсі. Одна множина “менша або дорівнює” іншій, якщо для будь-якого елемента першої множини існує “більший або рівний” елемент у другій. У B&B-методі розбиття застосовується до підзадач з недомінованими верхніми оцінками. Підзадачі з малими верхніми оцінками (менше деякої нижньої оцінки) видаляються. Встановлено збіжність методу до множини всіх недомінованих елементів. Прискорення по відношенню до переборного пошуку досягається за рахунок групової оцінки елементів вихідного простору. В работе метод ветвей и границ (B&B-метод) распространяется на задачи поиска недоминируемых точек в частично или квазиупорядоченном множестве. B&B-метод применяется к задачам оптимизации, где допустимое множество само определяется семейством квазипорядков. Структура обобщенного B&B-метода является стандартной: он включает в себя разбиение на подзадачи, оценки подзадач и отбраковку подзадач, но оценочные границы отличаются, они могут быть множествами. Для оценивания подзадач метод использует упорядочение множеств в следующем смысле. Одно множество “меньше или равно” другому, если для любого элемента первого множества существует “больший или равный” элемент во втором. В B&B-методе разбиение применяется к подзадачам с недоминируемыми верхними границами. Подзадачи с малыми верхними границами (меньше некоторой нижней границы) удаляются. Установлена сходимость метода к множеству всех недоминированных точек. Ускорение по отношению к переборному поиску достигается за счет групповой оценки элементов исходного пространства. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика B&B method for discrete partial order and quasiorder optimizations Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках Метод ветвей и границ для дискретной оптимизации в частичных или квазипорядках Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
B&B method for discrete partial order and quasiorder optimizations |
| spellingShingle |
B&B method for discrete partial order and quasiorder optimizations Norkin, V.I. Інформатика та кібернетика |
| title_short |
B&B method for discrete partial order and quasiorder optimizations |
| title_full |
B&B method for discrete partial order and quasiorder optimizations |
| title_fullStr |
B&B method for discrete partial order and quasiorder optimizations |
| title_full_unstemmed |
B&B method for discrete partial order and quasiorder optimizations |
| title_sort |
b&b method for discrete partial order and quasiorder optimizations |
| author |
Norkin, V.I. |
| author_facet |
Norkin, V.I. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2019 |
| language |
English |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках Метод ветвей и границ для дискретной оптимизации в частичных или квазипорядках |
| description |
The paper extends the Branch and Bound (B&B) method to find all nondominated points in a partially or quasiordered
space. The B&B method is applied to the so-called constrained partial/quasi order optimization problem,
where the feasible set is defined by a family of partial/quasi order constraints. The framework of the generalized
B&B method is standard, it includes partition, estimation, and pruning steps, but bounds are different, they are setvalued.
For bounding, the method uses a set ordering in the following sense. One set is "less or equal" than the other
set if, for any element of the first set, there is a "greater or equal" element in the second one. In the B&B method,
the partitioning is applied to the parts of the original space with nondominated upper bounds. Parts with small upper
bounds (less than some lower bound) are pruned. Convergence of the method to the set of all nondominated points
is established. The acceleration with respect to the enumerative search is achieved through the group evaluation of
elements of the original space.
У роботі метод гілок і меж/оцінок (B&B-метод) поширюється на задачі пошуку недомінованих елементів
у частково або квазіупорядкованій множині. B&B-метод застосовується до задач оптимізації, де допустима множина сама визначається сімейством квазіпорядків. Структура узагальненого B&B-методу є стандартною: він включає в себе розбиття на підзадачі, оцінювання підзадач і відбраковування підзадач, але
оцінки підзадач відрізняються, вони можуть бути множинами. Для оцінювання підзадач метод використовує впорядкування множин у такому сенсі. Одна множина “менша або дорівнює” іншій, якщо для будь-якого елемента першої множини існує “більший або рівний” елемент у другій. У B&B-методі розбиття застосовується до підзадач з недомінованими верхніми оцінками. Підзадачі з малими верхніми оцінками
(менше деякої нижньої оцінки) видаляються. Встановлено збіжність методу до множини всіх недомінованих
елементів. Прискорення по відношенню до переборного пошуку досягається за рахунок групової оцінки
елементів вихідного простору.
В работе метод ветвей и границ (B&B-метод) распространяется на задачи поиска недоминируемых точек
в частично или квазиупорядоченном множестве. B&B-метод применяется к задачам оптимизации, где допустимое множество само определяется семейством квазипорядков. Структура обобщенного B&B-метода
является стандартной: он включает в себя разбиение на подзадачи, оценки подзадач и отбраковку подзадач,
но оценочные границы отличаются, они могут быть множествами. Для оценивания подзадач метод
использует упорядочение множеств в следующем смысле. Одно множество “меньше или равно” другому,
если для любого элемента первого множества существует “больший или равный” элемент во втором. В
B&B-методе разбиение применяется к подзадачам с недоминируемыми верхними границами. Подзадачи
с малыми верхними границами (меньше некоторой нижней границы) удаляются. Установлена сходимость
метода к множеству всех недоминированных точек. Ускорение по отношению к переборному поиску
достигается за счет групповой оценки элементов исходного пространства.
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/150463 |
| citation_txt |
B&B method for discrete partial order and quasiorder optimizations / V.I. Norkin // Доповіді Національної академії наук України. — 2019. — № 1. — С. 16-22. — Бібліогр.: 13 назв. — англ. |
| work_keys_str_mv |
AT norkinvi bbmethodfordiscretepartialorderandquasiorderoptimizations AT norkinvi metodgiloktameždlâdiskretnoíoptimízaciívčastkovihabokvaziporâdkah AT norkinvi metodvetveiigranicdlâdiskretnoioptimizaciivčastičnyhilikvaziporâdkah |
| first_indexed |
2025-12-07T19:05:37Z |
| last_indexed |
2025-12-07T19:05:37Z |
| _version_ |
1850877503395069952 |