Для поиска глобального решения в невыпуклых конечномерных экстремальных задачах построена оригинальная теория глобального поиска, ядром которой являются новые условия глобальной оптимальности для задач с (d.c.) функциями, представимыми в виде разности двух выпуклых функций. Эти условия связаны с классической теорией, например, с условиями Каруша-Куна-Таккера, используют классическую идею линеаризации, примененную к базовой невыпуклости каждой из рассматриваемых задач, и обладают алгоритмическим (конструктивным) свойством условий оптимальности. Используя это алгоритмическое свойство, удалось построить и доказать сходимость методов глобального поиска, специальных для каждого из четырех (канонических) классов невыпуклых задач математического программирования: выпуклая максимизация (вогнутая минимизация), обратно-выпуклые задачи, d.c. минимизация (задачи с целевыми функциями, представимыми в виде разности двух выпуклых функций), задачи с d.c. ограничением.
Эти принципиальные алгоритмы (стратегии) являются новым и абсолютно оригинальным аппаратом поиска глобального решения в невыпуклых задачах, уже доказавшим свою эффективность. Для каждого из рассматриваемых классов невыпуклых задач предложены новые и модернизированы известные методы локального поиска, доказана их сходимость, и разработаны практические критерии останова. К тому же, установлено, что предельные точки, называемые далее критическими, доставляемые разработанными методами локального поиска, являются не просто классическими стационарами, но обладают некими дополнительными свойствами. Например, являются решениями выпуклых задач, которые являются линеаризованными по базовой невыпуклости исходной невыпуклой задачи; причём, линеаризация происходит в точности в этой же предельной точке. Все эти методы локального поиска протестированы и их эффективность доказана при решении прикладных задач. Кроме того, для некоторых специальных классов задач (например, билинейных) разработаны другие методы локального поиска, учитывающие структуру исследуемой задачи.
Группа под руководством А.С. Стрекаловского имеет опыт решения новых типов задач оптимизации, имеющих мощную практическую базу и рассматриваемых специалистами как новые парадигмы XXI века. Это задачи с иерархической структурой и динамикой, а также задачи эффективного поиска равновесий. Такими задачами являются, например, двухуровневые задачи оптимизации, где объектами поиска являются как оптимистические (иначе, по Штаккельбергу), так и гарантированные решения. Здесь особо отметим роль доказанных так называемых теорем редукции к некоторой одной, или даже к последовательности невыпуклых задач оптимизации, отвечающей поиску того или иного равновесия. Обратим внимание также на рекордно высокую размерность решённых иерархических задач. Например, при поиске гарантированного решения квадратично- линейной задачи было получено решение в задаче размерности 105. Методами, основанными на разработанных условиях глобальной оптимальности, удалось решить квадратично-линейные двухуровневые задачи с оптимистическими решениями размерности 500х500, а также отыскать равновесие Нэша в биматричной игре размерности 1000x1000.
Что касается динамических оптимизационных задач, в области оптимального управления доказаны оригинальные необходимые и достаточные условия глобальной оптимальности в задачах оптимального управления нелинейными системами ОДУ с терминальными (Майера), интегральными (Лагранжа) функционалами, а также с функционалами Больца, из которых в частности вытекает семейство принципов максимума Понтрянина. На основе условий глобальной оптимальности разработаны соответствующие алгоритмы поиска локально и глобально оптимальных процессов управления и проведено их теоретическое обоснование. Вычислительные эксперименты показали высокую эффективность разработанных методов решения невыпуклых задач оптимального управления с квадратичным целевым функционалом и линейной системой ОДУ (фазовая размерность 20, размерность по управлению 20, количество экстремалей Понтрягина около 60 000). Получение условий глобальной оптимальности в таких задачах в форме семейства принципов максимума, зависящих от параметра, связанного с поверхностью уровня выпуклой функции, которая задает невыпуклость, открыло новые перспективы поиска глобальных решений в невыпуклых задачах оптимального управления.
В области дискретной оптимизации предложены новые постановки задач о максимальной и максимальной взвешенной кликах, основанные на редукции к непрерывным невыпуклым задачам с d.c. функциями. Для их решения разработаны новые алгоритмы, базирующиеся на теории глобального поиска в задачах d.c. программирования. Предложены новые методы локального поиска и новый способ построения оценок на вес и мощность клик.
Для решения задачи о p-медиане и связанных с ней задач разработаны новый метод отсекающих плоскостей, а также эвристический метод поиска решений, включающий в себя метод релаксаций Лагранжа для поиска нижних оценок, позволившие работать на полных графах с количеством вершин до 90000. Были также решены задачи о p-медиане с особой структурой, которая характеризуется несвязностью графа. Эффективность предложенного подхода подтверждена численными экспериментами на практических задачах автомобилестроения на графах с более чем 80 тысячами вершин и 6 миллионами дуг. Распараллеливание метода позволило добиться линейного параллельного ускорения времени счета на 8 процессорах. Предложены новые формулировки задач размещения с предпочтениями клиентов и исследованы их полиэдральные свойства. Исследованы приложения подобных двухуровневых моделей в задачах интегративной кластеризации, возникающей в биоинформатики и системной биологии при анализе разнородных биологических данных. Для задач размещения с ограничениями на ресурсы разработан оригинальный подход на основе алгоритма отделения для многогранника задачи о рюкзаке. Этот подход был обобщен для задачи о покрытии множества. С помощью разработанных методов решены задачи транспортной логистики и задачи составления расписания в учебных заведениях.
Построена оригинальная математическая модель и эффективные эвристические методы для задачи диспетчерского управления на многоколейных участках железных дорог. Посредством разработанных алгоритмов решены практические примеры конкурса прикладных железнодорожных задач, поставленных американскими транспортными компаниями. По итогам конкурса, организованного Институтом исследования операций и научного менеджмента (INFORMS RAS), команда с участием И.Л. Васильева завоевала второе место.
1. Построена новая процедура нелокального улучшения для задач ОУ с целевым d.c. функционалом Больца и линейной управляемой системой. В ее основе лежат ранее доказанные необходимые и достаточные условия глобальной оптимальности.
2. Разработан модифицированный алгоритм поиска глобально оптимальных процессов для задач ОУ линейной системой, учитывающий структуру задач, базовая невыпуклость в которых порождается целевым функционалом Больца. Предложенная модификация позволила повысить эффективность работы глобального поиска, что подтверждается результатами вычислительного эксперимента на серии тестовых задач.
3. Разработаны, обоснованы и протестированы оригинальные методы отыскания гарантированных решений в квадратично-линейных задачах двухуровневой оптимизации высокой размерности, базирующиеся на теории глобального поиска в задачах d.c. минимизации. При этом базовая невыпуклость задач включена в целевую функцию посредством штрафа.
4. Разработан новый алгоритм поиска оптимистического решения в квадратично-линейной задаче двухуровневой оптимизации, базирующийся на прямой работе с невыпуклым ограничением.
5. Предложены схемы локального поиска для двухуровневых задач с матричной и биматричной игрой на нижнем уровне на основе их редукции к задачам с d.c. ограничениями.
6. Исследованы свойства выпуклой оболочки (ВО) допустимых точек задачи размещения с предпочтениями клиентов. Доказано, что часть неравенств входящих в исходную линейную формулировку задачи определяет фасеты такой ВО (другими словами, входят в систему с минимальным количеством линейных ограничений, описывающую ВО допустимых точек задачи)
7. Для задачи размещения с предпочтениями клиентов построено новое семейство отсечений (фасетов), и разработан метод поиска нижних оценок оптимального значения целевого функционала, базирующийся на результатах исследования свойств выпуклых оболочек допустимых точек. Проведен вычислительный эксперимент, подтвердивший эффективность предложенного семейства фасетов на серии тестовых примеров, известных из литературы.
8. Исследован вариант нелинейной задачи о p-медиане с предположением, что число открываемых предприятий не фиксировано. На основе свойств лагранжевых релаксаций для этой задачи разработаны методы поиска нижних и верхних оценок оптимального значения целевого функционала, а также эвристический метод решения задачи. Проведен обширный вычислительный эксперимент на серии известных тестовых примеров взятых из литературы, демонстрирующий эффективность разработанного подхода.
1. Проведено сравнительное тестирование ранее разработанного алгоритма решения квадратично-линейной двухуровневой задачи в оптимистической постановке, базирующегося на методе штрафов и стратегии глобального поиска в задачах d.c. минимизации с известным пакетом по решению задач оптимизации KNITRO. Результаты тестирования показали убедительное преимущество разработанного алгоритма по размерности задач, времени работы и качеству получаемых решений.
2. Разработан алгоритм решения квадратично-линейной задачи двухуровневой оптимизации в оптимистической постановке, базирующийся на стратегии глобального поиска в задаче с одним d.c ограничением-равенством.
3. В качестве основы для многометодного программного комплекса по решению квадратично-линейных задач двухуровневой оптимизации в оптимистической постановке разработан биметодный подход к их решению, сочетающий прямое применение теории глобального поиска в задачах с одним d.c. ограничением-равенством, а также метод штрафов и теорию глобального поиска в задачах d.c. минимизации (см. результаты 1 и 2).
4. Разработаны новые методы локального поиска в квадратично-квадратичных и d.c.-квадратичных двухуровневых задачах с оптимистическим решением, сочетающие идеи последовательного решения задачи по группам переменных и линеаризацию по базовой невыпуклости. Исследована сходимость методов. Предложены и обоснованы практические критерии останова.
5. Предложен и обоснован оригинальный метод генерации тестовых квадратично-линейных двухуровневых задач с известными гарантированными решениями. Предложенный метод базируется на идее построения задач произвольной размерности из небольших задач-ядер и позволяет генерировать задачи различной сложности.
6. Произведена и обоснована редукция квадратично-линейных двухуровневых задач в гарантированной постановке к семейству невыпуклых задач математического программирования. Разработан и численно протестирован алгоритм их решения, вытекающий из произведенной редукции.
7. Разработан метод отсечений для поиска новых нижних оценок оптимальных значений в двухуровневой дискретной задаче размещения с предпочтениями клиентов. Основной составляющей метода является алгоритм поиска локально максимальных взвешенных клик, разработанный для задачи о клике в непрерывной невыпуклой оптимизационной постановке. В результате вычислительного эксперимента удалось улучшить известные на настоящий момент нижние оценки оптимального значения для рассмотренной серии тестовых задач. Новые оценки были использованы для разработки точного метода решения исследуемой задачи
8. Произведена и обоснована редукция двухуровневых задач с матричной и биматричной игрой на нижнем уровне к одноуровневым невыпуклым задачам математического программирования с d.c. ограничениями.
9. Для практической задачи учета экономических и экологических факторов в системе взаимодействующих регионов разработана модель в виде задачи двухуровневой оптимизации, где на нижнем уровне из всех решений приемлемых для экологического состояния выбирается то, которое благоприятствует достижению цели максимизации прибыли на верхнем уровне
1. Разработан комплекс программ для поиска оптимистических решений в линейно-линейных и квадратично-линейных задачах двухуровневого программирования (ЗДП). Проведено его тестирование на большом спектре случайно сгенерированных задач различной сложности и размерности.
2. Разработан первый вариант программы по решению линейно-линейных ЗДП на основе алгоритма глобального поиска для задач с d.c. ограничением-равенством. Осуществлено численное сравнение с методикой из п.1.
3. Разработан модифицированный метод глобального поиска в линейно-линейных ЗДП, включающий в себя блоки генетического алгоритма для решения одной из вспомогательных задач.
4. Исследованы взаимосвязи задач математического программирования с двумя классами нелинейных ЗДП в оптимистической постановке: поиск решения в таких задачах эквивалентен решению семейства невыпуклых задач МП специального вида с d.c. целевой функцией. Предложены и обоснованы новые методы локального и глобального поиска в нелинейных ЗДП этих классов.
5. Доказана взаимосвязь ЗДП в пессимистической постановке и задачи поиска оптимистического решения с оштрафованным критерием нижнего уровня. Изучены свойства решений этих задач. Получено обобщение известных результатов на случай связанных переменных верхнего и нижнего уровней.
1. Разработан алгоритм глобального поиска для ЗОУ линейной системой ОДУ с d.c. терминальными функционалами на основе необходимых и достаточных условий глобальной оптимальности. Проведено исследование глобальной сходимости алгоритма.
2. Разработаны программы для решения ЗОУ с линейной системой ОДУ и целевым d.c. терминальным функционалом.
3. Проведено численное тестирование разработанных алгоритмов на семействе построенных тестовых невыпуклых ЗОУ, в которых известно большое количество процессов, удовлетворяющих ПМП, не являющихся решениями. Результаты численного эксперимента показали высокую эффективность алгоритмов.
4. Предложен новый метод локального поиска и доказана его сходимость для задачи оптимального управления (ЗОУ) линейной по состоянию системой ОДУ с интегральным критерием качества, заданным d.c. функцией.
5. Доказаны новые необходимые и достаточные условия глобальной оптимальности для задачи оптимального управления с целевым d.c. интегральным функционалом.
1. Проведен вычислительный эксперимент по сравнению предложенного ранее АГП для решения линейных задач дополнительности с некоторыми специализированными программными средствами на сериях задач.
2. Предложены новые алгоритмы локального и глобального поиска в негладких задачах d.c. минимизации, и доказаны их теоремы сходимости. Разработан программный комплекс по решению задач негладкой d.c. минимизации, который доказал свою эффективность на серии специальных тестовых примеров.
3. Для общей задачи билинейного программирования разработаны три варианта специального метода локального поиска и доказана сходимость этих методов. Разработан программный комплекс по решению билинейных задач общего вида с несвязанными переменными, использующий два варианта метода локального поиска. Проведено успешное тестирование этого алгоритма на тестовых задачах с использованием в качестве подпрограммы всех трех методов локального поиска.
4. Создан программный комплекс по решению биматричных игр использующий два варианта метода локального поиска. В результате подключения в качестве модуля подпрограммы из пакета CPLEX, а также модификации схемы алгоритма, удалось увеличить размерность решаемых задач до 1000x1000.
1. Разработан точный алгоритм отделения для многогранника задачи о рюкзаке. Данный алгоритм использован при реализации метода ветвей и отсечений для решения обобщенной задачи о назначениях и задачи о p-медиане с ограничениями на ресурсы. Проведен вычислительный эксперимент по тестированию предложенного алгоритма на серии тестовых примеров, который показал высокую эффективность по сравнению с известными подходами.
2. Разработан эвристический алгоритм для задачи размещения предприятий с ограничениями на мощность производства. Данный алгоритм позволяет получить как верхнюю и нижнюю оценку оптимального решения задачи.
3. Произведено обобщение непрерывной постановки известной NP-трудной комбинаторной задачи поиска максимальной клики (ЗМК) на графе как непрерывной задачи с d.c. ограничением. Доказана эквивалентность этой постановки и ЗМК.
4. Произведено обобщение результатов, полученных для ЗМК, на задачу о максимальной взвешенной клике (ЗМВК). Проведен вычислительный эксперимент по решению ЗМВК на графах из библиотеки DIMACS.
5. Разработан метод ветвей и отсечений для поиска оптимальных решений в задачах размещения с предпочтениями клиентов, в основе которого лежит метод отсечений для нового семейства правильных неравенств для многогранника данной задачи Вычислительный эксперимент и сравнение с известными результатами подтвердили эффективность разработанного алгоритма.