Неформальная история лаборатории
дискретных экстремальных задач

Наша лаборатория начала свое существование в Институте Математики в феврале 1974 г. (Автор этой заметки числится в составе лаборатории с 11 сентября 1974 г., поэтому может считать себя свидетелем большей части "исторических событий", происшедших в жизни лаборатории за этот почти 25-летний период.) Основным направлением исследований с самого начала деятельности лаборатории была разработка эффективных алгоритмов точного или приближенного решения дискретных оптимизационных задач, возникающих в самых разных областях человеческой деятельности. Помимо исследований чисто теоретических дискретных моделей часто выполнялись так называемые "хоздоговорные" прикладные работы для конкретных заказчиков (таких как Искитимский машиностроительный завод, Новосибирский завод вентиляционных установок, Новосибирская швейная фабрика, и т.д. и т.п.) По-видимому, апогеем этой деятельности можно считать участие в разработке Проекта строительства БАМ, когда группа наших сотрудников во главе с В.А. Перепелицей (куда также входили Наташа Пузынина, Толя Сердюков и я) была командирована в Москву для обеспечения "теоретического обоснования" принятия важного государственного решения "О перенесении сроков окончания строительства БАМ" (с 1983 на 1987 год). - Из простейшей сетевой модели вытекало, что при заданных условиях финансирования (а также из-за технологических трудностей, связанных со строительством сложнейшего Северо-Муйского тоннеля) выполнить прежнее правительственное решение было никак невозможно. (Вероятно, это прежнее решение принималось без построения подобной "сети", а скорее всего, вообще "с потолка".) В течение месяца в номере гостиницы "Россия" на листах миллиметровки рисовались всевозможные сети, в Госплане и других ведомствах добывалась "важная информация" и также наносилась на миллиметровку, а молодые подающие надежды м.н.с.-ы были вхожи в такие "закрытые места", куда сейчас, спустя 20 с лишним лет, нас - постаревших и поседевших "ученых" - не пустят и на порог. Как обычное дело воспринимались тогда обеды в столовке Госплана или "буфете" Управления Делами при Совете Министров (хотя суп из шампиньонов, подаваемый в фарфоровых горшочках, или ананасовый сок воспринимались тогда - в 1976 году - как нечто экзотическое). Наш умудренный опытом старший товарищ (и старший научный сотрудник) Виталий Афанасьевич тогда говорил нам: "Смотрите, ребята, - вы целый месяц живете в одной из лучших московских гостиниц. Будет ли у вас еше когда-нибудь такая возможность?" - Тогда эти слова воспринимались как "старческое брюзжание" 38-летнего.

В один прекрасный пасмурный день нас провели через Спасскую башню в Кремль на совещание с заместителем Соломенцева, где мы должны были изложить высокому чиновнику результаты наших глубоких теоретических исследований. Помню длинный стол, сидящего во главе этого стола пожилого партийного деятеля с седой гривой, по-отечески выслушивающего лепет нашкодивших ученых мальчишек: академика Аганбегяна, будущих докторов Алексеева и Перепелицу, Сашу Кисельникова (сейчас он возглавляет "Комитет по экономической реформе" при Новосибирском областном Совете) и меня. (Не помню, был ли кто-то еще.) Когда Анатолий Михайлович (Алексеев) во время своего доклада произнес дрожащим голосом какую-то далеко не бесспорную фразу и я "в порядке дискуссии" - как это принято у нас на семинарах - вклинился в разговор, то получил под столом серию таких недвусмысленных пинков от Виталия Афанасьевича, что в конце концов догадался заткнуться. (Как говорил в свое время Киса Воробьянинов: "Я думаю, что спор здесь неуместен".) Другой же участник беседы - Абел Гезович - спокойно ответил мне "по-существу", и инцидент был благополучно исчерпан. Правда, когда мы выходили обратно через ворота Спасской башни на Красную площадь, академик меня в упор не замечал. И на следующие высокие совещания (если они были) меня уже не брали.

Затем несколько лет мы занимались такими глобальными задачами как задача хозяйственного освоения зоны (!?) БАМ и задача разработки Западно-Сибирского Нефте-Газового Комплекса (ЗСНГК). Естественно, это были оптимизационные задачи, где главной целью была реализация проекта "с минимальными затратами". (Хотя кто их тогда считал, эти самые "затраты"?!)

