Как «выжать» максимум из алмаза при помощи математики

Когда бизнес ставит задачу, специалист ищет пути решения, это очевидно. Однако для создания рабочего алгоритма необходимо разобраться не только в математике, но и в деталях производства, которые определяют процесс. В предыдущей статье я уже рассказывал о том, как создавался алгоритм огранки алмазов с точки зрения бизнеса — настало время взглянуть на задачу с точки зрения математики и рассказать, с какими сложностями пришлось столкнуться.

Меня по-прежнему зовут Алексей Тарасов, я математик и уже пятнадцать лет работаю со сложными задачами для бизнеса. В портфеле — многое, от логистики железнодорожных и авиаперевозок до оптимизации продаж и маршрутизации трафика. Среди клиентов — Т-банк, Huawei, РИВЦ-Пулково, КРОК, ТрансКонтейнер, Octonus, WildTeam и крупные ретейлеры.

К тому времени я уже успешно работал с компанией Octonus. В одном обсуждении заказчик обмолвился, что опытные огранщики могут увеличить массу вытачиваемого бриллианта до 1%, немного скашивая грани. Чего не может сделать машина, выполнявшая тогда совсем другой, менее эффективный алгоритм. Однако я был уверен, что смогу создать лучший — и немедленно сказал об этом. После чего мы договорились попробовать, сойдясь на бешеной тогда для меня сумме проекта — один миллион рублей.

Уточню, что алгоритмы планирования огранки бриллиантов существовали, именно их мы и обсуждали изначально, однако работали они с абсолютно симметричными бриллиантами, у которых было несколько степеней свободы. Так они и подбирались.

Чтобы объяснить наглядно, что это значит, вернемся к теории.

Верхняя часть бриллианта — это корона, основная грань короны — площадка. Нижняя часть называется павильон, и эти названия пригодятся для понимания структуры процесса. К примеру, можно менять высоту короны, высоту павильона, размер площадки, высоту клиньев павильона, высоту нижних клиньев короны и толщину рундиста. Всего 6 степеней свободы.

