Диссертации, представленные на защиту и подготовленные в НИУ ВШЭ

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