Программные продукты и системы

Введение. Задачи целочисленного программирования (ЦП) широко применяются в различных отраслях, таких как производство, логистика, экономика, информационные технологии и многих других [1–3]. Их актуальность обусловлена необходимостью оптимизации различных процессов и распределения ресурсов. Являясь частным случаем линейного программирования (ЛП) [4], ЦП имеет достаточно долгую историю [5, 6].

В данной работе развивается идея из [7], где предложен алгоритм для поиска целочисленного решения по аналогии с методом покоординатного спуска [8]. Представленный алгоритм, помимо итеративного округления координат на каждом шаге, проверяет выход за область допустимых решений (ОДР) и при необходимости возвращает текущее решение на ее границу.

Современное состояние  предметной области

Одной из основных проблем при решении задач ЦП до сих пор является их высокая вычислительная сложность. Это обусловлено в основном тем, что точные методы решения данного рода задач, такие как метод отсечений и метод ветвей и границ [9] (также известный как метод Гомори [10]), тратят много вычисли- тельных ресурсов впустую из-за своей природы: решают множество конфигураций одной и той же задачи (тем самым разветвляясь), что экспоненциально увеличивает время выполнения. Кроме того, они полагаются на достаточно затратную операцию нахождения оптимального решения с помощью симплекс-метода [11] на каждом шаге выполнения алгоритма, что приводит к значительным временным затратам.

Для исследования дискретных задач ЦП с логическими переменными имеется метод L-раз- биений [12], который позволяет решать комбинаторные задачи, но не получать численные  решения. С другой стороны, существуют эвристические алгоритмы, такие как поиск с восхождением к вершине [13] и алгоритм имитации отжига [14], являющийся примером метода Монте-Карло, а также другие подходы с применением алгоритмов машинного обучения [15]. Данные методы часто используются для решения задач ЦП из-за их более высокой скорости выполнения по сравнению с точными алгоритмами. Поскольку данные алгоритмы эвристические, в них изначально заложен элемент случайности, поэтому, используя их, приходится делать некоторые допущения в плане точности.

В одной из недавних работ [16] представлен подход к решению задач математического программирования с помощью R-функционального моделирования на основе построения вок- сельных моделей геометрических объектов. Данный подход также увеличивает размерность пространства и в большей степени нацелен на задачи нелинейного программирования. В настоящий момент нет точных сведений  о его работе с задачами ЦП.

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

Алгоритм поиска решения с помощью  итеративного округления координат

В данной статье описывается точный алгоритм для поиска решения задачи ЦП, рассмотрены и экспериментально проверены несколько подходов. Основная идея каждого из них – смещение вглубь ОДР. Это достигается за счет построения луча, смотрящего внутрь ОДР в сторону уменьшения значения целевой функции (при задаче максимизации) и определяющего направление движения при смещении вглубь ОДР. Проверим некоторые предположения, а именно:

– определив новый базис в точке оптимального решения O, можно построить луч, который смотрел бы внутрь ОДР; данный луч можно использовать при смещении вглубь ОДР во время поиска целочисленного решения;

– поочередно округляя каждую из координат точки нецелочисленного оптимального решения O до ближайшего целого числа, можно найти целочисленное решение внутри ОДР.

Во всех случаях строится луч, выходящий из оптимальной точки O, считающейся начальной в данном алгоритме. После этого на построенном луче находится точка P, одна из координат которой является целочисленной. Из этой точки начинается итеративный процесс поиска целочисленного решения. Алгоритм состоит из нескольких шагов.

Определение ближайшего базиса

Для построения луча необходимо определить ближайшие смежные ограничения на точ- ку O. Для этого необходимо решить уравнение ограничений вида

                                              (1)

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

Допустим, даны следующие ограничения:

Тогда можно определить матрицу A и вектор :

После этого, подставив точку оптимально- го нецелочисленного решения  в уравнение (1), получим

Видно, что элементы с номерами k = 1, 2 являются наименьшими (равны 0), а значит, соответствующие ограничения образуют новый базис в точке O (рис. 1):

Новый базис s1s2 будет представлять собой прямоугольную систему координат с осями s1 и s2 соответственно.

