ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

3
Publication date:
13 September 2024

A statistical experiment to test practical convergence in one submodular programming problem

Date of submission article: 24.10.2022
Date after edit article: 13.12.2022
Date of acceptance for publication: 15.12.2022
UDC: 519.7
The article was published in issue no. № 2, 2023 [ pp. 250-256 ]
Abstract:The article discusses a statistical experiment to test practical convergence in a single submodular programming problem. It proposes setting the problem of maximizing the sum of the group assignment effectiveness. The paper introduces the concept of a mixed solution of the transport task of group assignment, when resource constraints are met on average. It is shown that defining mixed solutions to the group assignment transport problem can be reduced to a submodular programming problem, which can be solved by the branch-and-bound method with upper estimates based on the transport problem submodularity with constraints in the form of column equalities. The polynomial nature of the ε-optimal version of the branch-and-bound method has been proved only in relation to the classical scheme for solving the multidi-mensional knapsack problem. We use a scheme that uses the specifics of the problem, therefore, further efforts are needed to test the polynomial hypothesis, including with the help of statistical experiments. The main result of the work is the development of a numerical implementation of the ε-optimal version of the branch-and-bound method in the high-level C++ programming language and conducting a statistical experiment to verify the practical convergence of the algorithm itself based on the statistical transport problem of group assignment by the effectiveness of the assignment. Based on the results of the numerical experiment analysis, it was found that for the problem under consideration, the percentage of vertices revealed during the operation of the ε-optimal algorithm from the total number of vertices in the orgraph decreases quite quickly with increasing dimensionality, which indicates sufficient efficiency of the algorithm. The polynomial hypothesis has not been confirmed, since the authors did not use a classical algorithm for solving an integer problem, but the specifics of the task.
Аннотация:В статье рассматривается cтатистический эксперимент по проверке практической сходимости в одной задаче субмодулярного программирования. Предлагается постановка задачи по максимизации суммы эффективности группового назначения. Вводится понятие смешанного решения транспортной задачи о групповом назначении, когда ресурсные ограничения в среднем выполняются. Показано, что определение смешанных решений транспортной задачи о групповом назначении может быть сведено к задаче субмодулярного программирования, решаемой методом ветвей и границ с верхними оценками, основанными на субмодулярности транспортной задачи с ограничениями в виде равенств по столбцам. Полиномиальность ε-оптимальной версии метода ветвей и границ доказана лишь в отношении классической схемы решения многомерной задачи о рюкзаке. Авторы применили схему, использующую специфику задачи, поэтому для проверки гипотезы полиномиальности необходимы дальнейшие усилия, в том числе и при помощи статистических экспериментов. Основным результатом являются разработка численной реализации ε-оптимальной версии метода ветвей и границ на высокоуровневом языке программирования С++ и проведение статистического эксперимента по проверке практической сходимости самого алгоритма на основании статической транспортной задачи о групповом назначении по эффективности назначения. По результатам анализа численного эксперимента установлено, что для рассматриваемой задачи процент раскрытых в ходе работы ε-оптимального алгоритма вершин от общего числа вершин в орграфе при увеличении размерности убывает довольно быстро, что говорит о достаточной эффективности алгоритма. Гипотеза о полиномиальности не подтвердилась, так как используется не классический алгоритм решения целочисленной задачи, а специфика поставленной задачи.
Authors: Skakodub, K.R. (skakodub03@bk.ru) - Tver State University (Junior Researcher), Tver , Russia, Perevozchikov, A.G. (lesik56@mail.ru) - Tver State University (Associate Professor), Tver , Russia, Ph.D, Lesik, A.I. (pere501@yandex.ru) - RPA RusBITech-Tver JSC (Senior Researcher), Tver , Russia, Ph.D
Keywords: upper bounds of the criterion, branch-and-bound method, polynomial, statistical experiment, mmersion of the original problem into a family of problems, mixed solution, transport problem of group assignment
Page views: 1700
PDF version article

Font size:       Font:

В данной статье рассматривается задача определения оптимальных планов назначения на базе транспортной задачи (ТЗ) о групповом назначении (ГН). В отличие от существующей ТЗ с фиксированными добавками по критерию минимума стоимости [1] предлагается постановка по максимизации суммы эффективности ГН.

В исследовании [2] показано, что ε-оптимальная версия метода ветвей и границ имеет полиномиальную по n оценку ветвлений, однако численная реализация этой версии – непростая задача и ее решение даже при небольшой размерности может потребовать значительных вычислительных ресурсов.

