Аннотация результатов, полученных в 2017 году
В отчетном году работы по проекту проводились по нескольким направлениям. 1. Первое направление было связано с исследованием вопросов алгоритмического анализа наиболее общего случая обобщенной задачи коммивояжера (GTSP), ее геометрической постановки EGTSP-GC, обобщенной динамической задачи коммивояжера с ограничениями предшествования (DGTSP-PC) и евклидовой постановки задачи об оптимальной маршрутизации с ограниченной грузоподъемностью транспортных средств (CVRP). Для наиболее общей постановки обобщенной задачи коммивояжера (GTSP) - впервые введены понятия квази- и псевдопирамидального маршрутов, обобщающие классическое понятие пирамидального маршрута на случай частичных порядков, задаваемых на множестве вершин графа; - предложен алгоритм построения L-квазипирамидального маршрута минимального (максимального) веса, обладающий трудоемкостью O(4^L n^3), тем самым показано, что задача GTSP принадлежит классу FPT, относительно параметра L; - построен алгоритм поиска оптимального L-псевдопирамидального маршрута с трудоемкостью O(2^L k^{L+4} n^3); таким образом, показано, что задача GTSP принадлежит классу FPT относительно параметров (L,k) и параметра L при k=O(log n). Для евклидовой обобщенной задачи коммивояжера на сетке (EGTSP-GC) - описан нетривиальный полиномиально разрешимый подкласс, соответствующий постановкам задачи, высота сетки в которых не превосходит двух; фактически показано, что в этом случае задача обладает оптимальным 20-квазипирамидальным маршрутом, который может быть найден за время O(n^3). Для динамической задачи коммивояжера с ограничениями предшествования, транспортные затраты которой описывают накопленную дозу радиации в процессе перемещения в радиационных полях, впервые предложена параллельная схема динамического программирования, эффективность которой подтверждена результатами численных экспериментов на вычислительном кластере parallel.uran.ru 2. В рамках второго направления исследовались вопросы эффективной аппроксимируемости геометрических постановок известных взаимно двойственных комбинаторных задач о минимальной системе представителей (Hitting Set Problem, HSP) и о минимальном покрытии конечного множества (Set Cover Problem, SCP). Обоснованы NP- и W[1]-трудность задачи HSP для семейства r-окрестностей отрезков, составляющих множества ребер некоторых важных с точки зрения приложений плоских графов, в частности, для триангуляций Делоне и графов Габриэля. Для общего случая задачи HSP для семейства r-окрестностей отрезков разработан 300-приближенный алгоритм с временной сложностью O(m^4(log m)^2) и затратами памяти O(m^2). Описано семейство частных постановок задачи, включающее постановки, описываемые графами Габриэля, для которых фактор аппроксимации алгоритма снижается до 72. 3. Третье направление исследований состояло в проектировании алгоритмов оптимальной коррекции и регуляризации несобственных задач выпуклой оптимизации. Разработаны новые методы оптимальной коррекции (аппроксимации) несобственных задач (НЗ) линейного и выпуклого программирования (ЛП и ВП), основанные на применении принципов регуляризации некорректных оптимизационных задач с использованием стабилизаторов, порождаемых как евклидовой, так и полиэдральными нормами. Тип выбранной нормы определяет вид штрафной функции, минимизация которой вместе со стабилизирующей добавкой лежит в основе конкретного метода оптимальной коррекции НЗ. Обоснованы условия применимости и установлены оценки скорости сходимости предложенных методов. 4. Завершающее, но не менее важное направление исследований проекта связано с решением прикладных задач анализа данных. В 2017 г. основное внимание было уделено следующим задачам. а) задаче предварительной обработки (сегментации) изображений отпечатков пальцев с целью повышения качества разрабатываемой коллективом системы алгоритмов идентификации личности по биометрическим данным; б) задаче интерпретации результатов краудсорсинговой кампании, проводимой отделом EOS IIASA (Лаксенберг, Австрия); в) многокритериальной оптимизационной задаче, возникающей при проектировании согласованного человеко-машинного интерфейса. Разработана серия новых эвристических алгоритмов сегментации изображений отпечатков пальцев, основанная на комбинировании сверточных нейронных сетей, методов морфологии и разметки областей; высокая точность предложенных алгоритмов обоснована численно на публичных базах отпечатков FVC 2002 и 2004. Исходные коды и результаты тестирования размещены на открытом ресурсе https://github.com/PasynkovMK/ITNT 2018. Разработан эвристический алгоритм построения оптимального человеко-машинного интерфейса; предложенная эвристика является двухуровневой: на первом уровне производится начальная кластеризация методом UPGMA с использованием функции семантической близости; на втором окончательный вид интерфейса формируется специально разработанным методом итеративной кластеризации. Завершен комплекс работ, связанных с предварительной обработкой данных краудсорсинговой кампании PicturePile, проведенной отделом EOS IIASA и связанной с мониторингом сокращения лесных покровов по результатам аэрокосмической фотосъемки; произведены: фильтрация некачественных снимков, разметка обучающего набора снимков, обучением сверточных нейронных сетей, имитирующих экспертную классификацию, сопоставление предоставленных для анализа отпечатков с данными глобального мониторинга, опубликованными исследователями из Университета Мэриленда (картой Хансена). Полученные в 2017 г. результаты опубликованы в работах [1-24] (см. п. 1.7 настоящего отчета) среди которых 14 статей в изданиях, индексируемых WoS и/или Scopus, докладывались на конференциях [1-6] (п. 1.10 отчета) и заседаниях постоянно действующего семинара Отдела математического программирования ИММ им. Н.Н.Красовского УрО РАН (http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=38&confid=545). Участие исполнителей гранта в международных конференциях и семинарах способствовало активному обсуждению полученных результатов с ведущими специалистами в области дискретной и непрерывной оптимизации, исследования операций, распознавания образов и анализа изображений. В 2017 году исполнители проекта приняли активное участие в организации нескольких международных конференций по тематике данного гранта: VI International Conference on Analysis of Images, Social networks, and Texts (AIST2017) (http://aistconf.org), Jul, 27-29, 2017 - Хачай М.Ю. – session co-chair, Бакланов А.П. – PC-member XVII Baikal International Triennual School-Seminar on Methods of Optimization and Their Applications (MOPT2017), Maksimiha, Aug 1-5, 2017 – Хачай М.Ю. - PC member VII International Conference on Optimization and its Applications (OPTIMA2017). Petrovac, Montenegro. Oct 1-6, 2017 – Бакланов А.П., Скарин В.Д., Хачай М.Ю. - PC members Также в 2017 году Незнахиной Е.Д. подготовлена кандидатская диссертация “Эффективные алгоритмы с гарантированными оценками точности для некоторых обобщений задачи коммивояжера”, дата защиты – 24.01.2018.

