B&B method for discrete partial order and quasiorder optimizations

• Дата: 2019
• Автор: Norkin, V.I.
• Формат: Стаття
• Мова: English
• Опубліковано: Видавничий дім "Академперіодика" НАН України 2019
• Назва видання: Доповіді НАН України
• Теми: Інформатика та кібернетика
• Онлайн доступ: http://dspace.nbuv.gov.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 назв. — англ.

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.