Огляд. Метою алгоритму розгалужень і меж є знайти значення x, яке максимізує або мінімізує значення дійсної функції f(x), яка називається цільовою функцією, серед деякого набору S допустимих або кандидатських рішень. Множину S називають простором пошуку, або допустимою областю.
Метод розгалуження та межі використовується в інформатиці для пошуку оптимальних рішень шляхом систематичного дослідження просторів пошуку. Він ефективно розділяє проблему на підпроблеми (розгалуження), а потім оцінює ці підпроблеми, щоб усунути нежиттєздатні варіанти (обмеження).
Огляд розгалуження та межі: для задач мінімізації основна ідея розгалуження та межі полягає в тому, щоб розкласти задачу MILP на розв’язання задач LP (проблеми P) і записати верхню межу (найоптимальніше можливе рішення) та нижню межу. (оптимальний розв'язок лінійної релаксації) вихідної задачі під час розв'язку …
Чотири відомі стратегії пошуку, які використовуються в алгоритмах розгалужень і межевристичний пошук, пошук у глибину, пошук із найкращим зв’язком та пошук у ширину– теоретично порівнюються з точки зору продуктивності отриманих алгоритмів. Евристичний пошук включає інші три як особливі випадки.
Найкраще спочатку вимагає від вас визначити критерій для «найцікавішого рішення для дослідження», що іноді може бути важко/неможливо. Розгалуження та межі цікаві, лише якщо межі, які ви можете поставити на підпроблеми, є значущими/не надто широкими. Це залежить від проблеми, яку ви розглядаєте…
Додатки
- Цілочисельне програмування.
- Нелінійне програмування.
- Проблема комівояжера (TSP)
- Квадратична задача призначення (QAP)
- Проблема максимальної задовільності (MAX-SAT)
- Пошук найближчого сусіда (від Keinosuke Fukunaga)
- Планування потокового цеху.
- Проблема скорочення запасів.