Аннотация результатов, полученных в 2014 году
Исследованные в 2014 задачи подразделяются на три основные группы: Первую группу составляли: - задачи, связанные с разработкой метаалгоритмов, обеспечивающих повышение гарантированных оценок точности приближенных алгоритмов решения труднорешаемых задач. Разработанный подход опирается на обобщение известного метода мультипликативного изменения весов, стратегии boosting by sampling и игрового подхода к обучению. Предложенный метаалгоритм апробирован при разработке полиномиальных приближенных алгоритмов с рекордными гарантированными оценками точности для задачи MASC-GP(n) об оптимальном обучении в классе корректных кусочно-линейных монотонных решающих правил, основанных на логике голосования большинством голосов (аффинных разделяющих комитетов); - геометрические задачи о полиэдральном отделении конечных подмножеств d-мерного числового пространства наименьшим числом гиперплоскостей в смысле булевых функций, принадлежащих заданному классу Σ. Впервые эта задача (как и само определение полиэдральной отделимости) была сформулирована Н.Мегиддо в работе 1989 г. Задача построения разделяющих семейств гиперплоскостей возникает как в статистическом обучении, в процессе построения корректного коллектива линейных классификаторов, так и в комбинаторной оптимизации, например, в задачах аппроксимации многогранников и задачах так называемого классового покрытия Class Cover. Один из подходов, применяемых при оценке точности приближенных алгоритмов, разрабатываемых для этих комбинаторных задач опирается на эффективно вычисляемые нижние оценки оптимального значения. Для разбиений конечного подмножества Rd на два подмножества, порождаемых произвольными случайными раскрасками, получены доверительные нижние оценки оптимального числа разделяющих гиперплоскостей в предположении, что Σ совпадает либо с классом всех булевых функций от конечного числа аргументов, либо с классом мажоритарных булевых функций. Аппарат доказательства полученных результатов опирается на неравенства концентрации меры Хеффдинга-Чернова. Вторую группу исследованных в проекте задач составили задачи, являющиеся обобщениями классической задачи коммивояжера: задача о нескольких взаимодействующих коммивояжерах, известная под названием Minimum-weight k-Size Cycle Cover Problem (Min-k-SCCP) и задача последовательного обхода мегаполисов с дополнительными ограничениями, например, в виде условий предшествования. В задаче Min-k-SCCP цель состоит в поиске в полном взвешенном ориентированном графе k вершинно-непересекающихся циклов наименьшего суммарного веса, посещающих в совокупности каждую вершину графа в точности один раз. Нами показано, что Min-k-SCCP NP-трудна в сильном смысле как в общем, так и в частных метрической и евклидовой постановках. Показано, что в общем случае задача не допускает полиномиальной аппроксимации с произвольной точностью O(2^n), тем не менее даже в метрическом случае задача принадлежит классу Apx. Поэтому разработка и обоснование алгоритмов с гарантированными оценками точности для различных подклассов задачи представляется актуальной. Для метрического случая Min-k-SCCP разработан 2-приближенный алгоритм с асимптотически достижимой оценкой точности, обобщающий схему аналогичного алгоритма для метрической задачи TSP (совпадающей с Min-1-SCCP) на случай нескольких коммивояжеров. Вопрос, является ли найденная оценка для задачи Min-k-SCCP неулучшаемой в настоящее время остается открытым, однако нами показано, что известный подход Н.Кристофидеса, приводящий в случае TSP к алгоритму с оценкой 3/2, при произвольном k>1 не приводит к успеху. Для евклидовой задачи Min-2-SCCP на плоскости обоснована приближенная полиномиальная схема (PTAS). Трудоемкость полученной схемы совпадает с трудоемкостью PTAS, построенной С.Аророй для евклидовой задачи коммивояжера по порядку величины, и отличается от нее постоянным множителем. В задаче последовательного обхода мегаполисов классическая постановка задачи TSP отягощена дополнительными ограничениями в виде условий предшествования и функциями стоимости, допускающими зависимость от списка заданий. Постановки такого типа могут, в частности, возникать в атомной энергетике при решении проблемы оптимального демонтажа отработавших свой срок энергоблоков, в которой доза облучения зависит не только от геометрического расположения демонтируемых агрегатов, но и порядка их обхода. Труднорешаемость классической задачи коммивояжера, очевидно, сохраняется и в исследуемой задаче обхода мегаполисов, поэтому актуальным остается вопрос разработки приближенных и (или) эвристических алгоритмов, обладающих требуемым быстродействием. Нами исследована возможность сочетания в рамках одной схемы эвристических «глобальных» и точных локальных методов (например, метода оптимальной локальной вставки) с учетом всех дополнительных ограничений. В рамках третьей группы исследовались вопросы оптимальной (относительно заданной метрики) коррекции несобственных задач выпуклого программирования общего вида. Несобственность задачи подразумевает нарушение соотношений двойственности, вызываемое несовместностью прямой и (или) двойственной систем ограничений. Необходимость решения подобных задач возникает, в частности, в анализе данных при построении регрессионных зависимостей при различных априорных ограничениях на настраиваемые коэффициенты и квадратичной или L1-регуляризацией, а также при обучении методом опорных векторов. Полученные результаты в силу их общности справедливы и для перечисленных задач. Фактически, нами показано, что задача обучения восстановлению ridge или lasso регрессии эквивалентна некоторой задаче безусловной минимизации подходящей сильно выпуклой функции. Обоснован итерационный процесс, сходящийся к нормальному решению указанной задачи оптимальной коррекции, получены оценки уклонений от оптимума как по значению, так и по аргументу, обратно пропорциональные величине штрафных коэффициентов. Отдельное внимание было уделено решению практических задач анализа данных. В частности, исследовалась задача идентификации личности по отпечаткам пальцев. В отличие от классической задачи верификации, при решении которой основное внимание принято уделять точности алгоритмов, в задаче идентификации (состоящей в сопоставлении тестируемого отпечатка с заданной базой эталонов), немаловажную роль играет критерий численной эффективности и масштабируемости алгоритмов. Предлагаемый нами подход в целом развивает классическую схему Джейна-Бану, в рамках которой пространство вторичных признаков определяется конечным множеством т.н. контрольных точек (minutiae), т.е. точек нерегулярности семейства папиллярных линий исследуемого отпечатка. Нами предложена схема индексирования эталонных отпечатков, основанная на триангуляции Делоне множества контрольных точек и системе признаков, инвариантных относительно группы преобразований подобия исходного изображения, а также эвристический алгоритм идентификации, базирующийся на данной схеме и сферических кодах Мальтони. Публикации 2014 года Опубликованы 1. Dremin A., Khachay M., and Leshko A. Fingerprint Identification Algorithm Based on Delaunay Triangulation and Cylinder Codes // Springer. Communications in Computer and Information Sciences. 2014, Vol. 436. P. 126--137. 2. Хачай М.Ю., Незнахина Е.Д. Полиномиальная приближенная схема для евклидовой задачи о цикловом покрытии графа // Труды ИММ, 2014, 20, №4, С.297—311. Приняты к печати 3. Khachay M. and Neznakhina K. Approximation of Euclidean k-Size Cycle Cover Problem // Croatian Operational Research Review, 2015, 6, 1. 4. Kobylkin, K.S. Lower bounds for the number of hyperplanes separating two finite sets of points // Proceedings of the Steklov Institute of Mathematics. 2015. Vol. 289. 5. Skarin V.D. On the application of the residual method for the correction of inconsistent problems of convex programming // Proceedings of the Steklov Institute of Mathematics. 2015. Vol. 289. 6. Ченцов А.Г. Беллмановские вставки в задаче маршрутизации с ограничениями и усложненными функциями стоимости // Вестник Удмуртского Университета. Математика. Механика. Компьютерные науки. 2015. Поданы в печать 7. Khachay M. Committee Polyhedral Separability. Complexity and Polynomial Approximation - Machine Learning. 8. Хачай М.Ю., Незнахина Е.Д. Аппроксимируемость задачи о минимальном по весу цикловом покрытии графа - ДАН. 9. Khachay M. and Neznakhina K. Polynomial Time Approximation Scheme for Euclidean Minimum Weight k-Size Cycle Cover Problem - Journal of Global Optimization. Тезисы докладов 10. V. Skarin. Contradictory convex programs: the residual optimal correction method. – In: Optimization and Applications (V Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow, 2014, pp. 181-182. 11. K. Kobylkin. Covering algorithm for the simplest polyhedral separability problem. – In: Optimization and Applications (V Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow, 2014, p. 116. 12. Khachay M. Approximability of Geometric Traveling Salesman Problem and Some its Generalizations. XVI-th Baikal International School-Seminar «Methods of Optimization and Their Applications», 30th of June - 6th of July, 2014, At Olkhon Island, Baikal. Irkutsk: Melentiev Energy Systems Institute SB RAS, Volume: Abstracts. P. 14. 13. Khachay M. and Neznakhina K. Polynomial time approximation schemes for some generalizations of euclidean traveling salesman problem. 16th Baikal International School-Seminar «Methods of Optimization and Their Applications», 30th of June - 6th of July, 2014, Olkhon Island, Baikal. Irkutsk: Melentiev Energy Systems Institute SB RAS. P. 52. 14. Khachay M. and Neznakhina K. Approximation of k-Minimum Hamiltonian Cover Problem. XV International Conference on Operational Research (KOI'14). Sept. 24-26, 2014. Osijek, Croatia. Book of Abstracts. P. 41. 15. Khachay M. and Neznakhina K. k-Minimum Hamiltonian Cycles Problem. Complexity and Approximability. V International Conference `Optimization and Applications' OPTIMA-2014. 28.09 — 04.10.14. Petrovac, Montenegro. Book of Abstracts. P. 112-113. 16. Хачай М.Ю., Незнахина Е.Д. Аппроксимируемость геометрической задачи о нескольких коммивояжерах. 10 Международная конференция «Интеллектуализация обработки информации (ИОИ-2014)». 4-11 октября 2014. Ираклион. Крит. C. 98-99. 17. Ченцов А.Г., Салий Я.В. Неаддитивная задача маршрутизации с условиями предшествования Международная конференция "Алгоритмический анализ неустойчивых задач - 2014", г.Челябинск, 10-14 ноября 2014 С.166-167. Конференции и семинары 1. XVI Байкальская международная школа-семинар "Методы оптимизации и их приложения", 30 июня – 16 июля, 2014, о.Ольхон (пленарный доклад, Хачай М.Ю., секционный доклад, Хачай М.Ю., Незнахина Е.Д.). 2. 15th International Conference on Operational Research (KOI 2014), Osijek, Croatia, September 24-26, 2014. (секционный доклад, Хачай М.Ю.) 3. V International Conference “Optimization and Applications” (OPTIMA-2014), Petrovac, Montenegro, September 28 – October 4, 2014. (пленарный доклад, Хачай М.Ю., Незнахина Е.Д., секционные доклады, Скарин В.Д., Кобылкин К.С.) 4. X Международная конференция “Интеллектуализация обработки информации”, 5-10 октября, 2014, о. Крит, Греция (пленарный доклад, Хачай М.Ю.) 5. Международная конференция “Алгоритмический анализ неустойчивых задач“, 10-14 ноября, 2014, г. Челябинск (пленарный доклад, А.Г. Ченцов) 6. Семинар лаборатории ПреМоЛаб, 15 октября 2014 г., Москва (М.Ю.Хачай) 7. Постоянно действующий семинар отдела математического программирования ИММ УрО РАН "Теория и методы выпуклой и комбинаторной оптимизации, методы оптимальной коррекции несобственных оптимизационных задач, приложения в области распознавания образов, анализа данных и математического моделирования" (http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=38&confid=545)

