مساله حداکثر برش MAXCUT: مقایسه رهاسازی نیمه معین Semi-definite programming با رهاسازی خطی


برنامه‌ریزی نیمه‌معین semi-definite programming یا به‌اختصار SDP کلاسی از بهینه‌سازی محدب convex optimization است که کاربرد آن در علم تحقیق در عملیات بسیار موفق بوده است. پوسته عدد صحیح مسائل برنامه‌ریزی عدد صحیح را می‌توان با دقت بالایی با برنامه‌ریزی نیمه معین تقریب زد. در این پست قصد داریم به مسئله حداکثر برش MAXCUT در تئوری گراف پرداخته و رهاسازی نیمه‌معین آن را با رهاسازی خطی مقایسه نماییم.

مسئله حداکثر برش عبارت است از پیدا کردن برشی با وزن بیشینه در گراف که به دو زیرمجموعه افزار شود. گومنز و ویلیامسون Goemans-Williamson در سال ١٩٩۵ با به‌کارگیری برنامه‌ریزی نیمه‌معین، الگوریتمی برای این مسئله ارائه دادند که برش بیشینه یک گراف را با تقریب ۰/۸۷۸۵ در زمان چندجمله‌ای محاسبه می‌کند. این جزء اولین و مهم‌ترین دستاوردهای بهینه‌سازی نیمه‌معین بود. در دو دهه گذشته برنامه‌ریزی نیمه‌معین به یکی از مهم‌ترین ابزارها در بهینه‌سازی ترکیباتی و الگوریتم‌های تقریبی تبدیل شده است.

متغیر \( x \) رئوس مختلف را به دو بخش محصورشده و خارج از حصار تقسیم می‌کند. متغیر \(z\) نشان می‌دهد که آیا برش از یال متناظر عبور کرده است یا نه.

$$ \textbf{maximize} \quad \sum_{u,v \in E} w_{uv} z_{uv} \\ \textbf{subject to} \quad z_{uv} \le x_u + x_v, \qquad \forall u,v \in E \\ z_{uv} \le 2-(x_u + x_v), \qquad \forall u,v \in E \\ x_i \in \{0,1\}, \qquad \forall i \in E \\ z_{uv} \in \{0,1\}, \qquad \forall u,v \in E $$

با رهاسازی این دو متغیر باینری جواب زیر حاصل خواهد شد:

$$x_v = \frac{1}{2}, \qquad \forall v \in E$$

و می‌توان اثبات کرد که:

$$\textbf{OPT}^* \le \frac{1}{2} \textbf{OPT}^\textbf{LP-Relaxed}+\epsilon$$

ملاحظه می‌شود که رهاسازی خطی بدترین جواب ممکن و کران غیرقابل قبولی را برای مساله اصلی ارائه می‌کند. حال همین مساله را به صورت برنامه‌ریزی نیمه معین مدل می‌نماییم. متغیر دیگری تحت عنوان \(z_i\) که تنها مقادیر ۱- و ۱+ می‌پذیرد را تعریف می‌نماییم.

$$z_i= \begin{cases} +1, & \text{if the}\ i\text{th vertex in}\ V \\ -1, & \text{if the}\ i\text{th vertex in}\ U \\ \end{cases}$$

به این ترتیب معادل درجه دوم مساله حداکثر برش به صورت زیر بازنویسی می‌شود:

$$\textbf{maximize} \frac{1}{2} \sum_{(i,j) \in E} w_{ij} (1-v_i v_j) \\ v_i \in \{-1,+1\} \quad \forall i \in E$$

ابتدا رهاسازی را بر روی متغیر \(v_i\) اعمال می‌کنیم.

$$\|v_i\|^2 = v_i I v_j = Diag(X) = e$$

از طرفی داریم:

$$w_{ij} = W$$

بنابراین مدل رهاشده‌ی نیمه‌معین مساله حداکثر برش به صورت زیر بازنویسی می‌شود:

$$\textbf{maximize} \quad Tr(WX) \\ \textbf{subject to} \quad Diag(X) = e \\ Rank(X) =2 \\ X \in S^n_+$$

رهاسازی دوم بر روی محدودیت \( Rank(X) =2\) که حاصل از ماتریس حادث گراف دارای حداکثر برش است اعمال می‌شود (حذف این محدودیت). توجه شود که متغیر ماتریسی \(X\) در فضای مخروط نیمه‌معین قرار گرفته است. همچنین بردار \(e\) یک بردار یکه می‌باشد.

در نهایت این مدل را در نرم‌افزار متلب مجهز به افزونه‌های CVX کدنویسی می‌نماییم.

cvx_begin sdp
variable X(n,n) symmetric
minimize( trace( X*W ) )
diag(X) == ones(n,1);
X >= 0; %semi-definite cone
cvx_end

پس از حل مدل رابطه‌ی زیر برای مدل نیمه‌معین مشهود می‌باشد:

$$  \textbf{OPT}^\textbf{SDP-Relaxed}*0.878 \le \textbf{OPT}^* \le \textbf{OPT}^\textbf{SDP-Relaxed} $$

0 Comments
Inline Feedbacks
View all comments