И. В. Романовский: Мои научные интересы

У меня научные интересы легкомысленно часто изменялись, и от каждого слоя что-то оставалось, поэтому интересы разнообразные, даже слишком. Перечислим основные темы.

Дискретная оптимизация

Одна из проблем, к которой интерес сохранился навсегда — это дискретные задачи оптимизации. Понятно, что в общем виде задача нахождения точного максимума (или минимума) некоторой целевой функции на конечном, но ужасающе большом множестве допустимых решений не имеет надежды на успех. Речь может идти только о каких-то классах задач. Среди этих классов очень важны задачи, приводящие к динамическому программированию, и задачи в которых эффективны методы неявного перебора, в частности, очень популярный метод ветвей и границ.
Другое направление, которое сейчас стало особенно популярным — это построение и опробование эффективных приближенных методов, которые за приемлемое время давали бы решение, не слишком сильно отличающееся от точного оптимума. За последние годы приобрели большую популярность некоторые специальные методы: генетические методы, в которых используются ассоциации с молекулярной генетикой, методы табу (поиска с временными запретами), совершенствующие точные методы неявного перебора.
Очень важным разделом в проблеме дискретной оптимизации я считаю нахождение субоптимальных решений. В некоторых задачах оптимизации нам удается найти точное оптимальное решение, если мы позволяем себе несколько изменить задачу, — например, изменить целевую функцию или «забыть» о каких-либо ограничениях.

Компьютерная реализация оптимизационных алгоритмов

Пакет симплекс-метода

Когда только еще появлялись в нашем распоряжении вычислительные машины и языки программирования, ощущалась острая необходимость в создании программ, реализующих основные вычислительные действия бурно развивавшихся численных методов оптимизации.
Быстро появилось довольно много коммерческих пакетов, особенно американских, с четко фиксированными форматами ввода данных. Мы пошли по другому пути и стали создавать программные средства, написанные на алгоритмических языках высокого уровня (первоначально это был Алгол-60, затем появились ПЛ-1, Си, почему-то много позднее Паскаль. Нам было удобнее «подгонять» программу под задачу и делать специализированные варианты симплекс-метода, например, для задач линейного и плоского раскроя, задачи маршрутизации автомобильных перевозок, различных вариантов транспортной задачи.

В дальнейшем захотелось упростить писание таких программ, и нам пришлась очень кстати идея объектно-ориентированного программирования, которая воплотилась, в частности, в языках Си++ и Java, и в системе Дельфи.
Недавно мы разработали пакет Симплекс-метод, в котором полностью выдерживается идеалогия объектно-ориентированного программирования, причем пакет является открытым — в него легко добавляются программные модули (в форме DLL — библиотек динамического присоединения), которые могут понадобиться для новых практических задач. Для дальнейшего развития этого пакета нам очень нужны свежие кадры.

Решение больших теоретико-графовых и комбинаторных задач

Попрежнему интересным полем деятельности и в практическом и в теоретическом отношении является создание программных средств для решения оптимизационных задач большого размера, носящих комбинаторный характер. Часто такие задачи связаны с теорией графов. Например, в связи с одним из приложений нам потребовалось разработать (и пока мы этого не умеем) методы построения таких упорядочений конечного множества, которые не противоречили бы заданному на множестве частичному порядку и максимизировали сумму ценностей элементов с весами, зависящими от места в искомом упорядочении.

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

Компьютерная полиграфия


ххххххххххххххххххххххххххххххххххххххххххх

Развитие ТеХа
ххххххххххххххххххххххххххххххххххххххххххх

Развитие PostScript
ххххххххххххххххххххххххххххххххххххххххххх

Повышение эффективности работы с HTML и родственными языками
ххххххххххххххххххххххххххххххххххххххххххх

Использование компьютеров в обучении



Создание новых курсов и обучающих средств.
ххххххххххххххххххххххххххххххххххххххххххх