Двойственные оценки для задачи о максимальном К-клабе

Двойственные оценки для задачи о максимальном К-клабе

Рассмотрены возможности формирования квадратичных постановок задачи о максимальном k-клабе и, соответственно, нахождения верхних двойственных оценок, получаемых с помощью техники Н.З. Шора. На примере задачи о максимальном 2-клабе показано, что неоднозначность построения соответствующих квадратичных...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2008
Hauptverfasser: Березовский, О.А., Жереб, К.А.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2008
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/12693
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Двойственные оценки для задачи о максимальном К-клабе / О.А. Березовский, К.А. Жереб // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 11-16. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-12693
record_format dspace
spelling Березовский, О.А.
Жереб, К.А.
2010-10-20T09:23:17Z
2010-10-20T09:23:17Z
2008
Двойственные оценки для задачи о максимальном К-клабе / О.А. Березовский, К.А. Жереб // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 11-16. — Бібліогр.: 4 назв. — рос.
XXXX-0013
https://nasplib.isofts.kiev.ua/handle/123456789/12693
519.8
Рассмотрены возможности формирования квадратичных постановок задачи о максимальном k-клабе и, соответственно, нахождения верхних двойственных оценок, получаемых с помощью техники Н.З. Шора. На примере задачи о максимальном 2-клабе показано, что неоднозначность построения соответствующих квадратичных задач (в том числе с учетом добавления функционально избыточных ограничений) предоставляет значительные возможности для уточнения двойственных оценок.
Розглянуті можливості формування квадратичних постановок задачі про максимальний k-клаб і, відповідно, знаходження верхніх двоїстих оцінок, які можна отримати за допомогою техніки Н.З. Шора. На прикладі задачі про максимальний 2-клаб показано, що неоднозначність побудови відповідних квадратичних задач (у тому числі з урахуванням додавання функціонально надлишкових обмежень) надає значні можливості для уточнення двоїстих оцінок.
The opportunities of constraining quadratic formulations of k-club problem and, accordingly, finding of upper dual bounds received by using Shor's engineering are considered. On an example of 2­club problem it's shown, that the ambiguity of construction of the appropriate quadratic problems (including in view of addition of functional superfluous restrictions) gives significant opportunities to improve of dual bounds.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Двойственные оценки для задачи о максимальном К-клабе
Двоїсті оцінки для задачі про максимальний K-клаб
Dual bounds for K-club problem
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Двойственные оценки для задачи о максимальном К-клабе
spellingShingle Двойственные оценки для задачи о максимальном К-клабе
Березовский, О.А.
Жереб, К.А.
title_short Двойственные оценки для задачи о максимальном К-клабе
title_full Двойственные оценки для задачи о максимальном К-клабе
title_fullStr Двойственные оценки для задачи о максимальном К-клабе
title_full_unstemmed Двойственные оценки для задачи о максимальном К-клабе
title_sort двойственные оценки для задачи о максимальном к-клабе
author Березовский, О.А.
Жереб, К.А.
author_facet Березовский, О.А.
Жереб, К.А.
publishDate 2008
language Russian
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Двоїсті оцінки для задачі про максимальний K-клаб
Dual bounds for K-club problem
description Рассмотрены возможности формирования квадратичных постановок задачи о максимальном k-клабе и, соответственно, нахождения верхних двойственных оценок, получаемых с помощью техники Н.З. Шора. На примере задачи о максимальном 2-клабе показано, что неоднозначность построения соответствующих квадратичных задач (в том числе с учетом добавления функционально избыточных ограничений) предоставляет значительные возможности для уточнения двойственных оценок. Розглянуті можливості формування квадратичних постановок задачі про максимальний k-клаб і, відповідно, знаходження верхніх двоїстих оцінок, які можна отримати за допомогою техніки Н.З. Шора. На прикладі задачі про максимальний 2-клаб показано, що неоднозначність побудови відповідних квадратичних задач (у тому числі з урахуванням додавання функціонально надлишкових обмежень) надає значні можливості для уточнення двоїстих оцінок. The opportunities of constraining quadratic formulations of k-club problem and, accordingly, finding of upper dual bounds received by using Shor's engineering are considered. On an example of 2­club problem it's shown, that the ambiguity of construction of the appropriate quadratic problems (including in view of addition of functional superfluous restrictions) gives significant opportunities to improve of dual bounds.
issn XXXX-0013
url https://nasplib.isofts.kiev.ua/handle/123456789/12693
citation_txt Двойственные оценки для задачи о максимальном К-клабе / О.А. Березовский, К.А. Жереб // Теорія оптимальних рішень: Зб. наук. пр. — 2008. — № 7. — С. 11-16. — Бібліогр.: 4 назв. — рос.
work_keys_str_mv AT berezovskiioa dvoistvennyeocenkidlâzadačiomaksimalʹnomkklabe
AT žerebka dvoistvennyeocenkidlâzadačiomaksimalʹnomkklabe
AT berezovskiioa dvoístíocínkidlâzadačípromaksimalʹniikklab
AT žerebka dvoístíocínkidlâzadačípromaksimalʹniikklab
AT berezovskiioa dualboundsforkclubproblem
AT žerebka dualboundsforkclubproblem
first_indexed 2025-11-25T21:02:34Z
last_indexed 2025-11-25T21:02:34Z
_version_ 1850545606459654144
fulltext Теорія оптимальних рішень. 2008, № 7 11 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассмотрены возможности фор- мирования квадратичных поста- новок задачи о максимальном k-клабе и, соответственно, на- хождения верхних двойственных оценок, получаемых с помощью техники Н.З. Шора. На примере задачи о максимальном 2-клабе показано, что неоднозначность построения соответствующих квадратичных задач (в том числе с учетом добавления функцио- нально избыточных ограничений) предоставляет значительные воз- можности для уточнения двой- ственных оценок.  О.А. Березовский, К.А. Жереб, 2008 ÓÄÊ 519.8 Î.À. ÁÅÐÅÇÎÂÑÊÈÉ, Ê.À. ÆÅÐÅÁ ÄÂÎÉÑÒÂÅÍÍÛÅ ÎÖÅÍÊÈ ÄËß ÇÀÄÀ×È Î ÌÀÊÑÈÌÀËÜÍÎÌ K-ÊËÀÁÅ∗∗∗∗ При исследовании сетевых структур (в со- циологии, медицине, биологии, транспорте и т.д.) для анализа связных подмножеств удоб- но строить графовые модели, использующие такие понятия как k-клика, k-клаб, k-плекс и др. [1]. Эти понятия введены для характери- стики структурных свойств выделяемого подмножества (определяют критерий связно- сти его элементов) и, по сути, могут рас- сматриваться как модификации достаточно известной кликовой модели [2], расширяя (с точки зрения "ослабления" связей, при 2≥k ) возможности при моделировании реальных ситуаций в сетях [3]. Возникающие при этом экстремальные задачи на графах как благо- даря растущему к ним практическому инте- ресу (сетевые задачи приобретают все боль- шую значимость в обществе), так и в силу своей NP-полноты привлекают внимание ис- следователей, исповедывающих различные математические школы. В отличие от боль- шинства авторов, которые при рассмотрении данных проблем не выходили за рамки ли- нейных моделей, мы предлагаем применять квадратичные модели, что позволит восполь- зоваться подходом академика Н.З. Шора для получения двойственных лагранжевых оце- нок с использованием функционально избы- точных ограничений [4]. Применение данно- го подхода приводит к относительно ∗ Работа выполнена при частичной финансо- вой поддержке гранта UKM2-2812-KV-06 (CRDF Cooperative Grants Program). О.А. БЕРЕЗОВСКИЙ, К.А. ЖЕРЕБ 12 Теорія оптимальних рішень. 2008, № 7 неплохим, а в ряде случаев и к точным оценкам решений задач [4]. Причем, в первом случае всегда остается надежда, что расширение использованной квад- ратичной постановки за счет введения (добавления) новых избыточных ограни- чений позволит улучшить полученную для нее оценку и привести к точному зна- чению по функционалу. Следует отметить, что этот подход ни в коем случае не сужает используемый для исследований математический аппарат – имеется в виду, что на базе расширенных квадратичных моделей можно строить и линей- ные модели. В данной работе рассмотрим возможности применения техники двойствен- ных квадратичных оценок на примере одной из "простейших" из вышеупомяну- тых кластерных задач – задачи о максимальном 2-клабе. Для начала сформули- руем задачу о максимальном k-клабе в общем виде. Пусть задан неориентированный граф ),( EVG с множеством вершин },,1{ nV K= и множеством ребер },:),{( VjVijiE ∈∈= . Под k-клабом графа ),( EVG подразумевают подмножество вершин графа ),( EVG , из каждой вер- шины которого можно попасть в другую не более чем через )1( −k точку этого подмножества, соединенных ребрами из множества E (при 1=k получаем опре- деление клики графа ),( EVG ). Задача о максимальном k-клабе заключается в выделении в графе ),( EVG k-клаба максимальной мощности (т. е. содержащего максимальное количество вершин). Эту задачу можно сформулировать в виде следующей задачи дискретного программирования [3]: ∑ ∈ = Vi ik xGw max)( (1) при ограничениях ∑ ∈ +≤+ ij l ij PPl l ijji yxx : 1 Eji ∉∀ ),( , (2) l ijp yx ≥ )( l ijPVp ∈∀ , ij l ij PPl ∈∀ : , Eji ∉∀ ),( , (3) }1,0{∈ix Vi ∈ , (4) }1,0{∈l ijy ij l ij PP ∈∀ , Eji ∉∀ ),( . (5) Здесь каждой вершине графа соответствует булевая переменная ix , которая принимает значение 1, если вершина i принадлежит k-клабу, и 0, в противном случае; l l ijij PP }{= – множество всех путей между вершинами i и j в графе G , длина которых не более k, а l ijP – элемент этого множества (путь с номером l), которому ставится в соответствие булевая переменная l ijy – равна 1 только в том случае, если все вершины px данного пути равны 1 (т.е. принадлежат k-клабу). Смысл ограничений (2) – (5) состоит в следующем: если две вершины i ДВОЙСТВЕННЫЕ ОЦЕНКИ ДЛЯ ЗАДАЧИ О МАКСИМАЛЬНОМ K-КЛАБЕ Теорія оптимальних рішень. 2008, № 7 13 и j принадлежат k-клабу, то ∑ ∈ ≤ ij l ij PPl l ijy : 1 (из условия (2)), т. е. существует хотя бы один путь между данными вершинами (длина которого не более k), все верши- ны которого также принадлежат k-клабу ( l ijp yx ≥ ). Если же такого пути не су- ществует, то 0 : =∑ ∈ ij l ij PPl l ijy и согласно (2) 1≤+ ji xx , т. е. хотя бы одна вершина не принадлежит k-клабу. Построение квадратичной постановки рассматриваемой задачи далеко не- однозначно и, на сегодняшний день, не имеет общего условия предпочтительно- сти той или иной из них (кроме, конечно, критерия накопления ограничений, который, однако, может "раздуть" размеры даже небольшой задачи до неприем- лемой с вычислительной точки зрения размерности). Понятно, что самая про- стая квадратичная постановка с непрерывными переменными получается из за- дачи (1) – (5) после выражения условий булевости переменных квадратичными равенствами 02 =− ii xx , Vi ∈ , и 0)( 2 =− l ij l ij yy , ij l ij PP ∈∀ , Eji ∉∀ ),( . Если воспользоваться другими приемами, например, результатами различных допус- тимых перемножений линейных выражений, которые либо явно присутствуют в условиях задачи (1) – (5), либо являются их следствиями (например, 10 ≤≤ ix или 10 ≤≤ l ijy ), то соответствующие ограничения можно заменить квадратич- ными и получить ряд других квадратичных формулировок задачи о максималь- ном k-клабе даже без наличия каких-либо функционально избыточных ограни- чений. В случае если в постановку включать группу или даже все из таких воз- можных ограничений-следствий (при этом появятся и функционально избыточ- ные ограничения), то двойственная квадратичная оценка как минимум не ухуд- шится, а в большинстве случаев улучшится за счет большей "мобильности" мат- рицы функции Лагранжа (в смысле увеличения области положительной опреде- ленности квадратичной формы функции Лагранжа). Сформулируем одну из таких квадратичных постановок задачи о макси- мальном k-клабе (без функционально избыточных ограничений): ∑ ∈ = Vi ik xGw max)( (6) при ограничениях ∑ ∈ ≤ ij l ij PPl l ijiji yxxx : Eji ∉∀ ),( , (7) l ijp yx ≥ )( l ijPVp ∈∀ , ij l ij PPl ∈∀ : , Eji ∉∀ ),( , (8) 02 =− ii xx , Vi ∈ , (9) О.А. БЕРЕЗОВСКИЙ, К.А. ЖЕРЕБ 14 Теорія оптимальних рішень. 2008, № 7 0)( 2 =− l ij l ij yy , ij l ij PP ∈∀ , Eji ∉∀ ),( . (10) В данном случае ограничение (7) получено путем умножения обеих частей неравенства (2) на ix с учетом равенства 02 =− ii xx (заметим, что для каждой пары Eji ∉),( получаем два неравенства – как при умножении на ix , так и на jx ). При этом смысл ограничения (7) остался тем же, что и у ограничения (2). При выборе приведенной постановки мы руководствовались следующими соображениями. Во-первых, стремлением увеличить количество двойственных переменных в матрице функции Лагранжа, которые могли бы помочь расши- рить ее область положительной определенности (например, ограничения (7) это позволяют, в то время как замена (8) на l ij l ijp yyx ≥ ничего не дает). Во-вторых, нежеланием значительно увеличивать количество ограничений (этим объясняет- ся отсутствие в постановке функционально избыточных ограничений, а также отказ от полиномиальной постановки задачи о максимальном k-клабе, которая с одной стороны содержит только переменные ix , Vi ∈ , но влечет за собой по- следующее значительное увеличение переменных при сведении к квадратично- му виду). И, в-третьих, тем, что ограничение (7) активно (в том смысле, что мо- жет превращаться в равенство) на большей области определения прямых пере- менных задачи, чем другие возможные ограничения-следствия (например, ∑ ∈ ≤ ij l ij PPl l ijji yxx : , 2 :           ≤ ∑ ∈ ij l ij PPl l ijji yxx , ( ) 2 : 2 1           +≤+ ∑ ∈ ij l ij PPl l ijji yxx и т.п.), что также предполагает большую гибкость при работе с матрицей функ- ции Лагранжа, а значит и вероятность получения более точных оценок. В частном случае, когда 2=k (заметим, что это справедливо и при 3=k ), задача о максимальном k-клабе значительно упрощается – переменные l ijy ис- ключаются (каждому пути l соответствует только одна вершина и перемен- ные px , l ijy принимают один и тот же смысл) и размерность задачи становится равной ||V . Для данной задачи выпишем два варианта квадратичной постанов- ки из упоминавшихся выше: – вариант 1 (простейший) ∑ ∈ = Vi ixGw max)(2 (11) при ограничениях ∑ ∈ +≤+ ),( 1 jiNp pji xxx Eji ∉∀ ),( , (12) 02 =− ii xx , Vi ∈ . (13) ДВОЙСТВЕННЫЕ ОЦЕНКИ ДЛЯ ЗАДАЧИ О МАКСИМАЛЬНОМ K-КЛАБЕ Теорія оптимальних рішень. 2008, № 7 15 – вариант 2 (следует из задачи (6) – (10)) ∑ ∈ = Vi ixGw max)(2 (14) при ограничениях ∑ ∈ ≤ ),( jiNp piji xxxx , ∑ ∈ ≤ ),( jiNp pjji xxxx Eji ∉∀ ),( , (15) 02 =− ii xx , Vi ∈ , (16) где )()(),( jNiNjiN ∩= обозначает множество вершин графа, соединенных ребрами как с i -й вершиной ( )(iN ), так и с j -й вершиной ( )( jN ). На основе приведенных задач (11) – (13) и (14) – (16) проиллюстрируем по- ведение двойственных оценок Шора на двух специально подобранных тестовых примерах. Обозначим двойственную оценку для задачи (11) – (13) – 1ψ , а для задачи (14) – (16) – 2ψ . Пример 1. Пусть задан граф, который представляет собой цикл из 9 вер- шин, дополненный еще одним ребром, соединяющим вершины 2 и 4, т. е. мно- жество ребер равно )}4,2(),1,9(),9,8(),8,7(),7,6(),6,5(),5,4(),4,3(),3,2(),2,1{(=E . Мощность максимального 2-клаба для этого графа равна 4)(2 =Gw и достига- ется в точках (1,1,1,1,0,0,0,0,0) и (0,1,1,1,1,0,0,0,0). Двойственная оценка для за- дачи (11) – (13) 5.41 =ψ не является точной (отметим, что она совпала с линей- ной верхней оценкой, которая получается в результате релаксации задачи при замене ограничений (13) на 10 ≤≤ ix , Vi ∈ ). Для второго варианта квадратич- ной постановки оценка улучшилась и, более того, стала точной – 0.42 =ψ , что показывает преимущество квадратичной постановки (14) – (16). Однако она то- же не всегда будет точной. Покажем это на следующем примере. Пример 2. Граф представляет собой цикл из 7 вершин. Для этого графа 3)(2 =Gw и исходная задача имеет семь решений. Оценка 5.31 =ψ . Во втором случае оценка улучшилась – 3317667.32 =ψ , но также не является точной. Од- нако, как уже отмечалось, для таких случаев в технике двойственных квадра- тичных оценок [4] в запасе имеется достаточно успешный аппарат расширения квадратичных задач за счет функционально избыточных ограничений. Запишем новые ограничения вида lljli xxxxx ≤+ , Eji ∉∀ ),( , }{),( ∅=jiN , (17) которые строятся домножением линейных ограничений (12) для пар вершин i и j , между которыми нет пути длинной менее трех ребер (т.е. для которых спра- ведливо 0 ),( =∑ ∈ jiNp px ), на переменные lx . После добавления этих ограничений в задачу (14) – (16) получаем третий вариант квадратичной постановки для задачи О.А. БЕРЕЗОВСКИЙ, К.А. ЖЕРЕБ 16 Теорія оптимальних рішень. 2008, № 7 о максимальном 2-клабе – задачу (14) – (17), двойственная оценка для которой оказалась точной 0.33 =ψ . На предложенных тестовых примерах прослеживаются возможности квад- ратичных моделей, неоднозначность построения которых (в том числе с исполь- зованием функционально избыточных ограничений) предоставляет значитель- ные возможности для уточнения двойственных лагранжевых оценок. Можно сделать вывод, что применение техники двойственных квадратичных оценок Шора [4] для рассматриваемого класса задач (впрочем, как и для всех квадра- тичных задач) представляет определенный интерес и является достаточно пер- спективным, однако при этом приобретает значимость решение следующих во- просов: каким образом добавлять функционально избыточные ограничения (по какому правилу), чтобы не вводить слишком много дополнительных перемен- ных, общий критерий возможности достижения точной оценки и т.д. О.А. Березовський, К.А. Жереб ДВОЇСТІ ОЦІНКИ ДЛЯ ЗАДАЧІ ПРО МАКСИМАЛЬНИЙ K-КЛАБ Розглянуті можливості формування квадратичних постановок задачі про максимальний k-клаб і, відповідно, знаходження верхніх двоїстих оцінок, які можна отримати за допомогою техніки Н.З. Шора. На прикладі задачі про максимальний 2-клаб показано, що неоднознач- ність побудови відповідних квадратичних задач (у тому числі з урахуванням додавання функ- ціонально надлишкових обмежень) надає значні можливості для уточнення двоїстих оцінок. O.A. Berezovskyi, K. A. Zhereb DUAL BOUNDS FOR K-CLUB PROBLEM The opportunities of constraining quadratic formulations of k-club problem and, accordingly, find- ing of upper dual bounds received by using Shor's engineering are considered. On an example of 2- club problem it's shown, that the ambiguity of construction of the appropriate quadratic problems (including in view of addition of functional superfluous restrictions) gives significant opportunities to improve of dual bounds. 1. Mokken R. Cliques, clubs and clans // Quality and Quantity. – 1979. – Vol. 13. – P. 161–173. 2. Luce R., Perry A. A method of matrix analysis of group structure // Psychometrika. – 1949. – Vol. 14. – P. 95–116. 3. Balansundaram B., Butenko S., Trukhanov S. Novel approaches for analyzing biological networks // J. of Combinatorial Opt. – 2005. – Vol. 10. – P. 23–39. 4. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht, Kluwer, 1998. – 394 p. Получено 12.03.2008

Ähnliche Einträge