Аннотация результатов, полученных в 2015 году
Исследования по проекту проводились по следующим трем направлениям. 1. Алгоритмический анализ задач комбинаторной оптимизации, возникающих в рамках подхода к структурной минимизации риска и максимизации обобщающей способности алгоритмов обучения в классе коллективных решающих правил. 2. Вопросы разрешимости, вычислительной сложности и эффективной аппроксимируемости экстремальных задач маршрутизации, являющихся обобщениями классической задачи коммивояжера (TSP) и задачи оптимальной маршрутизации транспорта (VRP). 3. Вопросы оптимальной чебышевской коррекции несобственных (противоречивых, сингулярных) задач выпуклой оптимизации. В 2015 г. были получены новые результаты по всем перечисленным выше направлениям, однако наибольшего продвижения, по-видимому, удалось достичь в части исследования задач оптимальной маршрутизации, где основное внимание было уделено а) вопросам аппроксимируемости задачи о покрытии полного взвешенного графа семейством из k вершинно-непересекающихся циклов наименьшего суммарного веса (Min-k-SCCP), являющейся одновременно обобщением классической задачи коммивояжера (TSP) и специализацией задачи об оптимальной маршрутизации транспорта (VRP). В 2014 г. исполнителями проекта было показано, что задача Min-k-SCCP NP-трудна в сильном смысле при произвольном фиксированном числе маршрутов k и сохраняет труднорешаемость, будучи сформулированной в метрическом или даже конечномерном евклидовом пространстве произвольной фиксированной размерности d>1. Кроме того, было показано, что несмотря на неаппроксимируемость задачи в общем случае (при справедливости гипотезы о несовпадении классов P и NP), в метрическом случае задача Min-k-SCCP обладает 2-приближенным полиномиальным алгоритмом, трудоемкость которого при произвольном k оценивается сверху трудоемкостью соответствующего приближенного алгоритма для метрической задачи коммивояжера. Более того, для постановки задачи Min-2-SCCP на плоскости была обоснована полиномиальная приближенная схема PTAS, обобщающая подход, предложенный С.Аророй для евклидовой задачи коммивояжера. До последнего момента открытым оставался вопрос об аппроксимируемости евклидовой задачи Min-k-SCCP в общем случае, при произвольных фиксированных значениях параметров k и размерности пространства d, на который в 2015 г. удалось получить исчерпывающий ответ. Так, для задачи Min-k-SCCP, сформулированной в d-мерном евклидовом пространстве при произвольной фиксированной размерности d и k=O(log(n)) (т.е., в частности, при произвольном фиксированном размере k циклового покрытия) построена полиномиальная приближенная схема. Учитывая известный факт об отсутствии у данной задачи вполне полиномиальной приближенной схемы, полученный результат в известном смысле завершает цикл работ, посвященных детерминированному подходу к исследованию ее аппроксимируемости. Отметим, что данный результат, вообще говоря, не следует из известных ранее, для его получения авторами разработан новый подход к описанию комбинаторной структуры цикловых покрытий графов. б) обобщенной асимметричной задаче коммивояжера (GATSP), связанной с поиском оптимального (относительно аддитивного и минимаксного критериев) обхода заданных вершинных кластеров в полном взвешенном графе и известной под общим названием задачи обхода мегаполисов; условия исследованных задач были осложнены дополнительными ограничениями предшествования, заданными на множестве кластеров, и зависимостью стоимостей перемещения и внутренних работ (весов дуг и вершин исходного графа) от списков посещенных и (или) не посещенных ранее вершин. Авторами разработаны специализированные схемы динамического программирования, учитывающие зависимость весовых функций от списков посещенных вершин и ограничения предшествования для обоих упомянутых выше оптимизационных критериев. В частности, для аддитивного критерия и системы ограничений предшествования, обобщающей ограничения, введенные Э.Баласом для классической задачи TSP, показано, что построенные точные методы решения задачи GATSP эффективны, обладая полиномиальной трудоемкостью по числу кластеров при установленных соотношениях между параметрами задаваемых частичных порядков, мощностью мегаполисов и числом вершин графа. Более того, показано, что при произвольных фиксированных значениях этих параметров предложенные авторами точные алгоритмы (для NP-трудной в общем случае задачи GATSP) обладают линейной трудоемкостью. в) вопросам обоснования условий адаптивной устойчивости оптимальных решений комбинаторных задач к малым структурным изменениям их постановки. Например, в терминах задачи коммивояжера подобные изменения связаны с добавлением или удалением вершин (и инцидентных им дуг) в исходном графе. Задача комбинаторной оптимизации называется адаптивно устойчивой к заданному типу возмущений, если произвольное оптимальное решение невозмущенной постановки может быть преобразовано в оптимальное решение возмущенной с помощью заданного (эффективного) алгоритма адаптации. Исполнителями проекта обоснованы: критерий адаптивной устойчивости (для абстрактной задачи комбинаторной оптимизации), серия необходимых и достаточных условий адаптивной устойчивости для задачи коммивояжера и обобщенной задачи о назначениях. В рамках направления исследований, находящегося на стыке теории обучения и комбинаторной оптимизации, основное внимание было уделено - адаптации подходов, традиционно используемых в современной вычислительной геометрии в приложении к совершенствованию приближенных алгоритмов для труднорешаемых задач комбинаторной оптимизации. В частности, развивая стратегию мультипликативного изменения весов, известную в статистической теории обучения как boosting by sampling, авторами проекта предложен новый подход к уточнению гарантированных оценок точности приближенных алгоритмов, позволивший получить для ряда комбинаторных задач, связанных с обучением в классе коллективных решающих правил, приближенные алгоритмы с рекордными оценками точности. - задаче отделимости пары конечных множеств точек в евклидовом пространстве минимальным числом гиперплоскостей, возникающей, в частности, в компьютерной графике на этапе сегментации изображений. В связи с труднорешаемостью данной задачи актуальна разработка полиномиальных приближенных алгоритмов и обоснование порогов ее эффективной аппроксимируемости. С точки зрения описания полиномиально разрешимых подклассов данной задачи актуально получение нижних оценок оптимального значения задачи (далее OPT). Хорошо известны: алгоритм Броннимана-Гудрича (1995), обладающий точностью O(log(OPT)), и минимаксные нижние оценки для оптимального значения (Рудаков К.В., 1976, Боланд, Уррутия, 1995). Нами получены следующие результаты: 1) новые детерминированные и вероятностные нижние оценки для оптимального значения задачи об оптимальной отделимости в евклидовом пространстве произвольной фиксированной размерности; 2) нижняя оценка порога аппроксимируемости в классе релаксационных приближенных алгоритмов и эвристический алгоритм с меньшей, чем у алгоритма Броннимана-Гудрича трудоемкостью для задачи на плоскости. В рамках третьего направления исследовались вопросы оптимальной коррекции несобственных задач выпуклого и, в частности, линейного программирования. Так, для несобственных задач линейного программирования предложен новый подход к оптимальной лексикографической коррекции, в основе которого лежит многоступенчатая регуляризация классической функции Лагранжа одновременно по прямым и двойственным переменным. Регуляризованная функция может быть положена в основу формирования новых схем двойственности для задач такого типа. Приведены теоремы сходимости и численной устойчивости метода, дана содержательная интерпретация получаемого обобщенного решения. Отдельное внимание было уделено решению практических задач анализа данных. В частности, исследовалась задача улучшения качества изображений отпечатков пальцев (fingerprint image enhancement problem), актуальность которой подтверждается необходимостью разработки алгоритмов идентификации личности по отпечаткам пальцев, устойчивых как к естественным дефектам папиллярного узора (царапинам, порезам, ожогам и т.п.), так и к артефактам, возникающим на этапе сканирования. Традиционная схема восстановления отпечатка пальца основывается на градиентной аппроксимации поля направлений папиллярных линий и последующей адаптивной фильтрации с использованием банка фильтров Габора. К сожалению, данная схема не лишена недостатков, основной из которых состоит в том, что качество восстановления отпечатка, высокое в областях регулярности поля направлений, существенно деградирует в окрестностях особых точек (minutiae), неточность выявления местоположения и типа которых значительно повышает результирующую погрешность алгоритмов идентификации. Исполнителями проекта предложен новый (в области обработки отпечатков пальцев) подход к улучшению качества их восстановления, комбинирующий ряд классических результатов теории векторного поля: индексы Пуанкаре, аппроксимацию поля в классе полиномов Лежандра и голоморфные преобразования фрагментов восстанавливаемого изображения. Публикации 2015 года Опубликованные статьи 1. Michael Khachay. Committee polyhedral separability: complexity and polynomial approximation. Machine Learning, 2015, Volume 101, issue 1, 231-251. (IF=1.889) 2. Khachai М., Neznakhina E. Approximability of the problem about a minimum-weight cycle cover of a graph. Doklady Mathematics, 2015, Volume 91, No.2, 240-245. (IF=0.375) 3. Evgeny Ivanko. Adaptive stability: general approach and examples. Operational Research, 2015, Volume 15, 437-452. (IF=0.311) 4. Khachai M., Neznakhina E. A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph. Proceedings of the Steklov Institute of Mathematics, 2015, Volume 289, Suppl.1, 111-125. (IF=0.302) 5. Alexander Chentsov, Michael Khachay, Daniel Khachay. Linear Time Algorithm for Asymmetric Generalized Traveling Salesman Problem with Special Precedence Constraints International Conference on Control, Automation, and Artificial Intelligence (CAAI 2015), DESTech Pub. Inc. Lancaster. 2015. 225-229 (WoS) 6. A. G. Chentsov, Ya. V. Salii. A model of “nonadditive” routing problem where the costs depend on the set of pending tasks, Vestnik YuUrGU. Ser. Mat. Model. Progr., 2015, Volume 8, Issue 1, 24–45. (Scopus) 7. Mikhail Yu. Khachay, Maxim Pasynkov. Theoretical Approach to Developing Efficient Algorithms of Fingerprint Enhancement. Communications in Computer and Information Science, 2015, Volume 542, 83-95. (Scopus) 8. Незнахина Е.Д. PTAS для задачи Min-k-SCCP в евклидовом пространстве произвольной фиксированной размерности. Труды института математики и механики, 2015, Том 21, N3, 268-278. 9. Попов Л.Д., Скарин В.Д. Лексикографическая регуляризация и двойственность для несобственных задач линейного программирования. Труды института математики и механики, 2015, Том 21, N3, 279-291. 10. Ченцов А.Г., Хачай М.Ю., Хачай Д.М. Точный алгоритм с линейной трудоемкостью для одной задачи обхода мегаполисов. Труды института математики и механики, 2015, Том 21, N3, 309-317. Принятые к печати 11. Michael Khachay and Katherine Neznakhina. Approximability of the Minimum-weight k-Size Cycle Cover Problem. Journal of Global Optimization (2016 г.) (WoS) Отосланные в печать 12. George Kovács, Alexander Petunin, Jevgenij Ivanko, Nafissa Yusupova. From the First Chess-Automaton to the Mars Pathfinder - Some Relationships - Acta Polytechnica Hungarica. 2016. (WoS) 13. Chentsov A.G., Khachai D.M., Khachai M.Yu. An exact algorithm with linear complexity for a problem of visiting megalopolises — Proc. of the Steklov Institute of Mathematics, 2016. (WoS) 14. Neznakhina E.D. A PTAS for the Min-k-SCCP in a Euclidean space of arbitrary fixed dimension — Proc. of the Steklov Institute of Mathematics, 2016. (WoS) 15. Popov L.D., Skarin V.D. Lexicographic regularization and duality for improper linear programming problems — Proc. of the Steklov Institute of Mathematics, 2016. (WoS) 16. Michael Khachay and Maxim Pasynkov. Modeling of fingerprint ridge orientations using Legendre polynomials — WITPress. UK. 2016. (Scopus) 17. Michael Khachay and Katherine Neznakhina. Polinomial Time Approximation Scheme for the Minimum-weight k-Size Cycle Cover Problem in Euclidean Space of an Arbitrary Fixed Dimension — 8th IFAC conference on Manufacturing modeling, management and control. Troyes. France. 2016 18. Alexander Chentsov, Michael Khachay, and Daniel Khachay. Linear time algorithm for Precedence Constrained Asymmetric Generalized Traveling Salesman Problem — 8th IFAC conference on Manufacturing modeling, management and control. Troyes. France. 2016 Тезисы докладов 19. Alexander Chentsov, Daniel Khachay, Michael Khachay. Linear time algorithm for Generalized Traveling Salesman Problem with precedence constraints of a special type. Optimization and Applications (VI Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow. 2015. 44-45 20. Khachay Michael. Boosting of polynomial time approximation algorithms for committee polyhedral separability Математические методы распознавания образов (ММРО-17). Москва. 2015. 40-41 21. Konstantin Kobylkin. Integrality gap for Hitting Set problem on geometric graphs. Optimization and Applications (VI Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow. 2015. 109-110 22. Michael Khachay, Katherine Neznakhina. Polynomial Time Approximation Scheme for Euclidean Minimum-weight k-Size Cycle Problem on the plane. 28th Conference of the European Chapter on Combinatorial Optimization (ECCO XXVIII - 2015). 2015. 29 23. Mikhail Khachay, Katherine Neznakhina. Polynomial Time Approximation Scheme for Euclidean Minimum-weight k-Size Cycle Cover Problem in R^d. Optimization and Applications (VI Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow. 2015. 104 24. Vladimir Skarin. On an algorithm for optimal correction of inconsistent problems of convex programming. Optimization and Applications (VI Intern. Conf. in Optim. Methods and Appl, Book of Abstracts). Moscow. 2015. 166-167 25. Астафьев Н.Н. Таблица эластичности балансовой модели Леонтьева. Проблемы оптимизации и приложения: VI Междунар. конф., Омск. 2015. 155 26. Незнахина Е.Д., Хачай М.Ю. PTAS для евклидовой задачи Min-k-SCCP на плоскости для произвольных фиксированных значений параметра k>=2. XV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). 2015. 151-152 27. Иванко Е.Е. Задача курьера как эвристика для решения задачи коммивояжера. Проблемы оптимизации и приложения: VI Междунар. конф., Омск. 28 июня - 4 июля 2015 г.: тез. докл. Омск 2015. 124 28. Кобылкин К.С. Оценки числа гиперплоскостей, разделяющих два конечных множества точек. XV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). 2015. 143-144 29. Кобылкин К.С. Нижние границы точности некоторых приближенных алгоритмов для задач полиэдральной отделимости. Проблемы оптимизации и экон. приложения: VI Междунар. конф., Омск. 28 июня - 4 июля 2015: тез. докл. Омск. 2015. 98 30. Попов Л.Д., Скарин В.Д. XV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). 2015. 54-55 31. Астафьев Н.Н. Некоторые подходы к анализу несобственных задач линейного программирования. XV Всероссийская конференция Математическое программирование и приложения (тезисы докладов). 2015. 14-15 32. Скарин В.Д. О сходимости метода невязки для противоречивых задач выпуклого программирования. Проблемы оптимизации и экон. приложения: VI Междунар. конф., Омск, 28 июня - 4 июля 2015 г.: тез. докл. Омск 2015. 74-75 33. Хачай М.Ю. Об эффективной аппроксимируемости задач о кусочно-линейной отделимости. Проблемы оптимизации и экон. приложения : VI Междунар. конф. Омск, 28 июня - 4 июля 2015 г.: тез. докл. Омск. 2015. 82-83 Участие в конференциях 1. XV Всероссийская конференция «Математическое программирование и приложения MPA-2015», Екатеринбург, 2-6 марта 2015 г. - организация, пленарный доклад: Попов Л.Д. и Скарин В.Д.; секционные сообщения: Кобылкин К.С., Незнахина Е.Д. и Хачай М.Ю. 2. IV International Conference `Analysis Images, Social Networks and Texts AIST-2015’, Екатеринбург, 7-11 апреля 2015 г. - участие в организации (Хачай М.Ю. - сопредседатель програмного комитета), пленарный доклад: Хачай М.Ю., секционное сообщение: Хачай М.Ю. и Пасынков М.К. 3. II Международная конференция "Аппроксимация логических моделей, алгоритмов и задач (АЛМАЗ-2015)". Омск, 27 – 30 апреля 2015 г. пленарный доклад: Хачай М.Ю. 4. The 28th Annual Conference of the European Chapter of Combinatorial Optimization (ECCO XXVIII -2015), Italy, Catania, May 28-30б 2015. секционное сообщение: Хачай М.Ю. и Незнахина Е.Д. 5. Workshop of Advanced Systems Analysis dept. at International Institute for Applied System Analysis (IIASA), Austria, Laxenberg, June 25-28б 2015. два пленарных доклада: Хачай М.Ю. 6. VI Международная конференция «Проблемы оптимизации и экономические приложения», Омск, 28 июня – 4 июля 2015 г. секционное сообщение: Кобылкин К.С. 7. International Conference on Control, Automation, and Artificial Intelligence (CAAI'2015), Thailand, Phuket, Aug. 23-24, 2015. секционный доклад: Ченцов А.Г., Хачай М.Ю.и Хачай Д.М. 8. XVII Всероссийская конференция «Математические методы распознавания образов (ММРО-2015)» – Светлогорск, 19 – 25 сентября, 2015. пленарный доклад: Хачай М.Ю. 9. The VIth International Conference Optimization and Applications (OPTIMA-2015) – Черногория, Петровац, 27 сентября – 3 октября, 2015. пленарный доклад: Хачай М.Ю., секционные сообщения: Кобылкин К.С., Нехнахина Е.Д., Скарин В.Д., Ченцов А.Г., Хачай М.Ю. и Хачай Д.М. 10. Постоянно действующий семинар отдела математического программирования ИММ УрО РАН "Теория и методы выпуклой и комбинаторной оптимизации, методы оптимальной коррекции несобственных оптимизационных задач, приложения в области распознавания образов, анализа данных и математического моделирования" (http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=38&confid=545)

Аннотация результатов, полученных в 2016 году
В отчетном году работы по проекту проводились по нескольким направлениям. 1. В рамках первого направления исследовались вопросы аппроксимируемости евклидовой задачи об оптимальной маршрутизации транспорта с ограничением на грузоподъемность транспортных средств (CVRP), а также геометрической обобщенной задачи коммивояжера с кластерами, порождаемыми ячейками регулярной ортогональной сетки (EGTSP-k-GC). Показано, что произвольный приближенный алгоритм A для метрической задачи TSP с точностью аппроксимации r и трудоемкостью T индуцирует полиномиальный алгоритм для метрической задачи CVRP, за время O(T) находящий ее приближенное решение с асимптотической точностью O(1+r) при q=o(n). Кроме того, для произвольного натурального c нами построен (1+1/с)-приближенный алгоритм для евклидовой задачи CVRP с трудоемкостью O(n^2+T+mK^q2^K), где m — число складов (депо), T — трудоемкость вспомогательного приближенного алгоритма A, а число K=K(c,d,r) зависит исключительно от требуемой точности аппроксимации, размерности пространства d и гарантированной оценки точности алгоритма A. Насколько нам известно, возможность построения PTAS для задачи CVRP в конечномерных евклидовых пространствах размерности большей двух удалось обосновать впервые. Для евклидовой обобщенной задачи коммивояжера на сеточных кластерах (EGTSP-k-GC) обоснованы три приближенные схемы как для медленно, так и для быстро растущего числа кластеров k=k(n). Обладая линейными по n оценками трудоемкости, две из них представляют практический интерес и при фиксированном k, несмотря на полиномиальную разрешимость задачи в этом случае, поскольку наиболее эффективный точный алгоритм для данной задачи обладает кубической трудоемкостью, в то время как трудоемкость предложенных схем составляет O(k^2(1/eps)^{2k})+O(n) и 2^O(k+(1/eps)^2)k^5 +O(n), т.е. линейна по n. 2. Второе направление исследований посвящено разработке эффективных методов решения задачи маршрутизации, осложненной дополнительными ограничениями предшествования и динамически изменяющимися транспортными затратами. Предложена новая модификация схемы динамического программирования, разработанной в свое время Хелдом и Карпом для классической задачи коммивояжера. На стыке комбинаторной оптимизации и теории оптимального управления нередки так называемые динамические постановки задачи TSP, в которых часть транспортных издержек и дополнительных ограничений на выбор маршрута (например, в виде ограничений предшествования) могут быть неизвестны заранее и/или зависеть от построения частичного решения. Предложенная нами модификация схемы динамического программирования легко справляется с этими затруднениями, позволяя, тем самым, решать задачи маршрутизации в реальном времени. Кроме того, предложенный подход к распараллеливанию процедуры вычисления «слоев» функции Беллмана позволяет находить оптимальные решения таких задач эффективно. 3. В рамках традиционного для нашего проекта направления исследований, связанного с вопросами вычислительной геометрии показано, что геометрическая задача о пересечении конечного набора прямолинейных отрезков минимальным числом кругов NP-трудна даже в случае, когда отрезки задают множество ребер некоторого метрического графа (триангуляции Делоне или графа Габриеля), а центры кругов расположены близко к вершинам этого графа (vertex guards). Одновременно с доказательством труднорешаемости обоснована W[1]-трудность задачи (влекущая отсутствие эффективных полиномиальных приближенных схем (EPTAS)) при тех же дополнительных условиях. Для частного случая задачи, в котором длина отрезков ограничена сверху kr для некоторой универсальной (для заданного класса конфигураций отрезков) константы k, а r — радиус покрывающих кругов, нами обоснован простой O((1+k)^2)-приближенный алгоритм с субквадратичной трудоемкостью. Построенный приближенный алгоритм опережает наилучший из известных алгоритмов [A. Efrat, M.J. Katz, F. Nielsen, M. Sharir Dynamic data structures for fat objects and their applications, Volume 1272 Lecture Notes in Computer Science pp 297-306] по трудоемкости. 4. Четвертое направление исследований связано с разработкой эффективных процедур оптимальной коррекции и регуляризации несобственных (сингулярных) задач выпуклой оптимизации, возникающих повсеместно при решении задач анализа данных (SVM, topic modeling, LDA и т.п.). Несмотря на обилие практических работ, использующих регуляризирующие итерационные алгоритмы решения оптимизационных задач, описывающих процедуры анализа данных по-прежнему актуальным представляется вопрос теоретического обоснования условий и скорости сходимости методов для различных видов стабилизаторов, в особенности для переопределенных систем ограничений, являющихся стандартными для подобных задач. В 2016 г. нам удалось описать серию итерационных алгоритмов коррекционного типа, развивающих известную схему метода невязки, описать условия его сходимость и найти оценки скорости такой сходимости для класса несобственных задач выпуклой оптимизации достаточно общего вида. Отдельное внимание было уделено построению эффективной схемы лексикографической коррекции пары двойственных несобственных задач линейного программирования, позволяющей успешно моделировать неравнозначность прямых и двойственных ограничений, а также исследованию условий устойчивости «слабого» разрыва двойственности для задач полубесконечной оптимизации. 5. Завершающее направление исследований нашего проекта связано с решением прикладных задач анализа данных. Данные о растительном покрове поверхности Земли являются необходимым компонентом при проведении природоохранной политики и сохранении разнообразия видов, а также при управлении лесными и водными ресурсами, планировании городской и транспортной структуры, планировании мер по предотвращению природных бедствий и смягчению их последствий и, кроме того, при планировании мер по развитию агропромышленного комплекса. В этой связи задача повышения качества глобальных карт растительного покрова представляется важной и актуальной. Современные подходы к решению данной задачи связаны с анализом больших массивов аэрокосмических снимков. Для решения этой задачи разработан эвристический бустинг-подобный алгоритм согласования мнений волонтеров в тернарной краудсорсинговой игре. На материале Geo-Wiki Crowdsourcing Game, предоставленном коллегами из института IIASA (Austria), было проведено численное сравнение разработанного алгоритма с известными (state-of-the-art) методами агрегации мнений волонтеров. По результатам нескольких тестов предложенный нами алгоритм показал наивысшую в среднем точность. Сравнение проводилось на данных, собранных во время краудсорсинговой компании “The Cropland Capture”, в которой участвовало 2783 добровольца на протяжении 6 месяцев. Всего на голосование было вынесено 192613 изображений, которые собрали около 4.5 млн голосов. Нашими коллегами для согласования мнений волонтеров использовалось правило простого большинства, результаты которого совпали с экспертными оценками примерно в 76% случаев. Тестируемые нами алгоритмы позволили повысить процент согласия с мнением экспертов в среднем до 89-90%. Предложенный эвристический подход, основанный на комбинации современных алгоритмов компьютерного зрения и оригинальной процедуры согласования голосов, позволил повысить точность принятых решений до 92%, а для подмножества снимков, набравших более 10 голосов — до 96%. Кроме того, в 2016 г. исполнители гранта продолжили работы по совершенствованию разработанных в прошлом году алгоритмов восстановления отпечатков пальцев (fingerprint image enhancement), повышающих качество результатов их последующего распознавания. Проведенный сравнительный анализ результатов идентификации личности до и после применения разработанных нами в прошлом году алгоритмов восстановления отпечатков пальцев по общедоступным базам NIST и FVC численно подтвердил высокое качество предлагаемых алгоритмов. Развернутое описание разработанных алгоритмов и результаты их численного тестирования оформлены в качестве статьи, которая в ближайшее время будет представлена на рассмотрение в журнал IEEE Trans on Image Proc. Исполнители проекта приняли активное участие в организации двух международных конференций по тематике данного гранта: V International Conference on Analysis of Images, Social networks, and Texts (AIST2016) (http://aistconf.org) - Хачай М.Ю. – co-chair, Бакланов А.П. – pc-member IX International Conference on Discrete Optimization and Operations Research (DOOR2016) (http://math.nsc.ru/conference/door/2016/) – Хачай М.Ю. – pc-member, proc. сo-editor