Citeseer/An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875
«An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875»скачать
Большинство случаев этой NP-трудной задачи с более чем сорока переменными не могут быть решены в течение одного часа с помощью коммерческого программного обеспечения, такого как CPLEX 12.1.
Поэтому мы предлагаем быстрый и эффективный эвристический метод, который позволяет получить как хорошие нижние, так и верхние границы стоимости задачи за разумное время. В частности, он включает объединяет первичную эвристику и фазу редукции полудефинитного программирования в рамках суррогатной двойной эвристики.
Большие вычислительные эксперименты над случайно сгенерированными экземплярами, содержащими до 200 переменных, подтверждают актуальность границ, полученных нашей гибридной двойственной эвристикой, которая дает известные оптимумы (и доказывает оптимальность) в 90% (или 76%) в среднем за 100 секунд. …»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.