Вход
  1. Главная
  2. Журналы
  3. «Газовая промышленность»
  4. Газовая промышленность 10.2024
Газовая Промышленность 10.2024

Научная статья

EDN: GPJISE

УДК 004.41::66.011
(UDK 004.41::66.011)

Авторизуйтесь

ЦИФРОВИЗАЦИЯ (DIGITALIZATION)

ЭВРИСТИЧЕСКИЙ ПРИЕМ СОКРАЩЕНИЯ ВРЕМЕНИ ПОИСКА РЕШЕНИЙ В ЗАДАЧАХ ЧАСТИЧНО ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

(HEURISTIC METHOD OF REDUCING THE TIME TO FIND SOLUTIONS TO PROBLEMS OF MIXED INTEGER LINEAR PROGRAMMING)

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

The practical problems of optimal resource management with constraints (for example, designing the composition of multicomponent hydrocarbon mixtures considering the economic, regulatory, and technical limitations of production technology) it is often possible to reduce to the problems of mixed integer linear programming. As a rule, such problems are solved by various modifications of the classical method of branches and bounds, often involving primary and deep heuristics at several phases of the solution search. The effectiveness of the branch and bound method depends on the specific problem and, in unsuccessful cases, can lead to a complete search. Of applied interest is the development of computational algorithms aimed at improving the efficiency of the procedure for finding solutions to problems of mixed integer programming (in terms of reducing time costs), without the need to organize close architecturally dependent relationships with the stages of building a tree of branches and bounds.
The article proposes a heuristic method for a multiple reduction in the time spent on finding solutions to problems of mixed integer linear programming (for example, the rational distribution of petroleum products to consumers, considering various restrictions on the logic of moving petroleum products). The technique is based on an aggressive reduction in the dimension of the problem caused by the fixation of zero integer variables extracted from the solution of the original problem obtained without taking into account the limitations of integers. Empirically based recommendations for the values of hyperparameters of the proposed heuristic technique are given. Possible directions for the development of the proposed heuristics using classical machine learning techniques (for example, threshold classifiers and anomaly detectors) and deep learning (graph convolutional networks) are indicated. Computational experiments on the problems of the MIPLIB 2017 library confirm a significant reduction in time costs with controlled distortion of the objective function.

ПРОБЛЕМА КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ, СТРАТЕГИЯ ФИКСАЦИИ ЦЕЛОЧИСЛЕННЫХ ПЕРЕМЕННЫХ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, МАШИННОЕ ОБУЧЕНИЕ, ЭВРИСТИКА

PROBLEM OF COMBINATORIAL OPTIMIZATION, STRATEGY FOR FIXING INTEGER VARIABLES, BRANCH AND BOUND METHOD, MACHINE LEARNING, HEURISTICS

С.А. Косяченко, к.т.н., ООО «Цифровая индустриальная платформа» (Москва, Россия)

А.О. Подвойский, к.т.н., ООО «Цифровая индустриальная платформа»

Г.А. Алексашин, ПАО «Газпром» (Санкт-Петербург, Россия)

S.A. Kosyachenko, PhD in Engineering, Industrial Digital Platform LLC (Moscow, Russia)

A.O. Podvoyskiy, PhD in Engineering, Industrial Digital Platform LLC

G.A. Aleksashin, PJSC Gazprom (Saint Petersburg, Russia)

Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. 2-е изд., перераб. и доп. Новосибирск: Наука, 1987. 272 с.

Таха Х.А. Введение в исследование операций / пер. с англ. В.И. Тюпти, А.А. Минько. 6-е изд. М.: Вильямс, 2001. 911 с.

Корте Б., Фиген Й. Комбинаторная оптимизация. Теория и практика / пер. с англ. М.А. Бабенко. М.: МЦНМО, 2015. 719 с.

Achterberg T. Constraint integer programming: PhD thesis. Berlin: Technische Universitat Berlin, 2007. 404 p.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. 2-е изд., перераб. и доп. М.: Энергоатомиздат, 1988. 480 с.

Khalil E., Le Bodic P., Song L., et al. Learning to branch in mixed integer programming // Thirtieth AAAI Conference on Artificial Intelligence. 2016. Vol. 30, No. 1. P. 724–731. DOI: 10.1609/aaai.v30i1.10080.

Gasse M., Chetelat D., Ferroni N., et al. Exact combinatorial optimization with graph convolutional neural networks // Advances in neural information processing systems 32: Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019) / ed. by H. Wallach et al. Red Hook, NY, USA: Curran Associates, 2019. P. 15501–15514.

Gupta S., Joshi G., Yagan O. Correlated multi-armed bandits with a latent random source // Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). New York, NY, USA: IEEE, 2020. P. 3572–3576. DOI: 10.1109/ICASSP40776.2020.9054429.