Аннотация результатов, полученных в 2018 году
Согласно общему плану работ по проекту исследования, проведенные в 2018 г., могут быть условно разделены на несколько основных направлений. 1. Первое направление связано с алгоритмическим анализом комбинаторных задач, обобщающих классическую задачу коммивояжера (TSP) и задачу оптимальной маршрутизации транспортных средств (VRP). Особое внимание было уделено геометрической постановке обобщенной задачи коммивояжера EGTSP-GC, в которой разбиение на кластеры задается ячейками ортогональной сетки, задаче VRP с дополнительными ограничениями на грузоподъемность транспортных средств и временные промежутки обслуживания (CVRPTW) и обобщенной задаче коммивояжера с переменными транспортными издержками и ограничениями предшествования (DGTSP-PC). EGTSP-GC Введенные (исполнителями проекта) в 2017 г. для общей постановки задачи GTSP понятия L-квази- и L-псевдопирамидальных маршрутов распространены на случай порядка, задаваемого сеткой, и показано, что произвольный оптимальный маршрут в задаче EGTSP-GC(h), в которой высота сетки не превосходит h, является L(h)-псевдопирамидальным при L(h)=15 h^3+2h. Как следствие, обоснована гипотеза о полиномиальной разрешимости задачи EGTSP-GC(h) при произвольном фиксированном значении h, а вместе с ней дан положительный ответ на вопрос о полиномиальной разрешимости евклидовой задачи коммивояжера на плоскости при дополнительном условии ограниченности одного из размеров объемлющего прямоугольника, восходящий к классической работе К.Пападимитриу 1977 г. Численное моделирование показало, что с доверительной вероятностью 95% зависимость параметра пирамидальности L от высоты сетки h имеет вид O(h log h), по крайней мере, на сетках размера 500 x h, где h<=30, что позволяет надеяться на уточнение найденной теоретической оценки и, как следствие, повышение производительности предложенных точных алгоритмов. CVRPTW Для задачи впервые разработаны (две) полиномиальные приближенные схемы (PTAS). При произвольных фиксированных значениях грузоподъемности q и числа временных окон p алгоритмы являются эффективными полиномиальными приближенными схемами (EPTAS) с кубической трудоемкостью и сохраняют полиномиальность при q,p=O(log log n) и qp=O((log n)^0.25) соответственно. Сравнивая предложенные алгоритмы друг с другом, отметим, что при последовательной реализации вторая схема опережает первую по производительности (согласно полученным теоретическим оценкам), однако первая схема допускает очевидное распараллеливание. DGTSP-PC Основное внимание уделено постановке DGTSP-PC с нефиксированной начальной (финальной) позицией, принимающей произвольное положение в заданном компактном множестве, влияющее на окончательное значение оптимизационного критерия. Для построенной таким образом двухуровневой задачи оптимизации разработана эффективная схема динамического программирования с элементами параллелизма. Вычислительная эффективность предложенной схемы подтверждена результатами массивного численного тестирования, проведенного на платформе parallel.uran.ru, в том числе в сравнении с известными эвристиками. 2. Второе направление исследований связано с анализом вычислительной сложности и проектированием эффективных приближенных алгоритмов с теоретическими гарантиями по точности и трудоемкости для геометрических постановок задач об оптимальном покрытии (Set Cover) и минимальной системе представителей (Hitting Set). Построена серия приближенных алгоритмов для задачи оптимального пересечения отрезков равными кругами, включая как наиболее общий случай семейств отрезков, пересекающихся не более, чем в своих концевых точках, так и некоторые частные постановки, задаваемые множествами ребер плоских графов, возникающих в приложениях: на обобщенных внешнепланарных графах, триангуляциях Делоне, графах Габриэля, графах относительных окрестностей и др. Предложенные алгоритмы при относительно невысокой трудоемкости обладают рекордной на данный момент точностью. 3. Третье направление исследований состояло в проектировании алгоритмов оптимальной коррекции и регуляризации несобственных задач выпуклой оптимизации. В 2018 г. основное внимание было уделено вопросам равностепенной регуляризации функции Лагранжа одновременно по переменным как прямой так и двойственной задачи, а также совершенствованию схем оптимальной коррекции задач выпуклой оптимизации с несовместной системой ограничений (несобственных задач первого рода). Для двойственной пары задач линейного программирования впервые обоснована схема Тихоновской регуляризации по прямым и двойственным переменным, обеспечивающая одинаковую по порядку величины скорость сходимости аппроксимирующих последовательностей к нормальным оптимальным решениям обеих задач. Обоснованы условия сходимости и найдены оценки ее скорости для обобщенной схемы оптимальной коррекции по правым частям несобственной задачи выпуклой оптимизации первого рода. 4. Завершающее, но не менее важное направление исследований по данному проекту было связано с решением прикладных задач. а) В сотрудничестве с коллегами из отдела Ecosystems Services and Management Международного Института прикладного системного анализа (IIASA), Laxenburg, Austria, разработан автоматический метод мониторинга распространения индустриальных пальмовых плантаций в странах экваториального пояса (Индонезии, Малайзии, Бразилии), непосредственно влияющих на сокращение площадей тропических ливневых лесов и как следствие снижение адсорбции CO2 и глобальное потепление. Независимые методы проведения такого мониторинга связаны с анализом публично доступных спутниковых изображений земной поверхности, получаемых, например, со спутников Landsat, для которых традиционно применяется либо метод экспертной разметки, либо универсальные алгоритмы машинного обучения (SVM, RF, и т.п ). Несмотря на достигнутые успехи, ни один из перечисленных подходов не был свободен от очевидных недостатков. Использование для анализа снимков экспертов недопустимо дорого и не позволяет достичь требуемой производительности. Применение в целях снижения себестоимости анализа краудсорсинговых кампаний порождает ряд дополнительных проблем, например, в области оценки достоверности получаемых данных. Использование же традиционных алгоритмов обучения, не специализированных для решения задач анализа изображений, приводит к существенному снижению качества прогнозов. Предложенный подход основан на редукции задачи мониторинга площадей пальмовых плантаций к задаче семантической сегментации спутниковых изображений и решении последней в классе вполне конволюционных нейронных сетей. Обученная на снимках части о. Калимантан (Индонезия) сеть, авторская модификация сети FCN-8s (Shelhamer et al. 2017), обладающая наивысшей в эксперименте обобщающей способностью (OA=0.95), более чем на 9% опередила по качеству алгоритмы, традиционно применяемые для решения данной задачи. б) проблема оптимизации удобства использования (usability) пользовательского интерфейса, реализованного в виде иерархических меню сформулирована в виде подходящей задачи комбинаторной оптимизации, для решения которой предложено использовать оригинальный эвристический алгоритм. Полученные в 2018 г. результаты опубликованы в работах [1-26] (см. п. 1.7 настоящего отчета) среди которых 16 статей в изданиях, индексируемых WoS и/или Scopus, докладывались на конференциях [1-5] (п. 1.10 отчета) и заседаниях постоянно действующего семинара Отдела математического программирования ИММ им. Н.Н.Красовского УрО РАН (http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=38&confid=545). В текущем году исполнители проекта приняли активное участие в организации нескольких международных конференций по тематике данного гранта: 12th International Conference on Learning and Intelligent Optimization (LION`12). June 10-15, 2018, Kalamata, Greece - Хачай М.Ю. – session co-chair, Бакланов А.П. – PC-member 7th International Conference on Analysis of Images, Social Networks, and Texts (AIST 2018). July 5-7, Moscow, Russia — Хачай М.Ю. - session co-chair, Бакланов А.П., Кобылкин К.С., Незнахина Е.Д. - PC-members 7th International Conference on Optimization Problems and their Applications (OPTA 2018), July 8-14, Omsk, Russia — Хачай М.Ю. - PC co-chair, 9th International Conference on Optimization and Applications (OPTIMA 2018), October 1-5, 2018, Petrovac, Montenegro — Бакланов А.П., Хачай М.Ю. - PC members 12th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2018), Atlanta, USA — Хачай М.Ю. - PC member. Участие исполнителей гранта в международных конференциях способствовало активному обсуждению полученных результатов с ведущими специалистами в области дискретной и непрерывной оптимизации, исследования операций, распознавания образов и анализа изображений. 24.01.2018 Е.Д.Незнахиной успешно защищена кандидатская диссертация “Эффективные алгоритмы с гарантированными оценками точности для некоторых обобщений задачи коммивояжера”, диплом серия КНД №043840, приказ №609/нк-21 Подготовлена глава V.D. Mazurov, M.Yu. Khachay “Collective generalized solutions for infeasible systems of constraints and ensemble learning techniques”, содержащая обзор авторских результатов в области комитетных обобщенных решений несовместных систем ограничений, в том числе, полученных ранее в рамках данного проекта. Глава принята к публикации в составе коллективной монографии «Image Analysis and Pattern Recognition: State of the Art in the Russian Federation».