آزادسازی در برنامه‌ریزی خطی

الگو:بدون منبع الگو:سره‌نویسی افراطی در ریاضی و دانش رایانه، واهِلِش به برنامه‌نویسی خطی برنامه‌ای دُرُست (integer program) را به برنامه‌ای خطی می‌ترادیساند. در این ترادیسی، هر متغیر $x_i\in \{0,1\}$ در برنامهٔ درست با متغیری خطی $0\le x_i\le 1$ جایگزین می‌شود. این واهلش پرسمانی ان‌پی سخت را به پرسمانی خطی که در زمانی چند جمله‌ای حل می‌شود می‌ترادیساند. پاسخ به برنامهٔ خطی به دست آمده، اطلاع‌های سودمندی را دربارهٔ برنامهٔ درست اصلی فراهم می‌آورد.

برنامه‌ای درست و واهلش خطی این برنامه.

نمونه

برای نمونه، به پرسمان پوشش مجموعه می‌پردازیم. مجموعه‌ای مانند $F$ و زیرمجموعه‌های $S_0,S_1,...\subseteq U$ از این مجموعه داده شده‌اند. این پرسمان شماری از $S_i$ها را می‌جوید که یکایش (اجتماع) این زیرمجموعه‌ها مجموعه $F$خواهد بود.

در برنامهٔ درست برای پوشش مجموعه، برای هر زیرمجموعهٔ $S_i$ متغیری بولی $x_i$ داریم.

یکایش زیرمجموعه‌های گزینش شده باید برابر با $F$ باشد. به سخنی دیگر، هر $e_j\in F$ باید در این یکایش باشد: $\sum _{\{i|e_j\in S_i\}}{x}_j\ge 1$. این پاوند را پاوند یکایش می‌نامیم.

هم‌چنین، پاوندِ $x_i\in \{0,1\}$ برای هر متغیر $x_i$ نشان می‌دهد که آیا زیرمجموعه $S_i$ در پاسخ خواهد بود یا نه. به سخنی دیگرِ، ارزش یک/صفر برای $x_i$ نشان می‌دهد که زیرمجموعهٔ $S_i$ در پوشش هست/نیست. این پاوند را پاوند بولی می‌نامیم.

پرسمان کم‌ترین شمار زیرمجموعه‌ها را می‌جوید: $\min \sum _i{x}_i$.

واهلش به برنامهٔ خطی هر پاوند بولی $x_i\in \{0,1\}$ را با پاوند $0\le x_i\le 1$ جایگزین می‌کند. برنامهٔ خطی به دست آمده وزنی را برای هر زیرمجموعه فرضیده است؛ ولی، پاوند یکایش یکسان می‌ماند. در پاسخ به این برنامهٔ خطی، جمع وزن همهٔ زیرمجموعه‌هایی چون $S_i$ که دربردارندهٔ عضو $e_j\in F$ برابر با یک خواهند بود.

به این نمونه از پوشش مجموعه‌ای بنگرید: مجموعهٔ $F=\{a,b,c\}$ و زیرمجموعه‌های $S_1=\{a,b\},S_2=\{b,c\},S_3=\{a,c\}$ را داریم. در برنامهٔ درست، سه متغیر $x_1,x_2,x_3$ خواهیم داشت. برای هر کدام از $a,b,c\in F$ یک پاوند یکایش هست. برای نمونه، برای $a$ پاوندِ $x_1+x_3\ge 1$ را داریم. هم‌چنین، برای هر $S_i$ یک پاوند بولی $0\le x_i\le 1$ داریم.

گزینش هر جفت از زیرمجموعه‌های $S_1,S_2,S_3$ پاسخی بهین است. به سخنی دیگر، هر یک از $\{S_1,S_2\}$، $\{S_1,S_3\}$ یا $\{S_2,S_3\}$ یک پوشش مجموعه‌ای کمینه است؛ بنابراین پاسخ کمینه برای برنامهٔ درست برابر است با $2$.

ولی، پاسخی بهین به برنامهٔ خطی $\frac{3}{2}$ است. در این پاسخ، هر $x_i$ دارای ارزش $\frac{1}{2}$ است. این پاسخ پاوندهای یکایش را برآورده می‌کند.

هم‌سنجی پاسخ واهلش و برنامه‌ی درست

اگر در پاسخ بهین به برنامه‌ی خطی، هر متغیر ارزشی صفر یا یک بگیرد، این پاسخ پاسخی بهین برای برنامه‌ی درست نیز خواهد بود. با این همه،‌ ما پرسمان‌های اندکی با چینن پاسخ‌هایی داریم.

چون هر برنامه‌ی درست زیرمجموعه‌ای از برنامه‌ای خطی است،‌ پاسخ‌ها به برنامه‌ی درست نیز زیرمجموعه‌ای از پاسخ‌ها به برنامه‌ی خطی‌اند. اگر برنامه‌ی درست بیشینه‌سازی باشد،‌ پاسخ بهین به برنامه‌ی خطی همواره بزرگ‌تر از پاسخ بهین به برنامه‌ی اصلی است. به همین سان،‌ اگر برنامه‌ی درست کمینه‌سازی باشد،‌ پاسخ به برنامه ی خطی همواره کوچک‌تر از برنامه‌ی اصلی است. به سخنی دیگر،‌ پاسخ به برنامه‌ی خطی واهلیده همواره کرانی بالا (پایین) برای برنامه‌ای درست بیشینه‌سازی (کمینه‌سازی) است.

در نمونه‌ی بالا برای پوشش مجموعه‌ی،‌ پاسخ بهین خطی برابر بود با $\frac{3}{2}$. چون پرسمان پوشش مجموعه،‌ پرسمانی کمینه‌سازی است،‌ پاسخ بهین برای برنامه‌ی درست همواره بزرگ‌تر یا برابر با $\frac{3}{2}$ خواهد بود. افزون بر این،‌ چون هر متغیر در برنامه‌ی درست می‌تواند ارزش صفر یا یک داشته باشد،‌ دست کم باید دو متغیر با ارزش یک در پاسخ بهین باشند. بنابراین، می‌توان کران پایین برای برنامه‌ی درست را به کرانی تنگ‌تر بهبود داد. این کران برابر با ۲ است.

تقریب‌زنی و گاف درستالی

واهلش به برنامه‌‌ی خطی،‌ شیوه‌ای استاندارد برای طراحی الگوریتم‌های تقریبی است. گاف درستالی (integral gap) مفهومی کلیدی در این زمینه است. در واهلش، گاف درستالی نسبت بیشینه میان برنامه‌ی درست و برنامه‌ی خطی را نشان می‌دهد. اگر $M_d$ پاسخ بهین برای برنامه‌ی درست و اگر $M_v$ پاسخ بهین برای برنامه‌ی خطی باشند،‌ گاف درستالی در کمینه‌سازی به دیسه‌ی $GD=\frac{M_d}{M_v}$ تعریف می‌شود و در بیشینه‌سازی برابر است با $GD=\frac{M_v}{M_d}$. بنابراین، گاف درستالی همواره بزرگ‌تر از یک است. در نمونه‌ی بالا چون پرسمان کمینه‌سازی،‌گاف درستالی برابر است با $\frac{4}{3}$.

گاف درستالی کاربرد فراوانی برای یافتن نسبت تقریب در الگوریتم‌های تقریبی دارد. برخی الگوریتم‌های تقریبی این روش گِردسازی را به کار می‌برند: برای هر واسخ واهلیده‌ی $M_v$ پاسخی درست را می‌یابند که کوچک‌تر از $RG.M_v$ است ($RG$ همان نسبت گردسازی (rounding ratio) است).