آزادسازی در برنامه‌ریزی خطی کیست؟ توضیح بده.
در ریاضی و دانش رایانه، واهِلِش به برنامه‌نویسی خطی برنامه‌ای دُرُست (integer program) را به برنامه‌ای خطی می‌ترادیساند. در این ترادیسی، هر متغیر formula_1 در برنامهٔ درست با متغیری خطی formula_2 جایگزین می‌شود. این واهلش پرسمانی ان‌پی سخت را به پرسمانی خطی که در زمانی چند جمله‌ای حل می‌شود می‌ترادیساند. پاسخ به برنامهٔ خطی به دست آمده، اطلاع‌های سودمندی را دربارهٔ برنامهٔ درست اصلی فراهم می‌آورد.نمونه.برای نمونه، به پرسمان پوشش مجموعه می‌پردازیم. مجموعه‌ای مانند formula_3 و زیرمجموعه‌های formula_4 از این مجموعه داده شده‌اند. این پرسمان شماری از formula_5ها را می‌جوید که یکایش (اجتماع) این زیرمجموعه‌ها مجموعه formula_3خواهد بود.در برنامهٔ درست برای پوشش مجموعه، برای هر زیرمجموعهٔ formula_5 متغیری بولی formula_8 داریم.یکایش زیرمجموعه‌های گزینش شده باید برابر با formula_3 باشد. به سخنی دیگر، هر formula_10 باید در این یکایش باشد: formula_11. این پاوند را پاوند یکایش می‌نامیم.هم‌چنین، پاوندِ formula_1 برای هر متغیر formula_8 نشان می‌دهد که آیا زیرمجموعه formula_5 در پاسخ خواهد بود یا نه. به سخنی دیگرِ، ارزش یک/صفر برای formula_15 نشان می‌دهد که زیرمجموعهٔ formula_5 در پوشش هست/نیست. این پاوند را پاوند بولی می‌نامیم.پرسمان کم‌ترین شمار زیرمجموعه‌ها را می‌جوید: formula_17.واهلش به برنامهٔ خطی هر پاوند بولی formula_1 را با پاوند formula_19 جایگزین می‌کند. برنامهٔ خطی به دست آمده وزنی را برای هر زیرمجموعه فرضیده است؛ ولی، پاوند یکایش یکسان می‌ماند. در پاسخ به این برنامهٔ خطی، جمع وزن همهٔ زیرمجموعه‌هایی چون formula_5 که دربردارندهٔ عضو formula_10 برابر با یک خواهند بود.به این نمونه از پوشش مجموعه‌ای بنگرید: مجموعهٔ formula_22 و زیرمجموعه‌های formula_23 را داریم. در برنامهٔ درست، سه متغیر formula_24 خواهیم داشت. برای هر کدام از formula_25 یک پاوند یکایش هست. برای نمونه، برای formula_26 پاوندِ formula_27 را داریم. هم‌چنین، برای هر formula_5 یک پاوند بولی formula_19 داریم.گزینش هر جفت از زیرمجموعه‌های formula_30 پاسخی بهین است. به سخنی دیگر، هر یک از formula_31، formula_32 یا formula_33 یک پوشش مجموعه‌ای کمینه است؛ بنابراین پاسخ کمینه برای برنامهٔ درست برابر است با formula_34.ولی، پاسخی بهین به برنامهٔ خطی formula_35 است. در این پاسخ، هر formula_8 دارای ارزش formula_37 است. این پاسخ پاوندهای یکایش را برآورده می‌کند.هم‌سنجی پاسخ واهلش و برنامه‌ی درست.اگر در پاسخ بهین به برنامه‌ی خطی، هر متغیر ارزشی صفر یا یک بگیرد، این پاسخ پاسخی بهین برای برنامه‌ی درست نیز خواهد بود. با این همه،‌ ما پرسمان‌های اندکی با چینن پاسخ‌هایی داریم.چون هر برنامه‌ی درست زیرمجموعه‌ای از برنامه‌ای خطی است،‌ پاسخ‌ها به برنامه‌ی درست نیز زیرمجموعه‌ای از پاسخ‌ها به برنامه‌ی خطی‌اند. اگر برنامه‌ی درست بیشینه‌سازی باشد،‌ پاسخ بهین به برنامه‌ی خطی همواره بزرگ‌تر از پاسخ بهین به برنامه‌ی اصلی است. به همین سان،‌ اگر برنامه‌ی درست کمینه‌سازی باشد،‌ پاسخ به برنامه ی خطی همواره کوچک‌تر از برنامه‌ی اصلی است. به سخنی دیگر،‌ پاسخ به برنامه‌ی خطی واهلیده همواره کرانی بالا (پایین) برای برنامه‌ای درست بیشینه‌سازی (کمینه‌سازی) است.در نمونه‌ی بالا برای پوشش مجموعه‌ی،‌ پاسخ بهین خطی برابر بود با formula_35. چون پرسمان پوشش مجموعه،‌ پرسمانی کمینه‌سازی است،‌ پاسخ بهین برای برنامه‌ی درست همواره بزرگ‌تر یا برابر با formula_35 خواهد بود. افزون بر این،‌ چون هر متغیر در برنامه‌ی درست می‌تواند ارزش صفر یا یک داشته باشد،‌ دست کم باید دو متغیر با ارزش یک در پاسخ بهین باشند. بنابراین، می‌توان کران پایین برای برنامه‌ی درست را به کرانی تنگ‌تر بهبود داد. این کران برابر با ۲ است.تقریب‌زنی و گاف درستالی.واهلش به برنامه‌‌ی خطی،‌ شیوه‌ای استاندارد برای طراحی الگوریتم‌های تقریبی است. گاف درستالی (integral gap) مفهومی کلیدی در این زمینه است. در واهلش، گاف درستالی نسبت بیشینه میان برنامه‌ی درست و برنامه‌ی خطی را نشان می‌دهد. اگر formula_40 پاسخ بهین برای برنامه‌ی درست و اگر formula_41 پاسخ بهین برای برنامه‌ی خطی باشند،‌ گاف درستالی در کمینه‌سازی به دیسه‌ی formula_42 تعریف می‌شود و در بیشینه‌سازی برابر است با formula_43. بنابراین، گاف درستالی همواره بزرگ‌تر از یک است. در نمونه‌ی بالا چون پرسمان کمینه‌سازی،‌گاف درستالی برابر است با formula_44.گاف درستالی کاربرد فراوانی برای یافتن نسبت تقریب در الگوریتم‌های تقریبی دارد. برخی الگوریتم‌های تقریبی این روش گِردسازی را به کار می‌برند: برای هر واسخ واهلیده‌ی formula_41 پاسخی درست را می‌یابند که کوچک‌تر از formula_46 است (formula_47 همان نسبت گردسازی (rounding ratio) است).