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

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

function.pngروی تنظیم توان خروجی موبایل کار می کنم به هدف حداکثر سازی مجموع ِ پهنای باند ِ  ارایه شده در شبکه. جزییات را بگذاریم کنار، داستان ختم می شود به یک تابع هدف ِ گت و گنده که اینجا می بیندش. مساله پیدا کردن p_i هاست. این تابع را می شود رامش کرد با دستکاری هایی و می شود حلش کرد. این “می شود” ها البته یعنی کلی توی سر خود زدن (این مقاله را ببینید).

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

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

linear_approximation.png

quadratic_approximation.png

و آن لحظه ی هوا پریدن اینجاست: اینها را بگذار در آن تابع بی ریخت بالایی، می رسی به یک تابع هدف درجه یک یا دو. اینطور که می شود، نفسی می کشیم و لبخند می زنیم، چون برای بهینه سازی توابع درجه یک و دو، زمانی که محدودیت ها خطی باشند، خداوند سالهاست برنامه ریزی خطی و برنامه ریزی درجه دو را آفریده است. جزییات بیشتر در این مقاله آمده: pdf و همینطور html.

ضمانت اجرایی ِ داستان هم از این منحنی می آید.

approxs.png

اما نتیجه گیری:

۱- وقتی مساله خیلی سخت می شود، باید دوباره نگاه کرد.

۲- گاهی راه حل نه در مسیر اصلی، که با کمی خاکی رفتن حاصل می شود.