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

М.Ш. Левин,
 вед. н. сотр., к.т.н., mslevin@acm.org,
ИППИ РАН, г. Москва

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

 

New approach to solution reconfiguration (change of solution elements and/or structure over the elements) in combinatorial optimization is suggested (knapsack problem, multiple choice problem, clustering, sorting, assignment/allocation problem, morphological clique problem, minimum spanning tree problems, etc.). Two criteria are examined: (a) cost of solution change, (b) proximity to goal optimal solution at the next stage of problem solving. Two problem kinds are considered: (1) one-stage problem, (2) multistage problem (i.e., design of solution trajectory).

Введение

В настоящее время известны следующие подходы к изменению решений в комбинаторной оптимизации: (1) незначительная коррекция решений задач (т.е., локальные изменения) в рамках методов локальной оптимизации [1,3], (2) реоптимизация решений с целью улучшения значения целевой функции на рассматриваемом решении [2], (3) задачи изменения решения с целью получения требуемых свойств решения (например, требуемой связности сети) (augmentation) [4], (4) изменение решений в рамках решения динамических задач (в реальном времени) [5,8]. 

Предлагаемый новый подход направлен на реконфигурацию решений (т.е., изменение элементов решения и/или структуры на этих элементах) в задачах комбинаторной оптимизации с учетом использования двух основных критериев (стоимость изменения решения, близость получаемого решения к целевому оптимальному решению на следующем этапе решения задачи) [6,7]. Исследуются три типа постановок: (1) «базовая» одноэтапная задача, (2) многоэтапная задача (т.е., построение траектории решений), (3) реконфигурация решения при изменении исходного множества элементов в исследуемой задаче. Подход применяется к широкому классу задач комбинаторной оптимизации, включая следующие: задачи рюкзачного типа, задачи минимальных покрывающих деревьев, задачи кластеризации, многокритериальное ранжирование, задачи назначения/размещения и раскраски графов, задачи упаковки). Данная работа поддержана РФФИ (проект 15-07-01241а).

1. Одноэтапная задача

Задача реконфигурации (базовая» одноэтапная задача) имеет следующий вид: (1) построение оптимального решения исследуемой исходной задачи S0; (2) построение оптимального решения исследуемой задачи на следующем этапе (целевое решение) S1; (3) построение реконфигурируемого решения S* с учетом двух критериев: (а) минимизация стоимости изменения решения: (min c(S0 -> S*)), (б) близость реконфигурируемого решения S* к целевому оптимальному решению на следующем этапе решения задачи (min d(S0,S*)). Рисунок 1 и Рисунок 2 иллюстрируют данную постановку.

                                                                                   

Рис. 1  Схема одноэтапной реконфигурации

Можно рассматривать три формальные постановки:

Постановка 1:  min c(S0 -> S*) при условии d(S0,S*) <= D.

Постановка 2:  min d(S0,S*)  при условии c(S0 -> S*) <= C.

Постановка 3 (две целевые функции):  min c(S0 -> S*), min d(S0,S*).

            

Рис. 2  Иллюстрация одноэтапной реконфигурации

Простейшие версии задачи реконфигурации сводятся к многокритериальным моделям рюкзачного типа: (i) генерация множества возможных изменений в решении S0, (ii) отбор подмножества изменений в решении S0 с учетом некоторых ограничений и указанных критериев.

2. Многоэтапная задача

В задаче многоэтапной реконфигурации решения проводится поиск оптимального решения оптимизационной задачи на каждом этапе (S0,S1,S2,…,Sn) и построение траектории реконфигурируемых решений <S*1,S*2,…,S*n>. В данном случае необходимо использовать многоуровневую схему решения. Рисунок 3 иллюстрирует данную многоэтапную задачу.

                                                                          

Рис. 3  Иллюстрация многоэтапной реконфигурации

Заключение

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

Литература

1.  E. Aarts, J.K. Lenstra (eds), Local Search in Combinatorial Optimization. Princeton Univ. Press, 2003.

2.  C. Archetti, L. Bertazzi, M.G. Speranza, Reoptimizing the traveling salesman problem. Networks 42(3), 154-159, 2003.

3.  C. Blum, A. Roli, Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Computing Surveys, 35(3), 268-308, 2003.

4.  K.P. Eswaran, R.E. Tarjan, Augmentation problems. SIAM J. on Computing 5(4), 653-665, 1976.

5.  P. van Hentenruck, R. Bent, Online Stochastic Combinatorial Optimization. MIT Press, 2009.

6.  M.Sh. Levin, Towards combinatorial clustering: preliminary research survey. Electr. preprint, 2015. http://arxiv.org/abs/1505.07872 [cs.AI]

7.  M.Sh. Levin, Towards integrated glance to restructuring in combinatorial optimization. Electr. preprint, 2015. http://arxiv.org/abs/1512.06427 [cs.AI]

8.  S. Yang, Y. Jiang, T.T. Nguyen, Metaheuristics for dynamic combinatorial optimization problems. IMA J. of Manag. Math., 24(4), 451-480, 2013.