В работе [3] описывается подход к решению многомерной задачи о рюкзаке с помощью модифицированной версии метода ветвей и границ, используя сортировку ранжированных элементов по полезности: отдельные элементы, вероятно, те, что будут частью оптимального решения, фиксируются, а другие, ко-торые навряд ли будут таковыми, больше не рассматриваются (псевдопробелы). В [4] предложен итеративный алгоритм, улучшающий решение задачи путем поиска псевдопробелов. Эти два подхода сравниваются в [4], однако класс задачи при использовании данных алгоритмов остается NP, а в работе [2] установлено, что для некоторого класса задач переход от поиска точного решения к ε-оптимальному позволяет перейти от задачи класса NP к задаче класса P.

В статье [5] рассматривается способ аппроксимации при помощи поиска не более первых k компонент, удовлетворяющих всем требованиям, а затем поиска полиномиальной схемы для аппроксимации по времени.

В работе [6] описано применение этого же подхода, а также установлено, что для фиксированного значения ε-приближенное решение может быть вычислено во времени асимптотически независимо от ограничения мощности, что обеспечивает лучшую временную сложность.

Для проверки гипотезы о полиномиальности ε-оптимальной версии метода ветвей и границ в рассматриваемой задаче использован статистический эксперимент по аналогии с [7]. Была выбрана подходящая модельная задача, согласованы параметры генерации случайных коэфициентов и разработана общая программа решения поставленной задачи при любых значениях коэфициентов, причем для определенности время работы алгоритма ограничено одним часом.

Постановка ТЗ о ГН по эффективности назначения

Пусть, как в обычной ТЗ, i = 1, 2, ..., m обозначает пункты производства некоторого однородного товара, j = 1, 2, …, n – пункты его потребления. Даны величины: Xi > 0 – объем производства в пункте производства i; Yj > 0 – объем потребления в пункте потребления j, отнесенные к одному дню (горизонту планирования).

Найдем величины xij > 0 (объем перевозок из пункта i в пункт j), удовлетворяющие обычным транспортным ограничениям с неуравновешенным балансом:

                    (1)

i Î I = 1, 2, ..., m, j Î J = 1, 2, …, n,

где в общем случае

                                         (2)

и максимизирующие функцию:

                        (3)

где Aij – эффективность назначения i-го типа исполнителей на j-го типа заказчиков.

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

Положим xij = Yjzij. Тогда задача (1)–(3) превратится в многомерную задачу о рюкзаке:

                        (4)

при ограничениях

 i = 1, 2, ..., m,                     (5)

 j = 1, 2, …, n, zij  ≥ 0.                 (6)

Смешанные решения ТЗ о ГН

Предположим, что сумма слева в ограничении (6) равна либо нулю, либо единице, а сами переменные zij могут принимать дробные значения и, таким образом, интерпретироваться как вероятности того, что вся групповая заявка Yj назначается i-му исполнителю. Такое решение назовем смешанным в отличие от классического. Ограничения (5) для смешанного решения выполняются как бы в среднем. Погрузим задачу в семейство задач, отличающихся подмножеством ω  J групповых заявок, выбранных для назначения:

                        (7)

при ограничениях

 i = 1, 2, ..., m,                     (8)

                             (9)

Замечание. Более общей является задача планирования огневого поражения:

                   (10)

при ограничениях

,                            (11)

                         (12)

Связь между решениями семейств задач (7)–(9) и (10)–(12) определяется формулой xij = Yjzij.

Здесь Mij – математическое ожидание количества пораженных целей обороны j-го типа нарядом i-го типа средств нападения; Zij ≥ 1 – соответствующий наряд; Xi – количество средств нападения i-го типа; Yj – количество целей обороны j-го типа; Aj – важность j-го типа целей обороны; xij – матрица назначения разнотипных средств нападения по разнотипным целям.

Субмодулярность задачи

Для построения эффективных верхних оценок в методе ветвей и границ для решения задачи огневого поражения можно использовать свойство субмодулярности функции C = C(ω), которое установлено в работе [8].

Если ω = f – пустое множество или огра-ничения задачи несовместны, то положим C = C(ω) = 0.

Напомним, что функция C = C(ω), определенная на 2J, называется субмодулярной, если для любых δ, ν  2J выполняется неравенство

.

Используя свойство субмодулярности, для решения задачи максимизации C = C(ω) на множестве 2J подмножеств J можно использовать методы субмодулярного программирования из работы [1], представляющие собой комбинацию метода ветвей и границ с критериями предварительного отсева заведомо неоптимальных вариантов.

 

Построение верхних оценок  в методе ветвей и границ

 

Главная проблема использования метода ветвей и границ – построение верхних оценок критерия в узле ω  J поискового безконтурного орграфа G. Если функция C = C(ω), определенная на 2J, является субмодулярной, то для  в качестве верхней оценки можно взять любое из следующих выражений [1]:

или

,

