Оптимизационных задач комбинаторного типа и их исследование
Академия наук Украинской ССР
Ордена Ленина Институт кибернетики имени В.М. Глушкова
На правах рукописи
ХОДЗИНСКИЙ Александр Николаевич
УДК 519. 854+681.3
НЕКОТОРЫЕ МЕТОДЫ РЕШЕНИЯ
ОПТИМИЗАЦИОННЫХ ЗАДАЧ КОМБИНАТОРНОГО
ТИПА И ИХ ИССЛЕДОВАНИЕ
01.01.09 – математическая кибернетика
Автореферат диссертации на соискание ученой степени
кандидата физико-математических наук
Киев – 1984
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. Дискретное программирование является одним из важных разделов прикладной математики. В частности, большое практическое и теоретическое значение имеют исследования, связанные с решением задач комбинаторной оптимизации. Такие задачи возникают в проектировании, планировании, экономике. К настоящему времени разработано значительное число разнообразных методов решения комбинаторных оптимизационных задач. Продолжающаяся разработка новых и модификация известных методов объясняется расширением круга решаемых практических задач, а также появлением новых требований, возникающих при создании программ, которые реализуют алгоритмы этих методов на ЭВМ. Данные требования касаются главным образом возможностей организации прикладного программного обеспечения в форме пакетов программ (ПП).
Большинство вопросов, которые возникают при разработке конкретных ПП, носят комплексный характер. Поэтому усиленное их решение зависит от степени участия разработчиков алгоритмов в создании системной части пакета. В настоящей работе рассматривается ряд общих вопросов, связанных с разработкой ПП ВЕКТОР-2.
Цель работы состоит в том, чтобы:
– формализовать и исследовать один класс задач комбинаторной оптимизации;
– разработать новые алгоритмы решения выбранного класса задач комбинаторной оптимизации на базе схем известных методов, а также предложить новый приближенный метод;
– исследовать эффективность разработанных алгоритмов теоретически и по результатам машинного эксперимента;
– разработать часть программного обеспечения диалогового ПП ВЕКТОР-2, предназначенного для решения задач комбинаторной оптимизации;
– разработать алгоритмы решения задач из выбранного класса, предназначенные для реализации на ЭВМ с параллельной организацией вычислений.
Методика исследований. В основу исследований, связанных с разработкой и изучением области применения и эффективности методов решения задач комбинаторной оптимизации, положены методы и результаты комбинаторного анализа, теории графов, теории целочисленного программирования, элементы анализа вычислительной сложности алгоритмов, методы организации вычислений и создания математического обеспечения ЭВМ.
Научная новизна. Разработан метод решения задач комбинаторной оптимизации на перестановках. Предложена эффективная модификация метода вектора спада для решения многих важных задач дискретной оптимизации. Решен ряд вопросов, связанных с созданием ПП ВЕКТОР-2.
Практическая ценность и реализация результатов. Разработанные в диссертации методы и алгоритмы реализованы при создании ПП ВЕКТОР-2, предназначенного для решения задач комбинаторной оптимизации. Данный пакет внедрен и используется в ряде организаций страны, что позволило получить значительный экономический эффект (подтверждающие это внедрение акты прилагаются).
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на ІІ Республиканской конференции ”Вычислительная математика в современном научно-техническом прогрессе” (Киев, 1978 г.), Всесоюзном научно-практическом семинаре ”Прикладные аспекты управления сложными системами” (Кемерово, 1983 г.), V Всесоюзном совещании по автоматизации проектирования электротехнических устройств (Таллинн, 1983 г.), ІІІ Всесоюзном совещании по применению случайного поиска (Междуреченск, 1984 г.), на семинарах научного совета по проблеме “Кибернетика” (Киев, ИК АН УССР, 1977–1983 г.г.).
Публикации. Основные результаты диссертации опубликованы в работах [1] – [10].
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка цитируемой литературы и приложения. Общий объем работы 116 страниц, список литературы – 61 наименование. Изложение иллюстрируется 1 рисунком и 14 таблицами.
СОДЕРЖАНИЕ РАБОТЫ
Во введении приводится краткая характеристика предмета исследования и обоснование его актуальности.
Пусть 
=
– множество перестановок 
натуральных чисел; 
– его подмножество, определяемое ограничительными условиями задачи; 
– целевая функция (критерий) задачи, заданная на 
или на всем множестве 
. Требуется найти такую точку 
, для которой целевая функция принимает наименьшее значение:
=
. (1)
Перестановку 
натуральных чисел можно интерпретировать двояко: с одной стороны как некоторое упорядочение объектов, занумерованных этими числами, с другой – как некий способ назначения этих объектов на перенумерованные места. Поэтому в работе рассматривается четыре типа ограничений, задающих область 
, которые отражают эту двойственную интерпретацию перестановок:
– фиксированное назначение: заданы 
и требуется, чтобы 
;
– запретное назначение: заданы 
и требуется, чтобы 
;
– непосредственное следование: заданы 
такие, что если 
, то требуется, чтобы 
;
– простое следование: заданы 
такие, что если 
, 
, то требуется, чтобы 
.
Перестановку 
, определенную равенством (1), будем называть точным решением задачи. Если же существует множество 
и перестановка 
такие, что 
=
, то 
будем называть приближенным решением.
Пусть 
– множество первых 
натуральных чисел. Пусть 
– множество таких перестановок, у которых первые 
компонент равны соответственно заданным числам 
. При 
будем считать, что 
. Для любого 
число различных множеств 
равно, очевидно, 
. Какое из этих множеств обозначено 
, будет каждый раз понятно из контекста, так как будут известны значения первых 
компонент перестановок 
. Если необходимо подчеркнуть, что значение 
-той компоненты (последней из зафиксированных) перестановок 
из множества 
равно некоторому 
, то такое множество будем обозначать 
. Следующие обозначения касаются статистических характеристик критерия 
на множествах 
, 
.
Среднее значение 
на множестве 
будем обозначать 
, дисперсию – 
, среднее квадратическое отклонение – 
и вычислять по формулам:
где 
– мощность множества 
.
Соответствующие величины, характеризующие множество 
, будем обозначать 
.
В работе рассматривается несколько типов задач комбинаторной оптимизации. Каждая конкретная задача характеризуется набором ограничений, которые задают допустимую область 
, и видом критерия 
. Именно в зависимости от вида 
изучаемые задачи относятся к одному из следующих типов:
- линейная задача о назначениях;
- задача о коммивояжере;
- квадратичная задача о назначениях;
- задача разбиения;
- задача размещения;
- задача расписания.
Как уже было отмечено, в настоящее время к алгоритмам предъявляется ряд требований, связанных с реализацией этих алгоритмов на ЭВМ в форме ПП. В ходе выполнения данной работы учитывались, в основном, два таких требования:
- Универсальность алгоритмов. Как правило, ПП разрабатывается для решения не одной, а целого класса оптимизационных задач. По этой причине необходимо, чтобы каждый программный модуль алгоритма мог быть применен при решении каждой или хотя бы большинства их них.
- Разнообразие алгоритмов. Как показывает опыт, обычно не удается заранее определить, какой из алгоритмов окажется наиболее эффективным при решении конкретной прикладной задачи. Поэтому в ПП необходимо включать несколько алгоритмов для решения одних и тех же задач.
С целью удовлетворения требованию универсальности при построении и исследовании различных типов алгоритмов, которые рассматриваются в данной работе, применяется следующая методика. Вначале создается либо выбирается из известных такая общая схема, которую после незначительных модификаций можно использовать при построении алгоритмов любой из рассматриваемых в работе задач. Затем в рамках этой фиксированной схемы исследуются алгоритмы для решения конкретных задач. В рамках данной работы исследуются алгоритмы четырех типов:
- алгоритмы метода ветвей и границ. Эти алгоритмы предназначены для поиска решений с заданной точностью;
- алгоритмы метода вектора спада. Это локально-оптимальные алгоритмы итерационного типа;
- алгоритмы метода Монте-Карло. Это алгоритмы стохастического типа;
- алгоритмы последовательного типа.
В первой главе определяются способы вычисления критерия 
в изучаемых типах задач: в § 1 – для линейной задачи о назначениях, в § 2 – для задачи о коммивояжере, в § 3 – для квадратичной задача о назначениях; в § 4 – для задачи разбиения; в § 5 – для задачи размещения; в § 6 – для задачи расписания.
- Линейная задача о назначениях.
=
,
где 
, а 
, 
, 
заданная матрица.
- Задача о коммивояжере.
=
,
где 
, а 
, 
, 
заданная матрица.
- Квадратичная задача о назначениях.
=
где 
, а 
, 
, 
и 
, 
заданные матрицы.
- Задача разбиения. Пусть
, 
, некоторые фиксированные подмножества 
и пусть задано натуральное число 
и 
натуральных чисел 
таких, что 
. Каждой перестановке 
в зависимости от значений 
ставится в соответствие разбиение множества 
на 
непересекающихся подмножеств 
, 
:
, 
.
В этих обозначениях критерий оптимизации определяется следующим равенством:
=
.
- Задача размещения. Так будем называть задачу оптимального размещения геометрически однотипных модулей радиоэлектронной аппаратуры на дискретном поле позиций. Пусть задано
равных прямоугольников, которые назовем модулями. Вдоль одной пары параллельных сторон модуля расположены точки, которые назовем контактами. Расстояния между соседними контактами равны. Множество контактов всех 
модулей разбито на непересекающиеся подмножества, которые назовем цепями. На плоскости задано 
позиций, каждая из которых имеет размер модуля. Центры позиций расположены в углах ортогональной сетки, а сами позиции пронумерованы числами от 1 до 
. Любой способ установки множества модулей в множество позиций называется размещением. Очевидно, что между множеством размещений и множеством перестановок существует взаимно однозначное соответствие.
Кроме контактов модулей на плоскости задан ряд точек, которые называются внешними контактами. Внешние контакты могут входить в некоторые из цепей: эти цепи называются внешними, остальные – внутренними.
Пусть цепь с номером 
при заданном размещении 
объединяет контакты с координатами:
,
где 
число всех контактов в 
той цепи.
Полагаем:
=
,
=
,
=
+
.
Тогда критерий 
определяется из равенства:
=
,
где 
– число всех цепей.
- Задача расписания. Постановка этой задачи вначале берется в той форме, в которой она встречается в литературе – задача оптимального обслуживания
требований 
идентичными приборами.
Пусть заданы длительности 
выполнения требований приборами, а также наложены ограничения на порядок выполнения требований приборами в виде матрицы ограничений 
, 
, где
=
План обслуживания требований (расписание) 
характеризуется матрицей 
и вектором 
, 
, где
=
– момент начала выполнения 
-го требования.
Если 
-тое требование в расписании 
выполняется последним на 
-том приборе, то величина 
есть момент окончания работы 
-тым прибором. Критерием качества расписания 
является момент окончания работы всех приборов:
Легко видеть, что при такой постановке задачи множество 
допустимых расписаний бесконечно. В работе производится следующий способ выбора из этого бесконечного множества конечного подмножества 
.
Пусть 
=
– множество перестановок первых 
натуральных чисел, в которых для каждой пары компонент 
такой, что 
, выполняется неравенство 
. Легко понять, что в принятой в работе терминологии 
– это сужение множества 
путем введения ограничений типа простого следования. Поставим каждой перестановке 
в соответствие расписание 
, построенное по следующему 
-шаговому алгоритму:
-тый шаг алгоритма 
. На этом шаге в расписание включается наименее загруженный прибор, т.е. такой, момент 
окончания работы которого перед включением в расписание требованиям 
минимально. Если таких приборов несколько, то для определенности выбирается прибор с наименьшим номером. Обозначим через 
множество номеров тех требований, после которых может выполняться требование 
. Момент 
выбирается максимально возможным:
.
Легко видеть, что построенное по такому 
-шаговому алгоритму множество 
имеет мощность 
.
В работе доказана теорема 1.1, из которой следует, что при сужении исходного множества расписаний 
до множества 
глобальное решение исходной задачи не теряется.
Т е о р е м а 1.1. Пусть задано произвольное расписание 
. Тогда найдется расписание 
, такое, что 
.
Во второй главе изучаются перечисленные выше методы применительно к решению задач оптимизации без ограничений, т.е. когда 
. Каждый из этих методов имеет некую общую схему. Применительно к решению конкретных типов задач разработаны отдельные пункты этих схем. Проведен анализ результатов численного эксперимента и теоретического исследования по изучению таких показателей эффективности алгоритмов как временная сложность и точность получаемого решения.
В § 1 изучается метод ветвей и границ. Как известно, всевозможные модификации метода ветвей и границ различаются тремя основными моментами: способом ветвления, стратегией ветвления и способом вычисления нижней оценки. В связи с этим алгоритмы, которые рассматриваются в данной работе, имеют следующие особенности в реализации этих моментов.
С п о с о б в е т в л е н и я в данных алгоритмах – покомпонентное ветвление. Вариантом ветвления является множество 
– множество перестановок 
, у которых первые 
компонент фиксированы и равны известным в данный момент работы алгоритма числам 
. Пусть 
. В начале работы алгоритма вариантом ветвления является все множество 
. При ветвлении каждый такой вариант порождает 
новых вариантов – множеств 
, элементы которых имеют уже 
фиксированную компоненту.
Под с т р а т е г и е й в е т в л е н и я подразумевается способ выбора очередного варианта ветвления. В описанных в работе алгоритмах стратегией ветвления является ветвление по заранее выбранному пути, а конкретно – выбор очередного варианта происходит по принципу “иди влево” по дереву вариантов решений.
С п о с о б в ы ч и с л е н и я н и ж н е й о ц е н к и. Рассмотрим некоторый вариант ветвления – множество 
, 
. Нижнюю оценку значения критерия 
на этом множестве обозначим через 
. В работе показано, что для линейной задачи о назначениях нижней оценкой может служить величина:
В задаче о коммивояжере исследовались две нижние оценки:
В последнем равенстве 
означает оптимальное значение критерия линейной задачи о назначениях с матрицей, которая получена из исходной матрицы 
путем вычеркивания строк и столбцов с номерами соответственно 
и 
.
При решении конкретной задачи о назначениях различные способы получения нижних оценок основаны на представлении значений критерия 
при заданном варианте ветвления 
в таком виде:
Для того, чтобы оценить вторую и третью суммы в правой части последнего равенства, применяется известный способ порождения линейной задачи о назначениях, решение которой оценивает эти суммы снизу. Четвертая сумма оценивается снизу скалярным произведением векторов, первый из которых составлен из величин 
, упорядоченных по возрастанию, а второй – из величин 
, упорядоченных по убыванию 
. В работе предложен способ оценки четвертого слагаемого, который сочетает оба эти подхода и увеличивает нижнюю оценку.
Нижней оценкой в задаче разбиения служит величина
где 
=
Нижней оценкой в задаче размещения служит величина
где 
вычисляется тем же способом, что и 
, на множестве контактов тех модулей, которые входят в 
.
В задаче расписания выражение для вычисления нижней оценки имеет вид:
где 
– момент окончания работы 
-ого прибора при условии, что приборы будут выполнять только требования 
.
Результаты, полученные при доказательстве приведенных нижних оценок, сформулированы в т е о р е м а х 2.1–2.6.
В § 2 проводится исследование алгоритмов метода вектора спада. Как известно, применение метода вектора спада основано на метризации допустимого множества вариантов. Предположим, такая метризация проведена. Пусть 
окрестность радиуса 
с центром в точке 
, где 
номер очередной итерации. В каждом конкретном алгоритме метода вектора спада задан порядок перебора точек окрестности 
. Этот порядок удобно интерпретировать как последовательное применение к центру окрестности некоторой последовательности операторов 
Здесь 
– это оператор, который генерирует точку первого попавшегося “улучшения” целевой функции. Такая точка объявляется центром новой окрестности: 
. После перехода в центр новой окрестности 
операторы снова применяются в последовательности 
Такой алгоритм генерации точек очередной окрестности назовем линейным генератором вариантов. Линейный генератор традиционно применяется в различных модификациях метода вектора спада. В отличие от линейного генератора вариантов в работе предлагается применять алгоритм, который назовем кольцевым генератором вариантов. Этот алгоритм характеризуется тем, что в приведенных обозначениях точки окрестности 
генерируются путем применения последовательности операторов, начиная с 
В § 3 проводится исследование алгоритмов метода Монте-Карло. Основной интерес здесь представляет вопрос о вероятности получения любой из перестановок 
при использовании датчика случайных чисел. Доказывается
Т е о р е м а 2. 7. Пусть 
перестановка, генерируемая датчиком случайных чисел. Тогда для любой перестановки 
: 
.
В § 3 – § 7 предлагается и исследуется приближенный алгоритм последовательного типа. Основная идея построения последовательных алгоритмов известна: так как решение является сложным объектом (в данном случае перестановкой 
чисел), то его можно строить по частям, постепенно увеличивая число включенных элементов. Предлагаемый в работе метод обладает следующими конкретными особенностями. Считается, что перед началом очередного (
го) шага алгоритма уже определены 
компонент искомой перестановки 
. На 
м шаге должно быть определено значение 
. Это значение предлагается выбирать из условия минимума среднего значения критерия 
на множествах 
, 
В общем случае для приближенного вычисления средних используется процедура метода Монте-Карло:
где 
– значение случайной перестановки при 
ом бросании, а 
– число бросаний.
Для отдельных типов критерия можно получить точные и трудоемкие формулы определения значений 
. В работе показано, как это делается для линейной задачи о назначениях, задачи о коммивояжере, квадратичной задачи о назначениях.
В § 8 приводятся результаты исследования эффективности алгоритмов. Изучаются такие параметры эффективности как временная сложность алгоритмов и точность получаемого решения. Получены, в частности, следующие результаты:
- временная сложность алгоритмов метода вектора спада с кольцевым генератором вариантов при решении линейной задачи о назначениях и задачи о коммивояжере оценивается величиной
; - временная сложность последовательных алгоритмов при решении линейной задачи о назначениях и задачи о коммивояжере оценивается величиной
; а квадратичной задачи о назначениях – величиной 
.
Кроме того, ряд результатов получено при проведении численного эксперимента по решению ряда тестовых и прикладных задач. Например, время решения известной задачи Штейнберга (квадратичная задача о назначениях, 
) последовательным алгоритмом на ЭВМ БЭСМ-6 равно 0, 2 секунды, алгоритмом метода вектора спада – 23 секунды, при этом значение целевой функции составляет 4194, что является одним из лучших решений этой задачи. Другой пример – задача разбиения. Множество из 96 элементов было разбито на два равных подмножества, число разорванных цепей составило при этом 43. При решении данной задачи опытным конструктором был получен результат, равный 99.
Полученные в диссертации результаты позволили сделать следующие выводы:
- выбранные алгоритмы пригодны для решения всех изучаемых типов задач;
- предложенная модификация метода вектора спада с кольцевым генератором вариантов при решении выделенного класса задач более эффективна, чем традиционная схема метода;
- комплекс, состоящий из указанных алгоритмов, является эффективным средством для решения изучаемых задач.
В третьей главе рассмотрен ряд вопросов, касающихся реализации алгоритмов на ЭВМ.
В § 1 исследуется пригодность изучаемых алгоритмов для решения задач с ограничениями, а также для нахождения в этом случае допустимого решения. Показано, что после незначительной модификации метод вектора спада и метод ветвей и границ могут использоваться для решения задач со всеми четырьмя типами ограничений, причем последний метод пригоден для поиска допустимого решения.
В § 3 – § 4 рассматриваются отдельные вопросы, связанные с созданием программного обеспечения ЭВМ для решения задач оптимизации на примере ПП ВЕКТОР-2.
Выше было указано два требования, предъявляемые к алгоритмам, включаемым в ПП: их универсальность и разнообразие. Стремление удовлетворить этим требованиям и послужило основанием выбора для исследования рассматриваемого комплекса алгоритмов. Кроме того, программная реализация алгоритмов, включаемых в пакет, должна обладать определенными свойствами, которые диктуются способом организации системной части пакета:
– схемы алгоритмов должны предусматривать возможность прерывания вычислительного процесса и восстановления его с момента прерывания в следующем сеансе работы пакета;
- объем данных, которые сохраняются для восстановления работы пакета, должен быть минимальным;
- схемы алгоритмов должны предусматривать возможность прерывания вычисления для проведения сеанса диалога между пользователем и пакетом.
В § 2 показано, что схемы методов ветвей и границ и вектора спада обладают этим свойством.
В § 3 рассматриваются вопросы планирования вычислительного процесса в ПП ВЕКТОР-2 и создания комбинированных схем алгоритмов.
Для выполнения своей задачи специальному блоку ПЛАНИРОВЩИКУ АЛГОРИТМОВ требуются значения ряда величин, характеризующих эффективность алгоритмов при решении задач. Эти сведения, полученные при априорном исследовании алгоритмов, первоначально вводятся разработчиком алгоритмов, а затем уточняются в процессе эксплуатации пакета.
В ПП ВЕКТОР-2 имеются средства, предоставляющие пользователю возможность решать задачу, составляя комбинированные схемы из алгоритмов, которые имеются в пакете. Для успешного функционирования такого комбинированного алгоритма каждый из входящих в него алгоритмов должен удовлетворять требованию: вычислительная схема алгоритма должна быть одной и той же независимо от того, в какую комбинированную схему он включается.
В § 4 рассматривается организация функционирования ПП ВЕКТОР-2 в целом при решении задач.
Процесс решения задачи с помощью ПП ВЕКТОР-2 состоит из трёх последовательных этапов: этапа ввода задания и синтаксического контроля, этана семантического контроля и планирования вычислительного процесса, этапа счета по алгоритму. В общих чертах ход вычислительного процесса представлен на Рис. 1. Сплошными стрелками указана последовательность этапов решения задачи, которая соблюдается при отсутствии вмешательства со стороны пользователя, пунктирные стрелки отражают возможность изменений в чередовании этапов при таком вмешательстве.
Рис. 1. Схема процесса решения задачи.
Когда структура математического обеспечения диалогового пакета такова, что управление его функционированием децентрализовано, важное место занимает решение вопроса об организации обмена информацией между пакетом и пользователем. Для решения этого вопроса при создании ПП ВЕКТОР-2 было введено понятие виртуальной вычислительной машины (ВВМ), которая обладает такими свойствами.
- Внутренним языком ВВМ является ФОРТРАН-ІV.
- ВВМ имеет одно устройство обмена. Единицей обмена для этого устройства служит строка символов. Устройство обмена ВВМ может работать в одном из таких режимов: вывод строки, ввод строки, вывод и ввод строки. Обращение к устройству обмена из программы на Фортране происходит путем вызова (CALL) специальной системной подпрограммой пакета.
Как показал опыт, созданный на основе этой концепции пакет обладает простой структурой и вместе схем предоставляет пользователю широкие возможности для управления функционированием пакета в диалоговом режиме.
В § 5 рассматривается вопрос о возможности распараллеливания вычислений в схемах изучаемых алгоритмов. Существуют и разрабатываются вычислительные комплексы (МВК), в которых распараллеливание вычислений реализовано различным образом. Приводятся схемы метода ветвей и границ и метода вектора спада, приспособленные для использования на МВК, которые допускают распараллеливание на уровне целых программных блоков. В основу распараллеливания метода ветвей и границ положена возможность разбиения дерева вариантов решения на множество поддеревьев, чтобы для просмотра каждого из них использовать отдельный процессор. В методе вектора спада распараллеливание основано на том, что перебор точек очередной окрестности можно выполнять независимо.
В заключении приводятся
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ
- Осуществлена формализация и проведено исследование ряда важных в практическом и теоретическом отношении задач (размещения, теории расписаний и др.), сформулированных как комбинаторные задачи оптимизации.
- Предложен ряд новых алгоритмов решения выделенного класса задач и исследована их эффективность.
- Разработаны принципы организации и функционирования мобильных ПП для решения задач комбинаторной оптимизации, которые нашли применение при создании ПП ВЕКТОР-2.
- Проведен численный эксперимент по решению широкого круга практических и тестовых задач комбинаторной оптимизации, который подтвердил эффективность предложенных алгоритмов.
- Разработаны компоненты модульного программного обеспечения пакета программ ВЕКТОР-2, в котором реализованы основные алгоритмы, предложенные в диссертации.
- Разработаны алгоритмы решения задач из выбранного класса, предназначенные для реализации на ЭВМ с параллельной организацией вычислений.
Приложение содержит копии актов о внедрении.
По теме диссертации опубликованы следующие работы:
- Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.Н. Об одном пакете программ решения задач размещения для ЭМВ БЭСМ-6. – В кн.: ІІ Республиканская конференция “Вычислительная математика в современном научно-техническом прогрессе”. Тезисы докладов. – Киев, ИК АН УССР, 1978, с.190–191.
- Ходзинский А.Н. Результаты машинного эксперимента по решению одного типа задач теории расписаний методом ветвей и границ и методом вектора спада. – В кн.: Разработка математических и технических средств АСУ. Сб. научн. тр. – Киев: ИК АН УССР, 1978, с.17–24.
- Ходзинский А.Н. Об одном алгоритме поиска начального приближения в задачах размещения узлов ЭМВ. – В кн.: Вычислительные аспекты в пакетах прикладных программ. Сб. научн. тр. – Киев: ИК АН УССР, 1978, с. 39–44.
- Гуляницкий Л.Ф., Ходзинский А.Н. Особенности реализации алгоритмов метода ветвей и границ и метода вектора спада в пакете ВЕКТОР-ІВ. – В кн.: Вычислительные аспекты в пакетах прикладных программ. Сб. научн. тр. – Киев: ИК АН УССР, 1978, с.45–48.
- Ходзинский А.Н. Формализация и алгоритм решения одной задачи распределения интегральных схем по конструктивным узлам ЭВМ. – В кн.: Дискретные системы управления. Сб. научн. тр. – Киев: ИК АН УССР, 1980, с.66–68.
- Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.Н. Диалоговый пакет программ ВЕКТОР-2. – Киев, 1981. – 55с. (Препринт/АН УССР, Ин-т кибернетики: 81-63).
- Ходзинский А.Н. Использование закона распределения значений цtлевой функции при решении задач комбинаторной оптимизации. – В кн.: Всесоюзный научно-практический семинар “Прикладные аспекты управления сложными системами”. Тезисы докладов. – Всесоюзный совет научно-технических обществ, 1983, с.225–226.
- Гуляницкий Л.Ф., Сергиенко И.В., Ходзинский А.Н. О принципах решения задач комбинаторной оптимизации в пакете программ ВЕКТОР-2. – В кн.: Моделирование и оптимизация проектных решений в САПР. Тезисы докладов V Всесоюзного совещания по автоматизации проектирования электротехнических устройств. Часть ІІ. Таллинский электротехнический з-д им. М.И. Калинина, 1983, с.37-39.
- Гуляницкий Л.Ф., Ходзинский А.Н. Два алгоритма решения задач на перестановках. – В кн.: Эффективная организация вычислений и численные методы. Сб. научн. тр. – Киев: ИК АН УССР, 1983, с.
. - Ходзинский А.Н. Статистические свойства критерия и их использование в алгоритмах решения задач комбинаторной оптимизации. – В кн.: Применение случайного поиска при решении прикладных задач. Тезисы докладов 3-го рабочего совещания “Статистические методы в угольной промышленности”. (Междуреченск, 12–16 марта 1984 года). – Кемерово: Кемеровский обласной совет НТО, 1984, с.41–42.
