رياضي در برنامه نويسي

روش خاچيان اهميت نظري داشت ، رياضي در برنامه نويسي  زيرا اولين الگوريتم زمان چند جمله اي بود كه مي تواند براي مشكلات LP به كار رود. با اين حال ، در اكثر موارد عملي بهتر از الگوريتم سيمپلكس عمل نكرد. بسياري از محققاني كه خاچيان را دنبال كردند بر بهبود عملكرد متوسط ​​مورد و همچنين پيچيدگي بدترين حالت محاسباتي تمركز كردند. قابل توجه ترين پيشرفت ها شامل روش نقطه داخلي نارندرا كارماركار و رياضي در برنامه نويسي  بسياري ديگر از الگوريتم هاي سيمپلكس تجديد نظر شده [كارماركار 1984] بود.

4.5.3 مشكل برنامه نويسي خطي صحيح (ILP)

بسياري از برنامه هاي كاربردي برنامه نويسي خطي فقط به متغيرهايي در حوزه انتگرال توجه دارند. به عنوان مثال ، مقادير سيگنال در يك مدار ديجيتال تحت يك سيستم شماره مدولار است. بنابراين ، به احتمال زياد مشكلات بهينه رياضي در برنامه نويسي  سازي تعريف شده در رابطه با سيگنالها در يك مدار را مي توان به عنوان مشكلات ILP مدل كرد. از سوي ديگر ، مشكلاتي كه نياز به برشمردن موارد احتمالي دارند يا مربوط به زمان بندي برخي رويدادها هستند ، اغلب به عنوان ILP توصيف مي شوند.

مشكل ILP به طور كلي بسيار مشكل تر رياضي در برنامه نويسي  از LP است. مي توان نشان داد كه ILP در واقع يكي از مشكلات سخت NP است. اگرچه اثبات رسمي پيچيدگي محاسباتي مسئله ILP از حوصله اين كتاب خارج است ، ما از مثال زير براي نشان دادن روش و توضيح مشكل در حل مسئله ILP استفاده خواهيم كرد.

مشكل ILP در شكل 4.28 به حداكثر رساندن يك تابع هدف f با توجه به چهار محدوديت خطي {g1 ، g2 ، g3 ، g4} است. از آنجا كه مسئله رياضي در برنامه نويسي  فقط شامل دو متغير x و y است ، مي توان آن را در صفحه دو بعدي نشان داد ، جايي كه هر محدوديت يك خط مستقيم است ، چهار محدوديت يك منطقه بسته C را تشكيل مي دهند و راه حل هاي ممكن شبكه يا انتگرال است. نقاط درون اين منطقه iraniancyber  تابع هدف f كه به صورت يك خط راست در سمت راست ناحيه C نشان داده شده است ، با توجه به مقادير مختلف k به طور رياضي در برنامه نويسي  موازي حركت مي كند. به طور شهودي ، براي به دست آوردن حداكثر مقدار f ، مي توانيم خط f = k را از جايي كه در شكل قرار دارد منتقل كنيم تا منطقه C را بر روي يك نقطه شبكه قطع كند.

در شكل 4.30 ، برش هاي c1 و c2 نابرابري هاي معتبري گفته مي شود ، زيرا همه نقاط امكان پذير (يعني نقاط انتگرالي درون خط تيره C) پس از افزودن محدوديت هاي جديد هنوز معتبر هستند. از طرف ديگر ، برش c3 يك نابرابري معتبر نيست رياضي در برنامه نويسي  زيرا يك نقطه امكان پذير p1 بعداً نامعتبر مي شود.

واضح است كه افزودن نابرابري معتبر c2 به جستجوي راه حل بهينه كمك نمي كند زيرا ناحيه جستجو را محدود نمي كند. برعكس ، گفته مي شود كه برش c1 يك نابرابري معتبر قوي است زيرا فرمول را "قوي تر" مي كند. هدف الگوريتم صفحه برش اين است كه چنين نابرابري هاي معتبري را اضافه كند به اين اميد كه راه حل بهينه رياضي در برنامه نويسي  در نهايت به نقطه اي شديد از چند وجهي تبديل شود تا بتوان آن را با الگوريتم چند جمله اي LP زمان پيدا كرد.

روشهاي زيادي براي ايجاد نابرابريهاي معتبر وجود دارد مانند Chvátal-Gomory [Gomory 1960] ، 0-1 Knapsack [Wolsey 1999] ، و lift-and-project [Balas 1993]. با اين حال ، استفاده محض از اين روشهاي توليد نابرابري معتبر در الگوريتم صفحه برش ، در حل مشكلات دشوار ILP زياد پيش نخواهد رفت - ممكن است براي نزديك شدن به يك نقطه شديد انتهايي ، تعداد گامهاي نمايي لازم باشد. يك رويكرد بهتر تركيب الگوريتم صفحه برش با رياضي در برنامه نويسي  فرايند شاخه و محدود است. اين تكنيك تركيبي الگوريتم شاخه و برش ناميده مي شود.