Роланд Хильдебранд

Университет Гренобль-Альпы Научный сотрудник

Усиление релаксаций в бинарном программировании

Многие проблемы, возникающие на практике, требуют принятия решений типа да/нет или сводятся к таким решениям. Например, обрабатывать ли заказ i на станке j, перевозить ли груз i в день j, выдавать ли клиенту i кредит и т.д. При формализации таких проблем возникают оптимизационные задачи с бинарными переменными, которые относятся к классу смешанно-целочисленных программ. Обычно такие задачи решаются методами ограничений и ветвлений. Однако, бинарность переменных делает такие методы в классической реализации менее эффективными. С другой стороны, именно бинарность переменных делает возможными приёмы, в том числе из полиномиальной оптимизации, сильно улучшающие гарантии на качество решения. В этой презентации мы сделаем обзор таких приёмов и продемонстрируем их эффективность на конкретном примере из практики.

С октября 2004 научный сотрудник CNRS в Лаборатории Жан Кунцман (до 2007 г. Лаборатория Моделизации и Вычислений) Университет Гренобль-Альпы, Франция. Июнь 2013 – июнь 2016 Институт Вейерштрасса, Берлин (группа В.Г. Спокойного). Сентябрь 2003 – сентябрь 2004 пост-док в Лаборатории Моделизации и Вычислений. Сентябрь 2002 – август 2003 CORE fellow в Центре Исследования Операций и Эконометрики Католический Университет Лёвен, Лувен-ля-Нёв, Бельгия. Март 2002 – август 2002 пост-док в Центре Системной Инженерии и Прикладной Механики (CESAME), Католический Университет Лёвен. Март 2001 – март 2002 пост-док в CESAME, Католический Университет Лёвен, со стипендией Европейской Исследовательской Сети по Идентификации Систем (ERNSI).