B&B method for discrete partial order and quasiorder optimizations

Abstract

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-методе разбиение применяется к подзадачам с недоминируемыми верхними границами. Подзадачи с малыми верхними границами (меньше некоторой нижней границы) удаляются. Установлена сходимость метода к множеству всех недоминированных точек. Ускорение по отношению к переборному поиску достигается за счет групповой оценки элементов исходного пространства.