Определим прямую функцию перехода от исходного базиса к новому:

                                      (2)

и соответствующую ей обратную функцию перехода из нового базиса к исходному:

где  – преобразуемая точка в исходном базисе;  – вектор k-х свободных членов; M – квадратная матрица перехода к новому базису со строками k из матрицы A:

Построение луча

Наивный метод. В новом базисе M построим вектор  длиной n, где n – число столбцов матрицы M (равное числу измерений). Данный вектор будет определять луч в новом базисе и делить область между ограничениями пополам (рис. 2а). Зная матрицу M и вектор , можно перенести данный луч в исходный базис (рис. 2б), используя уравнение (2). Назовем такой метод построения луча наивным, поскольку простой перенос луча в исход- ный базис не позволяет получить луч, который делил бы ОДР ровно пополам.

Разделение области между ограничениями ровно пополам. Поскольку наивный метод построения луча не позволяет получить такой луч, который делил бы область между базисными ограничениями ровно пополам, необходимо модифицировать метод, с помощью которого строится луч. Это становится особенно заметным, если изменить ОДР, сделав ее более узкой.

Дело в том, что масштаб координатной сетки в новом базисе не равен масштабу в старом. Из-за этого, например, вектор (1,1) в исходном базисе будет перекошен в новом базисе и наоборот. Для избежания этого нужно построить вектор  таким образом, чтобы его координатами был шаг сетки по каждой из базисных осей (в данном случае – s1 и s2).

Шаг сетки базисной оси – это длина нормального вектора ограничения, образующего базис. Допустим, даны ограничения:

Тогда их нормальные векторы равны:

длины этих векторов соответственно:

а вектор, задающий луч в новом базисе, можно определить следующим образом:

Для удобства представления вектор  можно нормализовать:

Определение точки P на луче

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

После этого через полученную точку нужно провести секущие плоскости x1 = 2, x2 = 2, параллельные осям координат, и найти точки пересе- чения Pi между плоскостями и лучом (рис. 3).  Таким образом, получается набор потенциальных начальных точек внутри ОДР, в каждой из которых одна из координат является целочисленной. Затем необходимо выбрать наилучшую точку, рассчитав значения целевой функции f(x) для каждой точки Pi.

Допустим, задана целевая функция , тогда можно найти ее значения:

.

Значение целевой функции для P1 наибольшее, значит, точка P = P1 будет начальной.

Выбор оси координат для округления

После нахождения новой начальной точки  необходимо определить ось, вдоль которой будет происходить смещение. Поскольку у точки P одна из координат уже является целочисленной, выбирается ось координат, по которой из других осей следует двигаться далее. Так как в данном случае всего две оси (x1 и x2) и известно, что координата x1 точки P уже целочисленная, выбора не остается и смещение будет происходить вдоль оси x2.

Смещение точки P вдоль выбранной  оси координат

На первом этапе координата x1 точки P целочисленная, следовательно, нужно округлять по следующей доступной координате – x2. Обозначим точку с округленной координатой как éPù. Перенесем точку éPù в новый базис и обозначим как L(éPù). Одна из ее координат (s2) отрицательная. Это означает, что точка вышла за границы ОДР. Чтобы найти точку на границе ОДР, можно провести прямую между точками P и L(éPù) и найти ее пересечение с осью s1. По- лученную точку обозначим  (рис. 4) и перенесем обратно в исходный базис, обозначив как  – это будет следующей точкой для поиска решения.

Аналогично округлим начальную точку P вниз. Все ее координаты становятся целочисленными и положительными в новом базисе (рис. 5), следовательно, целочисленное решение для данного примера найдено.

После выполнения данных шагов координаты точки P проверяются на целочисленность. Если хотя бы одна из координат не является целочисленной, все шаги повторяются для новой точки P. Целочисленное решение будет най- дено, когда все координаты точки P станут целочисленными. На рисунке 6 представлена общая блок-схема описанного алгоритма.