где  – нижняя срезка величины x. Это эквивалентно тому, что в верхней оценке учитываются только такие j, которые увеличивают функцию C(ω1) (C(ω2) – соответственно). Наличие двух формул для верхней оценки дает возможность распараллеливания процесса, осуществляя одновременно работу алгоритма метода ветвей и границ соответственно от f и J навстречу друг другу. Такого рода алгоритмы называются методами последовательного анализа вариантов [9].

 

Метод Поляка для решения промежуточных ТЗ о ГН с равенствами

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

При этом

Замечание. В случае пустого множества допустимых стратегий алгоритм перейдет на максимизацию агрегированного ограничения, что можно увидеть через его отрицательное предельное значение функции в левой части. Таким образом, метод Поляка [10] достаточно пускать один раз в каждом узле.

Числовой пример

Приведем модельный пример для проверки практической сходимости метода Поляка во вспомогательной задаче целераспределения с неуравновешенным балансом. Исходные данные задачи представлены в таблицах 1 и 2.

Таблица 1

Матрица Mij

Table 1

Mij matrix

i

j

1

2

3

4

1

3

2

6

3

2

3

2

6

3

3

3

2

6

3

Веса Аj

1

1

2

2

Таблица 2

Матрица Zij

Table 2

Zij matrix

i

j

Xi

1

2

3

4

1

14

10

42

24

98

2

14

10

42

24

46

3

14

10

42

24

16

Yj

2

2

2

1

160

На основании этих данных проверим работу метода ветвей и границ, построим орграф с узлами, раскрытыми в ходе работы алгоритма (рис. 1).

На рисунке 1 первое число над каждым из узлов соответствует значению критерия в этом узле, а второе означает верхнюю оценку критерия в узле. Исходная размерность задачи J = 4, значит, общее количество узлов в числовом примере определяется как 2J = 16.

 

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

Положим в задаче (7)–(9) Mij = Pij Î (0, 1), Zij Î [1, 5], Yj Î [1, 5], Aj = 1, m = 1/2n. Тогда математическое ожидание  равно 3n, математическое ожидание  равно 10m = 5n, и они находятся в соотношении

обеспечивающем нетривиальность решения в среднем. При этом для половины целей имеем:

то есть половина целей может быть в среднем обстреляна. В частности, одна цель может быть обстреляна при n/2 ≥ 1, то есть при n ≥ 2.

Замечание. Все величины предполагаются случайными, равномерно распределенными на соответствующих отрезках.

В ходе работы была создана программа на языке С++17, способная решить данную задачу ε-оптимальным методом ветвей и границ. Для оптимизации выбора необходимых узлов использован контейнер set стандартной библиотеки STL [11]. Использование данного контейнера позволяет уменьшить расход памяти за счет устранения повторяющихся узлов в каждом из раскрытий нового узла.

Для проведения численного эксперимента с использованием разработанной программы было решено запускать алгоритм по 10 раз для каждой из размерностей и подсчитывать среднее количество раскрытых вершин с макси-мально допустимым практическим значением относительной точности ε = 0,1. При увеличении размерности увеличивается и количество раскрытых узлов поискового орграфа, что продлевает вычислительный процесс и замедляет время работы программы.

Замечание. В рамках численного эксперимента ограничимся размерностью, при которой решение находится в пределах одного часа.

На рисунке 2 график c1 отражает зависимость среднего количества раскрытых вершин в ε-оптимальной версии метода ветвей и границ от размерности m+n задачи, график c2 – логарифмический масштаб графика с1, который должен быть линейным в случае экспоненциальной сложности алгоритма и логарифмическим в полиномиальном случае. В этом состоит качественный критерий полиномиальности алгоритма.

Анализ результатов эксперимента

По результатам численного эксперимента были составлены два графика (рис. 2 и 3), из которых видно, что логарифмический масштаб, отображенный на рисунке 2 (график c2), линейный. Это означает, что ε-оптимальная версия метода ветвей и границ экспоненциальна.

Заметим, что с увеличением размерности процент раскрытия вершин для данной задачи с ε-оптимальной версией метода ветвей и границ убывает, как показано на рисунке 3 (график c3), однако количество раскрытых вершин растет с увеличением размерности, как показано на рисунке 2 (график с1). Тем не менее процент раскрытых вершин убывает достаточно быстро, что говорит о практической значимости алгоритма.

Заключение

В настоящей работе введено понятие смешанного решения ТЗ о ГН, предложены постановка задачи и метод ветвей и границ градиентов для ее решения. Показано, что поставленная задача является субмодулярной, и предложено использовать верхние оценки критерия, основанные на субмодулярности. Описана модификация метода Б.Т. Поляка для вычисления значений показателя в промежуточных вершинах поискового орграфа метода ветвей и границ.

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

