Аннотация. Предложена новая схема приближенного лексикографического поиска решения многомерной булевой задачи о ранце. Основная идея алгоритма состоит в постепенном определении лексикографического порядка (упорядочения переменных), в котором «качественные» решения задачи принадлежат прямому двустороннему лексикографическому ограничению, верхняя граница которого — лексикографический максимум множества допустимых решений задачи в этому порядке. Поскольку поиск «качественных» решений в каждом порядке осуществляется на ограниченном лексикографическом интервале, предлагаемый алгоритм назван ограниченным лексикографическим поиском. Качество работы приближенного метода ограниченного лексикографического поиска исследуется с помощью решения тестовых задач из известных наборов Beasley и F. Glover–G.A. Kochenberger .

Ключевые слова: лексикографический порядок, лексикографический максимум, многомерная булева задача о ранце, алгоритм лексикографического поиска .