Однако всё вышесказанное относится к той стороне деятельности лаборатории, которую я не считаю основной. (Итог этой деятельности в виде "конечной народо-хозяйственной прибыли" подвела сама жизнь. Другой побочный продукт - в виде полученной нами грамоты Обкома комсомола - вряд ли можно считать достаточной компенсацией за "бесцельно прожитые годы".) Основу же деятельности лаборатории составляли и составляют те теоретические исследования и результаты, которые не зависят от сиюминутной коньюнктуры и потребностей высшего партийного начальства, и которым суждена более долгая (трудно судить, насколько счастливая) жизнь. Именно благодаря этим результатам наших патриархов - Н.И.Глебова, Э.Х.Гимади и В.А.Перепелицы - можно утверждать, что российская школа построения приближенных алгоритмов с гарантированными оценками родилась в Сибири в конце 60-х годов. Обзор этих результатов - как четко осознанное "направление" - был опубликован в юбилейном (посвященном 250-летию АН СССР - !!?) 12-м выпуске "Управляемых систем" в статье упомянутых трех авторов "Исследования по теории расписаний". В дальнейшем это направление было поддержано исследованиями их учеников - А.И.Сердюкова, С.Е.Гвоздева, С.В.Севастьянова, и других, более молодых и зеленых. (Достаточно упомянуть "студенческий" результат Толи Сердюкова - полиномиальный алгоритм решения задачи коммивояжера (с неравенством треугольника) с до сих пор непревзойденной оценкой точности 3/2. Этот результат по прошествии 20 с лишним лет стал классическим в дискретной оптимизации, хотя ссылаются на него как на результат Кристофидеса.) Чтобы не быть излишне скромным, следует сказать, что мои результаты по построению алгоритмов приближенного решения задач теории расписаний (с использованием их сведения к задачам компактного суммирования векторов) также лежат в русле этого направления.

Однако наибольший почет нашей лаборатории принесло (сегодня можно говорить об этом вполне определенно) первоначально как бы "побочное" направление исследований в недрах лаборатории - теория графов. "Побочное" потому, что алгоритмический подход с самого начала явно не доминировал в этих исследованиях, а предпочтение отдавалось неконструктивным аспектам в задачах исследования свойств и задачах раскраски графов. (Да и сама теория графов за серьезную науку тогда не считалась - по крайней мере, в рамках тогдашнего Отделения кибернетики.) Постепенно бывшие студенты НГУ - Саша Косточка и Олег Бородин - доросли до ученых мирового уровня, без которых не обходится ни одна мало-мальски серьезная международная конференция по теории графов, - причем в последнее время, частенько с пленарными докладами. (Их теперешние докторские степени - лишь формальное подтверждение этого факта.) Третья докторская - по теории графов и комбинаторике - вполне созрела у Димы Фон-Дер-Флаасса. (Трудно сказать, будет ли она дописана на земле Туманного Альбиона, где он сейчас находится.) Именно благодаря этим вышеупомянутым "локомотивам науки" (выпускающим в год по 10-15 статей) наша лаборатория выдвинулась в тройку лидирующих лабораторий Института. (Конечно, нельзя принижать и скромный вклад в это достижение остальных участников этого пост-социалистического соревнования.) И какие бы мнения ни были на этот счет у отдельных товарищей, в формировании нашей "Сибирской графской школы" (точнее, в ее "реанимации" - после отъезда Зыкова и Визинга) нельзя не признать очевидных заслуг Леонида Сергеевича Мельникова, чей спецкурс по теории графов сегодня является, наверное, одним из старейших и наиболее стабильных спецкурсов НГУ (я слушал его еще в 1970 году !), а спецсеминар "Теория графов" проходит по-прежнему по вторникам (всё в той же 344 комнате ИМ) аж с тех самых пор и скоро торжественно отметит свое 1000-ное заседание. Как обычно, оно вероятно будет посвящено нерешенным проблемам. (Впрочем, гораздо больше об истории семинара по теории графов может рассказать его бессменный секретарь Надежда Павловна Мазурова, - см. посвященную этому страничку.) Я думаю, что последняя страница этой славной истории еще не дописана ее участниками.

Наконец, недавнее вливание свежей струи в нашу лабораторию в лице Сережи Августиновича, я думаю, также обещает дать начало следующей интересной главе в истории нашей лаборатории. 

  Lab's home