Citeseer/An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875

Ссылки сюда (1) →

«An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875»^{скачать}

« Точная 0-1 задача квадратичного рюкзака из k элементов («E—kQKP») состоит из максимизации квадратичной функции при двух линейных ограничениях: первое — классическое линейное ограничение вместимости; второе — ограничение равенства кардинальности на количество предметов в ранце.

Большинство случаев этой NP-трудной задачи с более чем сорока переменными не могут быть решены в течение одного часа с помощью коммерческого программного обеспечения, такого как CPLEX 12.1.

Поэтому мы предлагаем быстрый и эффективный эвристический метод, который позволяет получить как хорошие нижние, так и верхние границы стоимости задачи за разумное время. В частности, он включает объединяет первичную эвристику и фазу редукции полудефинитного программирования в рамках суррогатной двойной эвристики.

Большие вычислительные эксперименты над случайно сгенерированными экземплярами, содержащими до 200 переменных, подтверждают актуальность границ, полученных нашей гибридной двойственной эвристикой, которая дает известные оптимумы (и доказывает оптимальность) в 90% (или 76%) в среднем за 100 секунд. …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.