Проведен статистический эксперимент по проверке практической сходимости ε-опти­мальной версии метода ветвей и границ. Результаты его показали, что ε-оптимальная версия метода ветвей и границ экспоненциальна, однако процент раскрытых вершин убывает достаточно быстро, что говорит об эффективности алгоритма.

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

1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 c.

2. Финкельштейн Ю.Ю. Подход к многомерной задаче о ранце: полиномиальный рост дерева ветвления // Журнал вычислительной математики и математической физики. 1977. Т. 17. № 4. С. 1040–1042. doi: 10.1016/0041-5553(77)90120-3.

3. Kress A., Kiel F., Metternich J. A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Stored Branch and Bound Algorithm. Technical University Darmstadt. TU Darmstadt, 2021. URL: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404 (дата обращения: 10.12.2022).

4. Gao C., Lu G., Yao X., Li J. An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem. EJOR, 2017, vol. 260, no. 1, pp. 1–11. doi: 10.1016/j.ejor.2016.11.042.

5. Aardal K., van den Berg P.L., Gijswijt D., Li S. Approximation algorithms for hard capacitated k-faculty location problems. EJOR, 2015, vol. 242, no. 2, pp. 358–368.

6. Li W., Lee J., Shroff N. A faster FPTAS for knapsack problem with cardinality constraint. Discrete Applied Mathematics, 2022, vol. 315, pp. 71–85. doi: 10.1016/j.dam.2022.03.005.

7. Wu T., Chen L., Hui P., Zhang C.J., Li W. Hear the whole story: Towards the diversity of opinion in crowdsourcing markets. PVLDB, 2015, vol. 8, no. 5, pp. 485–496.

8. Монтлевич В.М. О субмодулярности функции прибыли в одной из задач планирования перевозок // Вестн. СамГУ. 2014. № 10. С. 48–54.

9. Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 353 c.

10. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 c.

11. Адильшаева Э.И., Халилова З.Э. Особенности реализации способов хранения и обработки данных на языках программирования С++ и Java // Информационно-компьютерные технологии в экономике, образовании и социальной сфере. 2018. № 1. С. 76–84.

Reference List

1. Korbut, A.A., Finkelshtein, Yu.Yu. (1969) Discrete Programming, Moscow, 368 p. (in Russ.).

2. Finkelshtein, Yu.Yu. (1977) ‘The ε-approach to the multidimensional knapsack problem: The polynomial growth of the branching tree’, USSR Computational Math. and Math. Phys., 17(4), pp. 1040–1042. doi: 10.1016/0041-5553(77)90120-3 (in Russ.).

3. Kress, A., Kiel, F., Metternich, J. (2021) ‘A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Stored Branch and Bound Algorithm. Technical University Darmstadt’, TU Darmstadt, available at: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404 (accessed December 10, 2022).

4. Gao, C., Lu, G., Yao, X., Li, J. (2017) ‘An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem’, EJOR, 260(1), pp. 1–11. doi: 10.1016/j.ejor.2016.11.042.

5. Aardal, K., van den Berg, P.L., Gijswijt, D., Li, S. (2015) ‘Approximation algorithms for hard capacitated k-faculty location problems’, EJOR, 242(2), pp. 358–368.

6. Li, W., Lee, J., Shroff, N. (2022) ‘A faster FPTAS for knapsack problem with cardinality constraint’, Discrete Applied Mathematics, 315, pp. 71–85. doi: 10.1016/j.dam.2022.03.005.

7. Wu, T., Chen, L., Hui, P., Zhang, C.J., Li, W. (2015) ‘Hear the whole story: Towards the diversity of opinion in crowdsourcing markets’, PVLDB, 8(5), pp. 485–496.

8. Montlevich, V.M. (2014) ‘On the submodularity of the profit function in a problem of transport planning’, Vestn. SamGU, (10), pp. 48–54 (in Russ.).

9. Khachaturov, V.R., Veselovsky, V.E., Zlotov, A.V. et al. (2000) Combinatorial Methods and Algorithms for Sol-ving Problems of Discrete Optimization of Large Dimension, Moscow, 353 p.

10. Polyak, B.T. (1983) Introduction to Optimization, Moscow, 384 p. (in Russ.).

11. Adilshayeva, E.I., Khalilova, Z.E. (2018) ‘Features of the implementation of data storage and processing methods in the C++ and Java programming languages’, Information and Computer Technologies in the Economy, Education and Social Sphere, (1), pp. 76–84 (in Russ.).


Permanent link:
http://swsys.ru/index.php?page=article&id=4998&lang=en
Print version
The article was published in issue no. № 2, 2023 [ pp. 250-256 ]

Perhaps, you might be interested in the following articles of similar topics: