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

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

پیوند=https://en.wikipedia.org/wiki/File:IP_polytope_with_LP_relaxation.png|بندانگشتی|300x300پیکسل|برنامه‌ای درست و واهلش خطی این برنامه.

## نمونه
برای نمونه، به پرسمان پوشش مجموعه می‌پردازیم. مجموعه‌ای مانند 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 \geq 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 \leq x_i \leq 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 \geq 1 را داریم. هم‌چنین، برای هر S_i یک پاوند بولی 0 \leq x_i \leq 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) است).

## پانویس

رده:برنامه‌ریزی خطی
رده:بهینه‌سازی ترکیبیاتی