Просмотр исходного текста страницы Citeseer/An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875

{{checked|}}
{{citeseerlink|citeseer/An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875|<html>
Точная 0-1 задача квадратичного рюкзака из k элементов («E—kQKP») состоит из максимизации квадратичной функции при двух линейных ограничениях: первое — классическое линейное ограничение вместимости;
второе — ограничение равенства кардинальности на количество предметов в ранце. 
<p>
Большинство случаев этой NP-трудной задачи с более чем сорока переменными не могут быть решены в течение одного часа с помощью коммерческого программного обеспечения, такого как CPLEX 12.1. 
<p>
Поэтому мы предлагаем быстрый и эффективный эвристический метод, который позволяет получить как хорошие нижние, так и верхние границы стоимости задачи за разумное время. В частности, он включает объединяет первичную эвристику и фазу редукции полудефинитного программирования в рамках суррогатной двойной эвристики.
<p>
Большие вычислительные эксперименты над случайно сгенерированными экземплярами, содержащими до 200 переменных, подтверждают
актуальность границ, полученных нашей гибридной двойственной эвристикой, которая дает известные оптимумы (и доказывает оптимальность) в 90% (или 76%) в среднем за 100 секунд.
</html>}}
{{enddiv}}

[[Категория:CiteSeerArticles]]