Прямой метод отсечений для задач комбинаторной оптимизации с дополнительными ограничениями

Abstract

Запропоновано та обґрунтовано прямий метод відсікання для розв’язування комбінаторних задач оптимізації на полірозміщеннях з додатковими обмеженнями. Метод не дозволяє будувати лінійну оболонку множини полірозміщень і отримувати на кожному етапі допустимий розв’язок.

A direct pruning method to solve combinatorial optimization problems on polyarrangements with additional constraints is proposed and substantiated in the paper. The method allows obtaining a feasible solution at each stage without constructing the linear hull of the set of polyarrangements.