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 o...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2019 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2019
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/150463 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | B&B method for discrete partial order and quasiorder optimizations / V.I. Norkin // Доповіді Національної академії наук України. — 2019. — № 1. — С. 16-22. — Бібліогр.: 13 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862727860343537664 |
|---|---|
| author | Norkin, V.I. |
| author_facet | Norkin, V.I. |
| citation_txt | B&B method for discrete partial order and quasiorder optimizations / V.I. Norkin // Доповіді Національної академії наук України. — 2019. — № 1. — С. 16-22. — Бібліогр.: 13 назв. — англ. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| 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-методе разбиение применяется к подзадачам с недоминируемыми верхними границами. Подзадачи
с малыми верхними границами (меньше некоторой нижней границы) удаляются. Установлена сходимость
метода к множеству всех недоминированных точек. Ускорение по отношению к переборному поиску
достигается за счет групповой оценки элементов исходного пространства.
|
| first_indexed | 2025-12-07T19:05:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-150463 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | English |
| last_indexed | 2025-12-07T19:05:37Z |
| publishDate | 2019 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| 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 |
| spellingShingle | B&B method for discrete partial order and quasiorder optimizations Norkin, V.I. Інформатика та кібернетика |
| title | B&B method for discrete partial order and quasiorder optimizations |
| title_alt | Метод гiлок та меж для дискретної оптимізацiї в часткових або квазiпорядках Метод ветвей и границ для дискретной оптимизации в частичных или квазипорядках |
| 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_short | B&B method for discrete partial order and quasiorder optimizations |
| title_sort | b&b method for discrete partial order and quasiorder optimizations |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/150463 |
| work_keys_str_mv | AT norkinvi bampbmethodfordiscretepartialorderandquasiorderoptimizations AT norkinvi metodgiloktameždlâdiskretnoíoptimízaciívčastkovihabokvaziporâdkah AT norkinvi metodvetveiigranicdlâdiskretnoioptimizaciivčastičnyhilikvaziporâdkah |