Непосредственно сама процедура одного смещения точки получает на вход точку P, индекс оси i, вдоль которой происходит смещение, а также направление округления – вверх или вниз. Процедура должна сделать копию точки P в памяти, которую обозначим Q, поскольку в дальнейшем понадобятся измененная точка Q и изначальная точка P. На первом шаге проверяется, является ли i-я координата точки Q целым числом. В случае целого числа производится ее смещение на единицу в положительную сторону вдоль оси i в случае округления вверх или же в отрицательную в случае округления вниз. Если i-я координата точки Q не является целым числом, ее значение округляется либо вверх, либо вниз до ближайшего целого. После этого точки P и Q переносятся в новый базис, найденный в начале итерации  (на первом шаге алгоритма). Обозначим новые точки как PT = L(P) и QT = L(Q).

Затем проверяются значения координат точки QT на неотрицательность. Отрицательное значение указывает на выход за ОДР.  В таком случае осуществляется поиск точки пересечения между прямой PTQT и i-й осью координат в новом базисе. Обозначим данную точку как R и перенесем ее в исходный базис: Q = L-1(R). В результате получим точку Q, которая будет либо смещена на единицу вдоль оси i, либо находиться на границе ОДР на данной оси.

Представим процедуру выполнения одного шага алгоритма на языке программирования Julia:

function make_step(axis, point, rounding_mode = RoundUp)

search_point = copy(point)

rounding_up = rounding_mode == RoundUp

if abs(search_point[axis] -  - round(search_point[axis])) <= 10^-10

search_point[axis] =  = search_point[axis] +  +(rounding_up ? 1 : -1)

else

search_point[axis] = round(search_point[axis], rounding_mode)

end

transformed_point = L(point)

transformed_search_point =  = L(search_point)

if minimum(transformed_search_point) <  < 0

got_out_of_bounds = true

plane_axis = argmin(transformed_search_point)

plane_normal = zeros(length(basis_indices))

plane_normal[plane_axis] = 1.0

search_point_intersection =  =intersect_line_with_plane(

transformed_search_point -  transformed_point,

transformed_point,

plane_normal,

[0.0, 0.0],

)

search_point = Linv(search_point_intersection)

else

got_out_of_bounds = false

end

return (search_point, got_out_of_bounds)

end

Блок-схема данной процедуры изображена на рисунке 7.

Наблюдение 1. Округление  в сторону направления луча

Изменим ОДР, сместив и повернув второе ограничение, и аналогичным образом построим луч, направленный вглубь ОДР. Точка O' необязательно должна находиться внутри ОДР, поскольку через нее проводятся прямые, парал- лельные осям координат и пересекающиеся с лучом, направленным вглубь ОДР. Благодаря этому точка будут находиться внутри ОДР.

Когда луч направлен вниз и влево, округления вверх или вправо, как правило, не дают результата (за исключением, когда базисное ограничение параллельно оси координат).

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

Аналогично для оси x2 стоит руководствоваться знаком второй координаты вектора , определяющей луч. Так, если луч направлен вниз, то значение координаты x2 у него отрицательное, следовательно, округлять координату точки необходимо также вниз. Если луч направлен вверх, то значение координаты x2 у его вектора положительное и округлять координату точки необходимо вверх. Далее представлен процесс выполнения алгоритма поиска решения (рис. 8).

Исследование алгоритма

при узкой ОДР

Изменим задачу так, чтобы ОДР была более узкой, а следовательно, целочисленное решение находилось бы дальше от оптимальной точки O. Из-за этого нужно будет выполнить больше шагов алгоритма, поэтапно округляя точку сначала по одной оси координат, а затем по другой. Используя уже представленный алгоритм, будем выполнять его итеративно до того момента, пока у точки P все координаты не окажутся целочисленными в исходном базисе. На рисунке 9 видно, что точка P как бы отскакивает от ограничений при выходе за пределы ОДР.

Исследование алгоритма  при добавлении третьего ограничения

Введем третье ограничение, которое изменяло бы форму ОДР так, чтобы в ходе выполнения алгоритма точка, находящаяся внутри базиса между двумя ограничениями (s1 и s2), смогла выйти за пределы ОДР. В таком случае проверка на выход из ОДР и возврат точки обратно невозможны, и это приведет к тому, что алгоритм может не сойтись, хотя в текущем случае он находит решение (рис. 10).