Программа работала относительно просто. Если уже был вписанный в алмаз бриллиант и зафиксировано 12 степеней свободы (6 — это форма бриллианта, 3 — расположение центра бриллианта, и еще 3 — поворот бриллианта (углы Эйлера), а также те 6 степеней, которые я описывал выше, выбиралась одна из этих координат, и ее значение менялось. Скажем, бриллиант поворачивался на определенный угол, или менялась толщина короны.

Далее мы обращались к стандартному алгоритму, который раздувал из центра бриллиант словно воздушный шарик, ровно до момента пока он не врежется в границу алмаза. Этот метод мы так и называли — baloon. И если масса получившегося бриллианта оказывалась выше, то мы переходили в это положение, а если нет, то перебирали остальные варианты. Пробовали по всем 12 координатам во все стороны, и в случае, когда решение улучшить было невозможно, останавливались.

Это довольно примитивный алгоритм, и называется он называется «метод координатного спуска». Те, кому знакомо понятие «градиентный спуск», могут догадаться, что можно двигаться еще дальше, по диагоналям. Но все же этот примитивный алгоритм был качественно написан и буквально «вылизан», а потому реально работал и находил достаточно хорошие решения на практике.

А потому передо мной стояла не только математическая, но и индустриальная задача. И давайте подробнее рассмотрим, каким должен быть идеальный круглый бриллиант — напоминаю, это самый популярный тип огранки.

Из-за четко определенных условий огранки если мы попробуем воспользоваться координатным спуском и, допустим, просто взять и отодвинуть одну грань на 1 микрон, то несколько граней просто не сойдутся в одной точке. И что же получится на выходе? Точно не ограненный бриллиант.

И как же в этом случае двигать грани, да еще и с таким количеством степеней свободы? Для этого придется вернуться к математической модели, состоящей из трех частей: параметризация, ограничение и целевая функция.

Самое важное здесь — переменные. Нам элементарно нужно выразить нужное положение бриллианта, ведь именно это и является огранкой. А исходники бывают очень разными, что делает процесс задавания параметров одним из важнейших при решении. Ведь каждая точка в получившемся пространстве это возможное решение, и не так важно, правильное или неправильное. И теперь из всех этих точек, которых может быть огромное количество, мы ищем одну-единственную — наше лучшее решение.

И это, конечно, нетривиальная задача.

Иногда сразу понятно, как создавать пространство для правильного решения: в школьной задаче мы складываем яблоки, задаем нужный икс, который равен, допустим, 3+2, и спокойно решаем. А как задать пространство решений для многогранника, который, допустим, стоит в каком-то углу? Сделать это можно миллионом разных способов: например, мы начинаем поиск решений с левого края, который попадает в один из углов, а значит, совпадает с какой-то стеной. А можно задать центр многогранника, что потребует полной замены переменных.

Некоторые задачи и вовсе нельзя решить на плоскости. Сразу вспоминается детская, издевательская немного, которая требует из шести спичек сделать четыре треугольника. Как ни раскладывай и ни перекладывай, ничего не сойдется, но стоит только сделать пирамидку — и вот оно, решение. Из двухмерного пространства приходится переходить в трехмерное.

Или наоборот. Возьмем классическую карту мира, ту самую, со школьных уроков географии. Нашу объемную планету мы буквально «загнали» в плоскость, где у каждой точки есть координаты, широта и долгота. Они и будут нашими переменными при поиске определенной точки, нужной для решения задачи. Например, где находится самая высокая точка России.

Стоит, конечно, учитывать, что площади при этом сильно искажаются, но для математики это не всегда важно.

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

Итак, переменные заданы, время перейти к постановке задачи, которая математически записывается именно ограничением. Что-то равно чему-то, или что-то меньше или равно чему-то — определенный предел, суть нашей задачи. «Бриллиант находится внутри алмаза», или «бриллиант не попадает в включение», и даже «бриллиант является выпуклым», все это записывается в виде ограничений. Даже законы природы, которые могут повлиять на результат, нужно отнести именно сюда.

Для простоты сначала взглянем на нейтральный пример. Все мы знаем, что такое судоку — кто-то из читающих эту статью наверняка и увлекается подобными задачками. А в судоку есть однозначное требование, чтобы в каждой клетке была только одна цифра, и в рамках игрового поля она должна встречаться только один раз. Что мы можем сделать, чтобы решить задачу правильно? Обозначить переменные, где каждой цифре будет соответствовать одна заданная нами переменная, от 1 до 9, и добавить условие, что сумма всех переменных должна равняться определенной цифре.

Или, к примеру, возьмем самый обычный мяч, который лежит где-то в комнате. Мы можем написать, что координата X, которую мы примем за центр мяча, должна быть больше нуля — это значит, что эту координату огораживает стена. А еще она меньше или равна пяти, что считается так — с другой стороны мяч огорожен другой стеной. То есть пространство комнаты находится в пределах пяти метров, а мяч элементарно не застрял в стене, ведь расстояние не обозначено как отрицательное.

Теперь давайте внимательнее взглянем на ограничения алгоритма. Главной моей идеей было записать бриллиант и его комбинаторные условия в виде задачи нелинейной непрерывной оптимизации. Итак, есть уравнение плоскости Ax+By+Cz= D (еще можно принять, что A^2+B^2+C^2 =1). Что я делаю: просто нумерую все вершины и грани, а потом завожу переменные для каждой грани A_i, B_i C_i, D_i и для вершин соответственно x_j, y_j, z_j.

Но здесь спрятан еще один очень важный трюк! Существуют два классических представления (выпуклых) многогранников:

Фактически можно было взять всего один набор переменных — например, координаты вершин, — а грани вычислить. Но я был уверен, что такой подход не сработает из-за числовой нестабильности.

Сделаю тут небольшое отступление. Геометрические задачи часто кажутся простыми — даже являются таковыми, если решать их в общем положении. К сожалению, нельзя избавиться от вырожденных ситуаций, когда что-то обнулилось. Скажем, если вы космонавт, и случайно упали на землю в какой-то точке, то вы точно не попадаете на берег, а будете на каком-то расстоянии от берега. Но если вам нужно будет дойти из точки А в точку Б, и одна из них на земле, а другая в море, то берег вы в любом случае пересечете. И если у вас алгоритм не готов к обработке такого частного случая, то он сломается.

Хороший пример — известный случай с самолетами в Израиле, когда они падали над Мертвым морем из-за специфической ошибке в коде. Дело в том, что Мертвое море находится ниже «уровня моря», и когда самолет летел достаточно низко, в программе происходило деление на 0.

Или — возьмем школьную задачу на решение квадратного уравнения ax^2 + bx+ c = 0. Мы знаем, что в зависимости от знака дискриминанта у нас есть три решения: есть два корня, один двойной или 0 корней (или два комплексных). Но на самом деле случаев больше! Если a=0 (вырожденное), то у нас возникает линейное уравнение, в котором будет 1 решение. Если же и линейное уравнение вырожденное, то есть b=0, то у нас будет 0 решений. А если еще и c вырожденное, то подойдет любой x, и у мы получим бесконечное количество решений.

Вот таким образом мы получаем 6 случаев, а не 3.

Есть и более сложная задача — определить, находится ли точка внутри треугольника. И если писать решающий ее алгоритм неаккуратно, то в результате получится более 30 различных случаев. А когда речь заходит о бриллиантах, все становится куда сложнее, и вырожденности уже не избежать.

К примеру, для V-многогранников ситуацией общего положения являются многогранники с треугольными гранями (симплициальные). Здесь можно взять случайные точки и их выпуклую оболочку. Но математически 4 точки не могут случайно попасть в одну плоскость, вероятность этого равна нулю, а потому все грани бриллианта будут только по 3 вершинам. Куб, допустим, в таких условиях не получить.

А для H-многогранников будут получаться простые многогранники — то есть как раз, такие где в вершине сходится ровно 3 ребра. И куб подойдет, а вот октаэдр нет.

Но вернемся к бриллиантам. Этот камень не является ни простым, ни симплициальным многогранником: в нем есть 8-угольная грань и несколько 4-угольных, а также одна вершина, где сходятся 8 ребер, и несколько, где сходится 4 или 5 ребер. Выходит, если мы выразим грани через вершины — или вершины через грани, — то в этих формулах не избежать вырождения ситуации, а значит, они будут давать очень большую погрешность, проводить к падениям и создавать кучу сложностей.

Что же я сделал в итоге? Просто воспользовался двойным набором переменных — и все сработало. Потому что одинарный работает нестабильно. И все же не рекомендую полагаться только на интуицию: да, я оказался прав, но лучше каждый раз делать несколько вариантов и перепроверять их. Конечно, это займет время, зато поможет убедиться в эффективности решения и не только. Но об этом я расскажу чуть ниже.

Эта часть позволяет сформулировать, какой результат мы хотим получить. Увеличить объём или массу камня, добавить нулей к цене или сделать его, например, красивее и аккуратнее. Хороший нейтральный пример для нее — карта рельефа местности. Допустим, перед нами стоит уже упомянутая выше задача: найти на такой карте самую высокую точку России. Граница страны станет в этом случае ограничением, ширина и долгота — координатами, то есть пространством для переменных, а высота — как раз-таки целевой функцией, благодаря которой мы и сможем найти самую высокую точку.

А для решения нашего алгоритма в качестве целевой функции мы возьмем объем.

И при использовании координатного спуска все кажется достаточно простым: берется коэффициент масштабирования и возводится в куб. Но как считается объем многогранника сложной формы, которым является бриллиант?

Можно делать это через определитель Кэли-Менгера или, допустим, через смешанное произведение. Мы выбрали второй вариант, потому что в нем получаем степень 3 вместо 6.

Каждая грань разбивается на треугольники, и берется смешанное произведение трех вершин как векторов. То есть скалярное произведение от векторного (v1, [v2,v3]).

Эта величина будет равна объему параллелепипеда, выходящего из начала координат и как бы «натянутого» на эти три ребра, то есть 6 объемам тетраэдра. Далее суммируем результат по всем граням и получаем общий объем.

Но здесь важно заметить, что объем получается со знаком. Когда мы идем по невидимой стороне от начала координат, то суммируем объем многогранника и конуса до этого многогранника,а когда идем по видимой стороне — вычитаем этот конус. В результате такой конструкции получаем данные нужного нам объема, которые не зависят от того, где находится начало координат. Очень удобно.

Что важно отметить: если мы раскроем все скобки в смешанном произведении, то получим в целевой функции многочлен третьего порядка. И это… плохо. Кто читал повесть «Понедельник начинается в субботу», тот знает, что в науке все делится на линейное и нелинейное. И происходит это потому, что линейное намного проще нелинейного — и практически, и теоретически. Да и численных проблем с нелинейностью гораздо больше. Вот только здесь избавиться от нее никак нельзя. А значит, мы создаем модель уже для нелинейного программирования.

Ограничения тоже становятся билинейными, то есть в этом конкретном случае координаты вершины перемножаются на координаты грани.

А вот если бы мы задавали только переменные вершин, то вместо координат граней нам бы пришлось прописать ограничения на них, а значит, мы бы отметили те самые 4 точки лежащими в одной плоскости, и объем тетраэдра, «натянутый» на них, был бы равен нулю. И что бы мы получили в итоге? Правильно, кривое трилинейное ограничение.

Подобные задачи требуют не только времени и ресурсов, но и готовности постоянно «включать» новые условности, усложняющие решения. К примеру, формальная красота бриллианта далеко не всегда совпадает с реальной, а это один из ключевых факторов, определяющих успешность алгоритма. Что уж говорить о частностях, когда приходится подбирать ограничения для выпуклости бриллианта! Однако и результат получается достойным.

В следующей статье обязательно поделюсь с вами, какие еще условности повлияли на алгоритм — и как именно удалось с ними справиться.