Анотація. Запропоновано нову схему наближеного лексикографічного пошуку розв’язку багатовимірної булевої задачі про ранець. Основна ідея алгоритму полягає у поступовому визначенні лексикографічного порядку (впорядкування змінних), у якому «якісні» розв’язки задачі належать прямому двосторонньому лексикографічному обмеженню, верхня межа якого є лексикографічним максимумом множини допустимих розв’язків задачі у цьому порядку. Оскільки пошук «якісних» розв’язків у кожному порядку здійснюється на обмеженому лексикографічному інтервалі, запропонований алгоритм названо обмеженим лексикографічним пошуком. Якість роботи наближеного методу обмеженого лексикографічного пошуку досліджується за допомогою розв’язання тестових задач з відомих наборів Beasley та F. Glover–G.A. Kochenberger .

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