Наблюдение 2. Определение  последовательности округления координат

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

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

Таким образом, вектор  указывает, что по оси x1 (первый элемент вектора) округлять нужно вниз (то есть влево на графике), как и по оси x2 (второй элемент вектора) (то есть вниз на графике). Например, если бы вектор  содержал значения с разными знаками, округлять стоило бы в направлении знака по соответствующим осям координат, поскольку именно в ту сторону направлен луч:

В таком случае округлять по осям x1 и x3 необходимо было бы вверх, а по оси x2 – вниз.

Исследование алгоритма при изменении направления луча

Изменим ОДР, повернув ограничение s2 так, чтобы луч смотрел не влево, а вправо. Тем самым продемонстрируем несостоятельность текущего способа построения луча, поскольку в таком случае алгоритм никогда не сойдется и целочисленное решение, лежащее внутри ОДР, не будет найдено (рис. 11).

Заключение

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

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

Список литературы

1.      Баусова З.И., Гамазина А Н., Дугина Ю.Н., Старикова А.Ю. Решение задач целочисленной линейной оптимизации // Вестн. ПензГУ. 2017. № 4. С. 117–121.

2.      Арженовский С.В., Синявская Т.Г., Рудяга А.А. Решение задачи целочисленной оптимизации для фирмы // Учет и статистика. 2017. № 4. С. 36–43.

3.      Легков К.Е., Нестеренко О.Е. Алгоритм формирования информационной структуры параллельных программ иерархической вычислительной системы // Наукоемкие технологии в космических исследованиях Земли. 2017. Т. 9. № 1. С. 52–59.

4.      Гальмукова И.А. Линейное программирование в задачах экономики // Социально-экономические проблемы развития предпринимательства: региональный аспект: материалы VI Междунар. конф. 2017. С. 333–338.

5.      Абдуахадов А.А. Краткая история развития математического программирования // Проблемы науки. 2021. № 6. С. 6–8.

6.      Ямашкин Ю.В., Новокрещенова О.А. Системный подход к организации. Саранск, 2016. 195 с.

7.      Матвеев Ю.Н., Иванов А.В. Использование метода покоординатного спуска для поиска решения задачи целочисленного программирования // Вестн. ТвГТУ. Сер. Технич. науки. 2023. Т. 17. № 1. С. 53–62.

8.      Пинягина О.В. Метод покоординатного спуска для задачи рыночного равновесия с ценовыми группами // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. 2018. Т. 160. № 4. С. 718–730.

9.      Мельников Б.Ф., Мельникова Е.А. О классической версии метода ветвей и границ // Компьютерные инструменты в образовании. 2021. № 1. С. 21–44. doi: 10.32603/2071-2340-2021-1-21-45.

10.    Смагин Б.И., Машин В.В. Критический анализ решения задачи целочисленного линейного программирования методом Гомори // Наука и образование. 2022. Т. 5. № 1. URL: http://opusmgau.ru/index.php/see/article/view/4520/4552 (дата обращения: 13.04.2023).

11.    Якубова У.Ш., Парпиева Н.Т., Мирходжаева Н.Ш. Некоторые применения графического и симплексного методов решения задач линейного программирования // Бюллетень науки и практики. 2022. Т. 8. № 4. С. 490–498. doi: 10.33619/2414-2948/77/57.

12.    Адельшин А.В., Кучин А.К. Исследование L-структуры многогранника смешанной задачи максимальной выполнимости // ПДМ. 2017. № 38. С. 110–118. doi: 10.17223/20710410/38/9.

13.    Атутова Н.Д. Применение эвристических методов для поиска булевых функций с криптографическими характеристиками // Прикладная дискретная математика. Приложение. 2022. № 15. С. 18–21. doi: 10.17223/2226308X/15/5.

14.    Максимова Н.Н., Колтунов Н.С. Поиск оптимального кольцевого маршрута на карте г. Благовещенска с использованием алгоритма имитации отжига // Вестн. АмГУ. 2020. № 91. С. 3–8. doi: 10.22250/jasu.1.

15.    Хамхоева Ф.Я. Нейронные сети в экономическом анализе: плюсы и минусы // Norwegian J. of Development of the Int. Sci. 2020. Т. 4. № 51. С. 72–75.

