Citeseer/An Efficient Hybrid Heuristic Method For The 0-1 Exact K-Item Quadratic Knapsack Problem (2013) 10.1.1.837.6875 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{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> </html…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{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> | {{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>}} | </html>}} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 14:35, 23 ноября 2021
«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 секунд. …»