Математическая оптимизация для бизнеса. Часть 1. Пассажирские авиалинии

В рамках серии статей по применению математической оптимизации для решения задач в бизнесе мне хотелось бы кратко, но ёмко раскрыть причины и предпосылки возникновения потребности у бизнеса решений задач такого класса, а также привести конкретные примеры кейсов, которые успешно реализованы в крупнейших компаниях мира. В отдельности каждый кейс заслуживает не менее 50 страниц текста для полноценного описания, я же постараюсь изложить главную суть решений и некоторые технические особенности в формате статей на Хабре. Алгоритмы математической оптимизации относятся к категории Prescriptive – аналитики, наиболее сложного и ценного для бизнеса аналитического сегмента. Данная категория позволяет создавать сложные интеллектуальные системы принятия решения с целью максимизировать экономические, производственные и многие другие KPI в рамках заданных ограничений. Математическая оптимизация имеет своё применение в каждом из видов бизнеса любого масштаба, включая промышленность, производство, розничную торговлю, транспорт и логистика, телеком, агросектор, энергетика, строительство, финансы, банкинг, спорт, кино, медицина, образование и т.д. В текущей статье пойдет речь о задачах в индустрии пассажирских авиалиний.

https://habr.com/ru/companies/axenix/articles/816525/

#математическая_оптимизация #авиалинии #исследование_операций #оптимизация_для_бизнеса #milp #ценообразование #планирование_расписаний #machinelearning #ai

Как мы в 2 раза ускорили решение MILP-проблем за счет ML

Многие задачи, с которыми мы имеем дело при цифровизации производства (неважно какого), – это задачи оптимизации: оптимизация производственного расписания, оптимизация цепочек поставок и размещения объектов, оптимизационное планирование и прочее. Многие из них сводятся к проблемам смешанного линейно-целочисленного типа (MILP – Mixed Integer Linear Problem). Конечно же мы хотим их решать быстрее и эффективнее, поэтому год назад начали разработку ML-модулей для этого. В этой статье мы познакомим вас с концептом одного такого модуля – для упрощения MILP методом обнуления переменных – и расскажем о том, насколько нам удалось с его помощью сократить время работы решателя.

https://habr.com/ru/companies/zyfra/articles/810965/

#MILP #ml #operations_research #blending_models #optimizaiton #решатель #оптимизация #mip #scip #highs

Researchers from MIT and ETH Zurich have developed a new, data-driven machine-learning technique that could be applied to many complex logistical challenges, such as package routing, vaccine distribution, and power grid management

#ai #artificalintelligence #machinelearning #labhorizons #ml #technology #software #MIT #MILP #research #tech #innovation

F. Liu et al., "Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP"¹

The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity 2^ 64.5. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.

#ResearchPapers #IACR #Cryptanalysis #RIPEMD-160 #CollisionAttack #ModularDifference #SignedDifference #MILP
__
¹ https://eprint.iacr.org/2023/277

Oh my 40 might #ML followers, what do you recommend as a good #book on #discrete #optimization?

(all aspects are interesting, from #combinatorics to #continuous #relaxations #integer #programming #ILP #MILP etc)