16.    Толок А.В., Толок Н.Б. Решение задач математического программирования функционально-воксельным методом // Проблемы управления. 2017. № 3. С. 37–42.

References

1.      Bausova, Z.I., Gamazina, A.N., Dugina, Yu.N., Starikova, A.Yu. (2017) ‘Solving integer linear optimization problems’, Vestn. of Penza State University, (4), pp. 117–121 (in Russ.).

2.      Arzhenovskiy, S.V., Sinyavskaya, T.G., Rudyaga, A.A. (2017) ‘Solving an integer optimization problem for a company’, Accounting and Statistics, (4), pp. 36–43 (in Russ.).

3.      Legkov, K.E., Nesterenko, O.E. (2017) ‘The algorithm for forming the information structure of parallel programs of a hierarchical computing system’, High Tech in Earth Space Research, 9 (1), pp. 52–59 (in Russ.).

4.      Galmukova, I.A. (2017) ‘Linear programming in economics’, Proc. 6th Int. Conf. Social and Economic Problems of Entrepreneurship Development: Regional Aspect, pp. 333–338 (in Russ.).

5.      Abduakhadov, A.A. ‘Brief history of mathematical programming development’, Problems of Sci., 2021, (6), pp. 6–8 (in Russ.).

6.      Yamashkin, Yu.V., Novokreshchenova, O.A. (2016) A Systematic Approach to the Organization. Saransk, 195 p. (in Russ.).

7.      Matveev, Yu.N., Ivanov, A.V. (2023) ‘Usage of coordinate descent algorithm in search of a solution to an integer programming problem’, Vestn. of TvSTU. Ser. Tech. Sci., 17(1), pp. 53–62 (in Russ.).

8.      Pinyagina, O.V. (2018) ‘A coordinate descent method for market equilibrium problems with price groups’, Uchenye Zapiski Kazanskogo Universiteta. Ser. Fiziko-Matemat. Nauki, 160 (4), pp. 718–730 (in Russ.).

9.      Melnikov, B.F., Melnikova, E.A. (2021) ‘On the classical version of the branch and bound method’, Computer Tools in Education, (1), pp. 21–44 (in Russ.). doi: 10.32603/2071-2340-2021-1-21-45.

10.    Smagin, B.I., Mashin, V.V. (2022) ‘Critical analysis of the solution of the problem of integer linear programming by the Gomori method’, Sci. and Education, 5 (1), available at: http://opusmgau.ru/index.php/see/article/view/4520/4552 (accessed April 13, 2023) (in Russ.).

11.    Yakubova, U.Sh., Parpieva, N.T., Mirkhodzhaeva, N.Sh. (2022) ‘Some applications of graphical and simplex methods for solving linear programming problems’, Bull. of Sci. and Pract., 8 (4), pp. 490–498 (in Russ.). doi: 10.33619/2414-2948/77/57.

12.    Adelshin, A.V., Kuchin, A.K. (2017) ‘Analysis of L-structure of polyhedron in the partial max sat problem’, Applied Discrete Math., (38), pp. 110–118 (in Russ.). doi: 10.17223/20710410/38/9.

13.    Atutova, N.D. (2022) ‘Application of heuristic methods to search for Boolean functions with good cryptographic characteristics’, Applied Discrete Math. Supplement, (15), pp. 18–21 (in Russ.). doi: 10.17223/2226308X/15/5.

14.    Maksimova, N.N., Koltunov, N.S. (2020) ‘Search for an optimal ring route on the Blagoveshchensk map using the annealing simulation algorithm’, Messenger AmSU, (91), pp. 3–8 (in Russ.). doi: 10.22250/jasu.1.

15.    Khamkhoeva, F.Ya. (2020) ‘Neural networks in economic analysis: Pros and cons’, Norwegian J. of Development of the Int. Sci., (51)4, pp. 72–75 (in Russ.).

16.    Tolok, A.V., Tolok, N.B. (2017) ‘Mathematical programming problems solving by functional voxel method’, Problemy Upravleniya, (3), pp. 37–42 (in Russ.).