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

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