تیم اسپارک

📝 فهرست مطالب

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

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

صورت برنامه‌ریزی :

$$min ||V||_2,0 s.t. SV=0 L <= V <= U$$

برای حل برنامه ریزی بالا ابتدا مطابق راهنمایی سوال نرم دو-صفر را با نرم دو یک جایگزین کردیم. سپس به تعداد ستون های ماتریس وی، برنامه ریزی بخش قبل را حل کردیم که هر برنامه ریزی یک ستون از وی را به ما داد. چون برنامه ریزی بخش قبل به گونه ای نوشته شده که تعداد سطر های صفر هر بردار زیاد شود، میتوان نتیجه گرفت که تعدادی برنامه ریزی خطی با تقریب سطر های صفر ماتریس وی را افزایش میدهد.

پس در نهایت برای هر ستون ماتریس وی برنامه ریزی زیر را حل کردیم و سپس ستون های به دست‌امده را با هم ادغام کردیم. $$min a_1 + a_2 + ... + a_n s.t. Sv=0 l_i <= v <= u_i a >= v a >= -v$$

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

در این بخش از این کتاب استفاده کردیم که روش های کلی کمینه کردن نرم صفر را بررسی میکرد. ایده های مطرح شده در فصل اول و سوم این کتاب را مطالعه کردیم. تعدادی تابع هدف پیشنهادی در این کتاب مطرح شده بود که هر کدام از آن ها یا توسط سالور های موجود قابل اجرا نبودند و یا جواب مساله را بهتر نمیکردند. همچنین ایده‌ی

concave approximation

که در قصل سوم این کتاب مطرح شده در جلسه‌ی اسکایپ مورد بررسی قرار گرفت اما پیاده سازی آن به نتیجه ای نرسید.
علاوه بر ان یک کد ناقص در کتابخانه‌ی

Optim.jl

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

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

محدودیتی در این بخش وجود ندارد و با نصب پکیج های مورد نظر میتوان یک جواب شدنی برای هر ۳ ورودی مسابقه به دست آورد. اما مدت زمان اجرا در دیتای دور سوم مسابقه قابل توجه است.

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

از آنجایی که در روش اولیه برنامه ریزی ها از یکدیگر مستقل هستند، میتوان آن ها به صورت موازی اجرا کرد تا در داده های بزرگ زمان اجرا به صورت قابل توجهی کاهش یابد.

🏁 روند اجرا

میتوانید نوتبوک را به صورت یکجا یا سلول به سلول ران کنید و خروجی در همان مسیر ذخیره میشود.

پیش‌نیازها

🎈 نحوه استفاده

برای گرفتن خروجی سابمیت شده از تابع

opt_vector1

در بخش آخر نوتبوک استفاده کنید. فراخوانی این تابع در سلول های مورد نظر کامنت شده است.
برای گرفتن خروجی از تابعی که پس از ددلاین این دور پیدا کردیم از تابع

opt_vector3

در بخش آخر نوتبوک استفاده کنید. در حال خاضر اگر نوتبوک را ران کنید خروجی مربوط به همین تابع ذخیره میشود.

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

برنامه در زبان جولیا نوشته شده و لیست پکیج های مورد نیاز در ادامه آمده است :

  MAT
  JuMP
  GLPK
  Ipopt
  SparseArrays
  DelimitedFiles

✍️ نویسندگان

هر دو نفر از اعضای تیم تعدادی از مقاله های موجود در صورت سوال را بررسی کرده و تلاش به پیاده سازی تعداد از آن ایده ها کردند به طور دقیق تر ایده‌ی

concave approximation

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