• بهینه سازی عدد صحیح

مسائل بهینه سازی خطی که نیاز به اعداد صحیح برخی از متغیرها دارند، برنامه های عدد صحیح مختلط (MIP) نامیده می شوند.

این متغیرها می توانند به چند صورت ایجاد شوند:

  • متغیرهای عدد صحیحی که تعداد اقلام را نشان می‌دهند، مانند ماشین‌ها یا دستگاه‌های تلویزیون، و مشکل این است که تصمیم می‌گیریم چه تعداد از هر اقلام را تولید کنیم تا سود را به حداکثر برسانیم.
    به طور معمول، چنین مسائلی را می توان به عنوان مسائل بهینه سازی خطی استاندارد تنظیم کرد، با این شرط که متغیرها باید اعداد صحیح باشند. بخش بعدی نمونه ای از این نوع مشکلات را نشان می دهد.

  • متغیرهای بولی که تصمیماتی را با مقادیر 0-1 نشان می دهند.
    به عنوان مثال، مشکلی را در نظر بگیرید که شامل انتساب کارگران به وظایف است (به تکلیف مراجعه کنید). برای راه‌اندازی این نوع مشکل، می‌توانید متغیرهای بولی x i,j را تعریف کنید که اگر کارگر i به وظیفه j اختصاص داده شود، برابر با 1 و در غیر این صورت 0 است.

برای یک آغازگر خوب در بهینه سازی اعداد صحیح، کتاب آشپزی مدلسازی Mosek را توصیه می کنیم.

ابزار

گوگل چند راه برای حل مشکلات MIP ارائه می دهد:

  • MPSolver : پوششی برای چندین حل کننده MIP شخص ثالث که از تکنیک های استاندارد شاخه و کران استفاده می کنند.
  • حل کننده CP-SAT : یک حل کننده برنامه نویسی محدودیت که از روش های SAT (رضایت پذیری) استفاده می کند.
  • حل کننده اصلی CP : یک حل کننده برنامه نویسی محدودیت .

از کدام حل کننده استفاده کنم؟

هیچ قانون اساسی برای تصمیم گیری در مورد استفاده از حل کننده MIP یا حل کننده CP-SAT وجود ندارد. به عنوان یک راهنمای تقریبی:

  • حل‌کننده‌های MIP برای مسائلی مناسب‌تر هستند که می‌توانند به عنوان یک LP استاندارد تنظیم شوند، اما با متغیرهای عدد صحیح دلخواه، مانند مثال اول بالا.
  • حل کننده CP-SAT برای مسائلی که اکثر متغیرها در آنها Boolean هستند، مناسب تر است، مانند مثال دوم بالا.

برای MIP های معمولی که دارای هر دو متغیر اعداد صحیح و بولی هستند، اغلب تفاوت واضحی در سرعت بین دو حل کننده وجود ندارد، بنابراین انتخاب شما ممکن است به ترجیح شخصی بستگی داشته باشد.

برای مثال‌هایی که از حل‌کننده‌های MIP و CP-SAT استفاده می‌کنند، به حل مسئله تکلیف و سایر بخش‌های تخصیص مراجعه کنید.

راه دیگر برای حل مسائل برنامه نویسی عدد صحیح استفاده از حل کننده جریان شبکه است.
به عنوان مثال به تخصیص به عنوان یک مسئله جریان هزینه حداقل مراجعه کنید.
برای مشکلی که می تواند به عنوان یک جریان شبکه راه اندازی شود، حل کننده جریان حداقل هزینه می تواند سریعتر از حل کننده های MIP یا CP-SAT باشد. با این حال، همه MIP ها را نمی توان به این روش تنظیم کرد.