М.Ш. Левин

О реконфигурации решений в комбинаторной оптимизации

В статье рассматривается новый класс задач модификации в комбинаторной оптимизации. Подход заключается в реконфигурации (реструктуризации) решений (в виде множества/структуры). Две характеристики процесса реконфигурации решения исследуются: (а) стоимость изменения решения, (б) близость получаемого реконфигурированного (реструктурированного) решения к некоторому целевому решению. Предлагаются три типа задач реконфигурации: (1) одностадийная реконфигурация решения, (2) многостадийная реконфигурация решения, (3) реконфигурация при изменении набора элементов решения. Рассматриваются постановки задачи с одним или многими критериями. Задачи реконфигурации решений соответствуют прикладным задачам перепроектирования (улучшения, обновления) модульных систем. Предложенный подход применен к двум задачам комбинаторной оптимизации: задаче о рюкзаке, задаче блочного рюкзака. Численные примеры иллюстрируют задачи реконфигурации и схемы решения.

КЛЮЧЕВЫЕ СЛОВА: комбинаторная оптимизация, реконфигурация, реструктуризация, рюкзак, блочный рюкзак, эвристики