1
Привет, Я ищу алгоритм приближения для линейного программирования 0-1. В настоящее время алгоритмы аппроксимации, которые я нахожу, должны ослабить интервал, равный [0,1]. Однако моя проблема может лечить только 0 или 1 в качестве решения.0-1 алгоритмы аппроксимации целочисленного линейного программирования
У кого-нибудь есть идеи? Заранее спасибо.
Привет, Крис, ветка с привязкой подходит для меня. Я рассмотрел [пример ветви и границы] (http://wps.prenhall.com/wps/media/objects/1159/1186960/cdrom_modules/module_c.pdf). Временная сложность случая 0-1 представляется экспоненциальной. Я прав? Знаете ли вы некоторые алгоритмы аппроксимации с меньшей временной сложностью? – user811416
, что верно для наихудшего случая. Но производительность ветвей и границ зависит от нескольких аспектов, например правил ветвления или хороших и двойных границ. Это влияние, насколько велико дерево поиска. – Kalle
ОК. Еще раз спасибо. – user811416