Труды КНЦ (Технические науки) 2/2022(13).

В общем случае процесс решения задачи методом удовлетворения ограничений можно представить в виде попеременной работы алгоритмов двух типов: распространителей и ветвителей. Распространители, как было описано ранее, жестко привязаны к ограничениям и сокращают домены участвующих в них переменных. При этом, если домен какой-либо переменной сократился в результате работы одного из распространителей, то будут повторно вызваны распространители всех других ограничений, где участвует данная переменная. Так будет продолжаться, пока не случится одна из следующих ситуаций: 1) домены всех переменных сокращены до единственного значения — найдено решение задачи; 2) домены всех переменных перестали меняться — достигнута неподвижная точка, для продолжения решения требуется ветвление, то есть разбиение пространства поиска на части и исследование каждой из частей отдельно; 3) домен какой-либо переменной оказался пуст (из него удалены все значения) — найдено противоречие, то есть решения в данной части пространства поиска нет, нужно перейти к другой его части, то есть откатиться к последней точке ветвления. Ветвление осуществляется специализированным алгоритмом и предназначено для продвижения процесса решения путем разбиения пространства поиска на части. Простейший пример ветвления — принудительное присвоение переменной значения из ее домена. Если это в итоге приводит к противоречию, после возврата к этой точке ветвления выбранное значение удаляется из домена переменной для продолжения поиска решения. Ограничения можно условно разделить на два класса: простые и глобальные. В простых ограничениях заранее известно количество ограничиваемых переменных, например, ограничение a < b ограничивает домены двух переменных. Глобальные же ограничения описывают зависимости на множестве переменных: например, ограничение alldiff(B) на множестве переменных B обязывает все переменные этого множества принимать отличные друг от друга значения, причем количество переменных в B может быть любым. Чаще всего глобальные ограничения можно заменить множеством простых, но на этапе распространения это приведет к постоянному опросу и запуску множества распространителей при самых незначительных изменениях доменов переменных, что занимает дополнительное машинное время. Кроме того, распространители глобальных ограничений намного эффективнее сокращают домены своих переменных, поскольку им доступно больше информации для анализа. Таким образом, от того, каким именно способом будут представлены ограничения, во многом зависит эффективность процесса решения задачи удовлетворения ограничений. Как и в методах линейного программирования, ограничения на объемы добычи кодируются достаточно просто: например, их достаточно легко привести к типовому глобальному ограничению bin-packing. Основную же трудность представляют ограничения на порядок извлечения блоков. Авторами был проведен ряд исследований на эту тему [7, 8], результатом которых оказалась разработка собственного глобального ограничения для описания всех зависимостей карьера этого типа в одном ограничении. На тестовой машине с 32 ГБ оперативной памяти удалось провести расчет решения для задачи размерностью 82000 блоков, что заняло около получаса, а за 5 часов было построено решение для задачи в 525000 блоков. Заключение Проведен краткий аналитический обзор методов решения задачи планирования открытых горных работ. Сделан вывод о преимуществах методов программирования в ограничениях по сравнению с методами линейного программирования при решении задач, имеющих практический интерес. В методах Mixed Integer Linear Programming используется явное представление зависимостей в форме линейных уравнений и неравенств, что предъявляет повышенные требования к объемам оперативной памяти компьютера и не позволяет решать практически значимые задачи планирования открытых горных работ с требуемым уровнем дискретизации модели, то есть с количеством блоков в несколько сотен тысяч. Кроме того, не все ограничения, возникающие в практических задачах, могут быть тривиальным образом преобразованы в линейные уравнения и неравенства. Методы удовлетворения ограничений подразумевают имплицитное представление зависимостей с помощью механизма глобальных ограничений, что позволяет существенно сократить расход оперативной памяти, необходимой для представления рассматриваемой задачи планирования. Труды Кольского научного центра РАН. Серия: Технические науки. 2022. Т. 13, № 2. С. 111-115. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2022. Vol. 13, No. 2. P. 111-115. © Олейник Ю. А., Зуенко А. А., 2022 114