عقاب‌های خسته‌بال

---

در این بخش هدف پیدا کردن ماتریس V ای بود که در قیدهای داده‌شده صدق کند که این قیدها نسبت به V خطی بودند. همچنین می‌خواستیم V را به‌گونه‌ای پیدا کنیم که تا جای ممکن بیشترین تعداد سطر تمام صفر را داشته باشد. برای حل این مساله، ابتدا بردار v^norm را به گونه‌ای تعریف کردیم که درایه iام آن برابر با بزرگترین قدر مطلق مقادیر سطر iام V باشد. به این ترتیب iامین سطر V تمام ۰ است اگر و تنها اگر iامین درایه این بردار برابر ۰ باشد و بنابراین تابع هدف به نرم l0 این بردار تغییر پیدا می‌کند. به این شکل، این مساله بسیار شبیه به مساله دور قبل می‌شود و برای حل آن از ایده‌های آن دور استفاده می‌کنیم.

📝 فهرست مطالب

• صورت‌بندی سوال
• الگوریتم بهینه‌سازی
• محدودیت‌ها
• ایده‌های گسترش
• روند اجرا

• وابستگی‌ها
• نویسندگان

🧐 صورت‌بندی سوال

💡 الگوریتم بهینه‌سازی

همانطور که در بالاتر نیز گفته شد، با کمک بردار v^norm مساله زیر را شبیه به مساله دور دوم ساختیم که معادل با مساله اصلی است

مانند دور دوم، ابتدا نرم l0 را با نرم l1 تخمین زدیم. از آنجا که درایه‌های v^norm نامنفی هستند، نرم l1 آن برابر با جمع درایه‌های آن می‌شود و به این ترتیب مساله زیر به شکل تقریبی از مساله اصلی به‌دست می‌آید.

مانند دور دوم، بعد از حل این مساله با استفاده از solver های Julia، به صورت گام به گام نتیجه را بهبود بخشیدیم. به این منظور، در هر گام با استفاده از نتایج گام قبل (و در گام اول با استفاده از نتایج تخمین l1 مساله)، وزن wi را به شکل زیر تولید کردیم:

با استفاده از این وزن‌ها، مساله زیر را تعریف کرده و با حل آن به نتایج بهتری دست پیدا کردیم:

ایده‌ی پشت این روش نیز کاملا مشابه این روش در دور دوم است. تنها تفاوت این روش با روش دور دوم در این است که به دلیل این که مقادیر بردار v^norm نامنفی هستند، تابع sgn حذف شده چون همیشه مقدار ۱ را به ما می‌دهد و به دلیل مشابه قید نامنفی بودن v^norm نیز حذف شده است. برای تعریف مساله MILP نیاز به بردار M داریم که درایه iام آن ماکسیمم قدر مطلق مقداری است که یک درایه در سطر iام V ممکن است بگیرد. به عبارت دیگر M به شکل زیر تعریف می‌شود:

در نهایت، مساله MILP زیر حل شده و جواب مساله را به ما می‌دهد:

⛓️ محدودیت‌ها

با توجه به سخت بودن حل مسائل MILP و بزرگ بودن اندازه ورودی سوم، حل کردن مساله MILP حداقل با سخت‌افزارهای معمولی (مثل لپ‌تاپ‌های شخصی) بسیار طول خواهد کشید. برای این ورودی، خروجی بعد از تقویت به صورت گام به گام قرار داده شده است.

🚀 ایده‌های گسترش

با توجه به این که روش فوق بهترین پاسخ ممکن را برای دو ورودی اول پیدا می‌کند، ایده‌ای برای گسترش بیشتر برای این دو داده وجود ندارد. اما با توجه به روش‌هایی که برای دورهای بعد به ذهنمان رسید، ایده‌ای برای حل این دور هم وجود دارد که می‌تواند سرعت به پاسخ رسیدن را بسیار بهبود بخشد. ایده از این قرار است که به V به صورت ستون به ستون نگاه کرده و برای هر ستون آن با استفاده از روش دور دوم یک بردار پیدا کنیم که در قیدها صدق کند و بیشترین تعداد ۰ ممکن را داشته باشد. به این صورت یک ماتریس V اولیه تشکیل دهیم. سپس سطرهایی از V که ۰ شده‌اند و همچنین سطرهایی که امکان ندارد ۰ شوند (یعنی درایه‌ای از آن‌ها وجود دارد که بازه‌ی شدنی مقادیر آن شامل ۰ نیست) را از V حذف کرده و سپس سعی کنیم این مساله را در ماتریس بسیار کوچک‌تر شده حل کنیم که به مراتب سریع‌تر حل می‌شود. با این که این روش را در این دور پیاده نکرده‌ایم، اما دور بعد را با استفاده از این روش انجام داده‌ایم. برای توضیحات بیشتر و کد، می‌توانید به دور بعد مراجعه کنید.

🏁 روند اجرا

کافیست آن را در کنار فایل ورودی قرار داده، نام فایل ورودی را در کد در خط دوم سلول دوم به نام فایل ورودی مورد نظر تغییر داده؛ مقادیر size_of_v_r, size_of_v_c را نیز که سایز ماتریس V خروجی است، در خطوط سوم و چهارم از سلول سوم، با توجه به ابعاد داده‌ی ورودی به‌روزرسانی کنید. در نهایت سلول‌ها را به ترتیب اجرا کنید. پس از اتمام اجرا، خروجی مورد نظر در فایل output.txt در کنار کد ذخیره خواهد شد. بالای هر سلول نیز توضیحی داده شده که در آن سلول چه اتفاقی دارد می‌افتد.

پیش‌نیازها

از آنجا که در کد از زبان جولیا استفاده شده‌است، نیاز است این زبان نصب شود. همچنین بسته‌هایی که در سلول اول کد استفاده شده‌اند نیز باید نصب شود. برای نصب جولیا و بسته‌های مورد نظر می‌توانید به وب‌سایت جولیا مراجعه کنید.

نصب

⛏️ وابستگی‌ها

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

• JuMP
• Cbc
• ECOS
• GLPK
• MAT
• SparseArrays
• DelimitedFiles
• LinearAlgebra
• MathOptInterface

✍️ نویسندگان

احمد رحیمی و دیبا هاشمی