Khalil E.B., Dilkina B., Nemhauser G.L., et al. Learning to run heuristics in tree search // Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) / ed. by C. Sierra. Menlo Park, CA, USA: IJCAI, 2017. P. 659–666.

Hendel G. Adaptive large neighborhood search for mixed integer programming // Mathematical Programming Computation. 2018. Vol. 14. P. 185–221. DOI: 10.1007/s12532-021-00209-7.

Akbarzadeh B., Moslehi G., Reisi-Nafchi M., Maenhot B. A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering // Journal of Scheduling. 2020. Vol. 23. P. 265–288. DOI: 10.1007/s10951-020-00639-6.

Baltean-Lugojan R., Bonami P., Msener R., Tramontani A. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks // Optimization Online: репозиторий. URL: https://optimization-online.org/2018/11/6943/ (дата обращения: 15.10.2024).

Tang Y., Agrawal S., Faenza Y. Reinforcement learning for integer programming: Learning to cut // Proceedings of Machine Learning Research. 2020. Vol. 119. P. 9367–9376.

SCIP: сайт. URL: https://www.scipopt.org/ (дата обращения: 15.10.2024).

CBC // GitHub, Inc.: офиц. сайт. URL: https://github.com/coin-or/Cbc (дата обращения: 15.10.2024).

HiGHS: сайт. URL: https://highs.dev/ (дата обращения: 15.10.2024).

IBM ILOG CPLEX Optimizer // IBM Corporation: офиц. сайт. URL: https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer (дата обращения: 15.10.2024).

Gurobi Optimization, LLC: офиц. сайт. URL: https://www.gurobi.com/ (дата обращения: 15.10.2024).

COPT GmbH: офиц. сайт. URL: https://www.copt.de/ (дата обращения: 15.10.2024).

MIPLIB 2017: сайт. URL: https://miplib.zib.de/ (дата обращения: 15.10.2024).

Ke G., Meng Q., Finley T., et al. LightGBM: A highly efficient gradient boosting decision tree // Advances in neural information processing systems 30: Proceedings of the 31st Annual Conference on Neural Information Processing Systems (NIPS 2017) / ed. by I. Guyon et al. San Diego, CA, USA: Neural Information Processing Systems Foundation, 2017. P. 3147–3156.

Li Z., Zhao Y., Botta N., et al. COPOD: Copula-based outlier detection // Proceedings of the IEEE International Conference on Data Mining (ICDM) / ed. by C. Plant et al. New York, NY, USA: IEEE, 2020. P. 1118–1123. DOI: 10.1109/ICDM50108.2020.00135.

Li Z., Zhao Y., Hu X., et al. ECOD: Unsupervised outlier detection using empirical cumulative distribution functions // IEEE Transactions on Knowledge and Data Engineering. 2022. Vol. 35, No. 12. P. 12181–12193. DOI: 10.1109/TKDE.2022.3159580.

Goldstein M., Dengel A. Histogram-based outlier score (HBOS): A fast unsupervised anomaly detection algorithm // KI-2012: Poster and Demo Track of the 35th German Conference on Artificial Intelligence / ed. by S. Wölfl. Freiburg, Germany: Albert-Ludwigs-Universitat Freiburg, 2012. P. 59–63.

zero_integer_vars_miplib2017 // GitHub, Inc.: офиц. сайт. URL: https://github.com/LeorFinkelberg/zero_integer_vars_miplib2017.git (дата обращения: 15.10.2024).

Mukhacheva EA, Rubinshteyn GSh. Mathematical Programming. 2nd ed. Novosibirsk, Russia: Science [Nauka]; 1987. (In Russian)

Taha HA. Operations Research: An Introduction. Trans. Tyupti VI, Minko AA. 6th ed. Moscow: Williams; 2001. (In Russian)

Korte B, Figen Y. Combinatorial Optimization. Theory and Algorithms. Trans. Babenko MA. Moscow: Moscow Center for Continuous Mathematical Education; 2015. (In Russian)

Achterberg T. Constraint integer programming. PhD thesis. Technische Universitat Berlin; 2007.

Kuznetsov OP, Adelson-Velskiy GM. Discrete Mathematics for Engineers. 2nd ed. Moscow: Energoatomizdat; 1988. (In Russian)

Khalil E, Le Bodic P, Song L, Nemhauser G, Dilkina B. Learning to branch in mixed integer programming. Thirtieth AAAI Conference on Artificial Intelligence. 2016; 30(1): 724–731. https://doi.org/10.1609/aaai.v30i1.10080.

