Груздева Т.В., Стрекаловский А.С. Задачи о клике и невыпуклая оптимизация

Новосибирск: Наука, 2014. — 202 с. — ISBN 978-5-02-019183-9.Для поиска в простом неориентированном графе полного подграфа (клики) с максимально возможным количеством вершин или полного подграфа максимально возможного веса (максимальной взвешенной клики) предлагается подход, основанный на редукции к непрерывным невыпуклым задачам оптимизации. В полученных непрерывных задачах целевую функцию или ограничения задают функции, представимые в виде разности двух выпуклых (d.c. функции).
Для их решения с учетом свойств задач о клике разработаны новые алгоритмы, базирующиеся на теории глобального поиска в задачах d.c. программирования. Предложены новые методы локального поиска и новый способ построения оценок на вес и мощность клик.
Проведен обширный вычислительный эксперимент на графах из библиотеки DIMACS, демонстрирующий эффективность предлагаемого подхода и его сравнение с некоторыми другими непрерывными методами решения задач о клике.
В приложении приведена теория и методы решения задач d.c. программирования: d.c. максимизации и задач с d.c. ограничением.
Для специалистов в области дискретной и непрерывной оптимизации, а также аспирантов и студентов соответствующих специальностей. На основе отдельных глав монографии могут быть прочитаны курсы лекций для студентов математических факультетов университетов.True PDF