ИСПОЛЬЗОВАНИЕ МЕТОДА ПОКООРДИНАТНОГО СПУСКА ДЛЯ ПОИСКА РЕШЕНИЯ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
USAGE OF COORDINATE DESCENT ALGORITHM IN SEARCH OF A SOLUTION TO AN INTEGER PROGRAMMING PROBLEM

Скачать статью

Авторы

Ю.Н. МАТВЕЕВ, д-р техн. наук, А.В. ИВАНОВ, аспирант

Аннотация

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

Ключевые слова

дискретная оптимизация, математическое программирование, линейное программирование, целочисленное программирование, оптимизация, алгоритм, градиентный метод, покоординатный спуск.

Abstract

The article proposes an algorithm for solving the integer programming problem in a way similar to the coordinate descent method. An alternative algorithm avoids the time-consuming search for a point using the simplex method at each iteration. A detailed description of the algorithm and a demonstration of its operation is given on the example of an optimization problem with two parameters. The current limitations of the proposed algorithm are given, as well as arguments about their possible use in future works.

Keywords

discrete optimization, mathematical programming, linear programming, integer programming, optimization, algorithm, gradient method, coordinate descent