Gasse M, Chetelat D, Ferroni N, Charlin L, Lodi A. Exact combinatorial optimization with graph convolutional neural networks. In: Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R (eds) NeurIPS 2019: Advances in neural information processing systems 32: Proceedings of the 33rd Conference on Neural Information Processing Systems, 8–14 December 2019, Vancouver, Canada. Red Hook, NY, USA: Curran Associates; 2019. p. 15501–15514.

Gupta S, Joshi G, Yagan O. Correlated multi-armed bandits with a latent random source. In: IEEE ICASSP: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, 4–8 May 2020, Barcelona, Spain. New York, NY, USA: IEEE; 2020. p. 3572–3576. https://doi.org/10.1109/ICASSP40776.2020.9054429.

Khalil EB, Dilkina B, Nemhauser GL, Ahmed S, Shao Y. Learning to run heuristics in tree search. In: Sierra C (ed.) IJCAI-17: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 19–25 August 2017, Melbourne, Australia. Menlo Park, CA, USA: IJCAI; 2017. p. 659–666.

Hendel G. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation. 2018; 14: 185–221. https://doi.org/10.1007/s12532-021-00209-7.

Akbarzadeh B, Moslehi G, Reisi-Nafchi M, Maenhot B. A diving heuristic for planning and scheduling surgical cases in the operating room department with nurse re-rostering. Journal of Scheduling. 2020; 23: 265–288. https://doi.org/10.1007/s10951-020-00639-6.

Baltean-Lugojan R, Bonami P, Msener R, Tramontani A. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. Available from: https://optimization-online.org/2018/11/6943/ [Accessed: 15 October 2024].

Tang Y, Agrawal S, Faenza Y. Reinforcement learning for integer programming: Learning to cut. Proceedings of Machine Learning Research. 2020; 119: 9367–9376.

SCIP. Homepage. Available from: https://www.scipopt.org/ [Accessed: 15 October 2024].

GitHub, Inc. CBC. Available from: https://github.com/coin-or/Cbc [Accessed: 15 October 2024].

HiGHS. Homepage. Available from: https://highs.dev/ [Accessed: 15 October 2024].

IBM Corporation. IBM ILOG CPLEX Optimizer. Available from: https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer [Accessed: 15 October 2024].

Gurobi Optimization, LLC. Homepage. Available from: https://www.gurobi.com/ [Accessed: 15 October 2024].

COPT GmbH. Homepage. Available from: https://www.copt.de/ [Accessed: 15 October 2024].

MIPLIB 2017. Homepage. Available from: https://miplib.zib.de/ [Accessed: 15 October 2024].

Ke G, Meng Q, Finley T, Wang T, Chen W, Ma W, et al. LightGBM: A highly efficient gradient boosting decision tree. In: Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S (eds.), et al. NIPS 2017: Advances in neural information processing systems 30: Proceedings of the 31st Annual Conference on Neural Information Processing Systems, 4–9 December 2017, Long Beach, CA, USA. San Diego, CA, USA: Neural Information Processing Systems Foundation; 2017. p. 3147–3156.

Li Z, Zhao Y, Botta N, Ionescu C, Hu X. COPOD: Copula-based outlier detection. In: Plat C, Wang H, Cuzzocrea A, Zaniolo C, Wu X (eds.) ICDM: Proceedings of the IEEE International Conference on Data Mining, 17–20 November 2020, Virtual. New York, NY, USA: IEEE; 2020. p. 1118–1123. https://doi.org/10.1109/ICDM50108.2020.00135.

Li Z, Zhao Y, Hu X, Botta N, Ionescu C, Chen GH. ECOD: Unsupervised outlier detection using empirical cumulative distribution functions. IEEE Transactions on Knowledge and Data Engineering. 2022; 35(12): 12181–12193. https://doi.org/10.1109/TKDE.2022.3159580.

Goldstein M, Dengel A. Histogram-based outlier score (HBOS): A fast unsupervised anomaly detection algorithm. In: Wölfl S (ed.) KI-2012: Poster and Demo Track of the 35th German Conference on Artificial Intelligence, 24–27 September 2012, Saarbrücken, Germany. Freiburg, Germany: Albert-Ludwigs-Universitat Freiburg; 2012. p. 59–63.

GitHub. zero_integer_vars_miplib2017. Available from: https://github.com/LeorFinkelberg/zero_integer_vars_miplib2017.git [Accessed: 15 October 2024].

Перевод выполнен Moscow Translation Agency

Назад к журналу
ТЕРРИТОРИЯНЕФТЕГАЗ

Внимание к деталям — от идеи
до воплощения! Только актуальная информация и свежие новости.

Журналы

Контент

О нас

Контакты