آشنایی با برنامه ریزی مخروطی درجه دوم (قسمت اول)

:: آشنایی با برنامه ریزی مخروطی درجه دوم (قسمت اول)

 

رده خاصی از مسائل غیرخطی، جز دسته مسائل برنامه ریزی مخروطی درجه دوم (second order conic programs) قرار می گیرند که در زمینه های متعدد علوم کنترل، سرمایه گذاری، علوم مهندسی و پزشکی و عیره را می توان به صورت آن بیان کرد. امروزه به جای حل این دسته مسایل با استفاده از الگوریتم های کلی که در حل مسایل غیرخطی کاربرد دارند، الگوریتم های تخصصی نقطه درونی (interior point) معرفی شده که در اکثر نرم افزار های تجاری توسعه داده شده اند.

 

 

بنابراین خواص مدل های دسته SOCP را در چهار مورد می توان معرفی کرد:

قابل تبدیل به فرم استاندارد برنامه ریزی درجه دوم

عدم نیمه معین مثبت بودن

دارای فضای محدب

کارایی در حل با استفاده از الگوریتم های نقطه داخلی 

 

منبع : بهنماآشنایی با برنامه ریزی مخروطی درجه دوم (قسمت اول)
برچسب ها : الگوریتم ,درجه ,ریزی ,برنامه ,دسته ,برنامه ریزی ,مخروطی درجه ,ریزی مخروطی

حل مدل نونوگرام توسط الگوریتم CP نرم افزار CPLEX

:: حل مدل نونوگرام توسط الگوریتم CP نرم افزار CPLEX

 

در این پست قصد داریم حل مدل نونوگرام (سخت ترین مساله بهینه‌سازی ترکیباتی) را با استفاده از الگوریتم CP در نرم افزار IBM Ilog CPLEX ارائه دهیم.

 

همونطور که در شکل زیر نیز ملاحظه می کنید این مساله اغلب برای رمزنگاری استفاده میشه. جالبه که این شکل رو GANT CHART خود نرم افزار تولید می کند.

 

 

 

  

 

منبع : بهنماحل مدل نونوگرام توسط الگوریتم CP نرم افزار CPLEX
برچسب ها : افزار

بکارگیری ساختار داده tuple در مدل سازی (بخش اول)

:: بکارگیری ساختار داده tuple در مدل سازی (بخش اول)

  

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

  

مفهوم matrix sparsity به این نکته اشاره دارد که قبل از حل مدل، بررسی کنیم که این ماتریس از چه الگویی تبعیت میکند.

 

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

 

استفاده از ساختار داده ها یکی از راهکارهای مطمئن جهت شناساندن این الگو به رویه حل محسوب می شود. tuple ها یک دسته خیلی مهم از این ساختار داده ها بحساب می آیند.

 

معنای تحت الفظی tuple : "مجموعه مرتب".
کاربرد دیگر tuple ها در الگوریتم های مبنی بر گراف هستند. این کاربرد در پست بعدی بحث خواهد شد.

 

منبع : بهنمابکارگیری ساختار داده tuple در مدل سازی (بخش اول)
برچسب ها : داده ,tuple ,ماتریس ,ساختار ,رویه ,خیلی ,ساختار داده ,matrix sparsity

بکارگیری ساختار داده tuple در مدل سازی (بخش دوم)

:: بکارگیری ساختار داده tuple در مدل سازی (بخش دوم)

 

اغلب مسایل بهینه سازی ترکیباتی که با آنها سروکار داریم در عمل به تصمیم گیری درباره نحوه شکل گیری عملیات، مسیریابی، سیکل ها و ... منتج می شوند. به عنوان مثال یک مساله فروشنده دوره گرد با 6 شهر و مسیر مشخص زیر را در نظر بگیرید:

 

$$1 \rightarrow 6 \rightarrow 2 \rightarrow 5 \rightarrow 3 \rightarrow 4$$  

 

 در ادبیات عرف این است که این مسیر را توسط بک ماتریس orthogonal صفر و یک (ماتریسی که ابر صفحه تمامی بردارهای آن مستقلا بر هم عمود باشند) نشان می دهیم:

  

routes = [
[0 0 0 0 0 1]
[0 0 0 0 1 0]
[0 0 0 1 0 0]
[1 0 0 0 0 0]
[0 0 1 0 0 0]
[0 1 0 0 0 0]
]; 

  

 متناظرا در ادبیات گراف همین مفهوم مسیر را با تعریف یال و گره می توان نشان داد:

 

 

 

که در این صورت این مسیر با بکارگیری مفهوم tuple به صورت زیر قابل بیان است: 

 

tuple ROUTE {
int i;
int j;
}
{ROUTE} routes = {<1,6>,<6,2>,<2,5>,<5,3>,<3,4>};

 

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

  

منبع : بهنمابکارگیری ساختار داده tuple در مدل سازی (بخش دوم)
برچسب ها : ightarrow ,tuple ,مسیر ,الگوریتم ,گراف ,نشان ,مفهوم tuple

الگوریتم سیمپلکس جز 10 الگوریتم برتر قرن بیستم شناخته شد

:: الگوریتم سیمپلکس جز 10 الگوریتم برتر قرن بیستم شناخته شد

 

اخیرا خبری در پایگاه علمی SIAM News شمارگان 33 منتشر شد که در آن 10 الگوریتم برتر قرن بیستم از نگاه دانشمندان علوم کامپوتر و ریاضیات معرفی گردید. الگوریتم سیمپلکس یکی از الگوریتم هایی بود که در این لیست به چشم می خورد.
جرج دانتزیگ (George Dantzig) از موسسه RAND الگوریتم سیمپلکس را برای حل مسایل برنامه ریزی خطی طراحی کرده و توسعه داد.

 

 

 

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

  

منبع : بهنماالگوریتم سیمپلکس جز 10 الگوریتم برتر قرن بیستم شناخته شد
برچسب ها : الگوریتم ,برنامه ریزی ,مسایل برنامه ,الگوریتم برتر

آشنایی با برنامه ریزی مخروطی درجه دوم (قسمت دوم)

:: آشنایی با برنامه ریزی مخروطی درجه دوم (قسمت دوم)

 

در این پست قصد داریم مساله جایابی تک تسهیلاتی از نوع فاصله اقلیدسی را با نرم افزار Ilog CPLEX حل نماییم.

جهت استقرار تسهیل جدید در میان تسهیلات قدیمی بایستی رابطه زیر را مینیمم کرد:

  

$$\textbf{Min} \quad \sum_j \sqrt {(x-a_j)^2+(y-b_j)^2}$$

   

که در این رابطه $(x,y)$ مختصات تسهیل جدید و $(a_j,b_j)$ مختصات تسهیلات قدیمی می باشند.

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

  

$$\textbf{Min} \quad \sum_j z_i$$

$$(x-a_j)^2 + (y-b_j)^2 \leq  z_j , \quad \forall j \in C$$

    

به عنوان مثال مختصات زیر را برای چهار تسهیل قدیمی در نظر بگیرید:

  

$$a=(0,0,5,12)$$
$$b=(0,10,0,6)$$

 

که خروجی نرم افزار به فرم زیر خواهد بود:

    

Parallel mode: using up to 4 threads for barrier.
solution (optimal) with objective 168.749973187147
Summary statistics for Cholesky factor:
  Threads                   = 4
  Rows in Factor            = 14
  Integer space required    = 14
  Total non-zeros in factor = 105
  Total FP ops to factor    = 1015
 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf Inf Ratio
   0  4.8284271e+000 -1.0000000e+000 3.13e+001 0.00e+000 5.83e+000 1.00e+000
   1  3.6794597e+001  3.9733735e+001 3.13e+001 0.00e+000 5.83e+000 1.42e-001
   2  7.4568401e+001  8.0527827e+001 1.89e+001 0.00e+000 3.51e+000 1.10e-001
   3  1.4779422e+002  1.5081331e+002 1.45e+001 0.00e+000 2.69e+000 2.55e-001
   4  1.6789467e+002  1.6802209e+002 4.13e+000 0.00e+000 7.69e-001 6.28e+000
   5  1.6869662e+002  1.6870380e+002 1.46e-001 0.00e+000 2.72e-002 1.11e+002
   6  1.6874720e+002  1.6874756e+002 8.28e-003 0.00e+000 1.54e-003 2.26e+003
   7  1.6874987e+002  1.6874988e+002 4.06e-004 0.00e+000 7.55e-005 4.77e+004
   8  1.6874997e+002  1.6874998e+002 1.92e-005 0.00e+000 3.57e-006 2.38e+005

   

در خروجی نرم افزار می توان مشاهده نمود که نرم افزار به طور خودکار تابع مسدودسازی (barrier) را تشکیل داده و از الگوریتم اختصاصی نقطه درونی جهت دستیابی به نقطه بهینه استفاده نموده است.

 

منبع : بهنماآشنایی با برنامه ریزی مخروطی درجه دوم (قسمت دوم)
برچسب ها : افزار ,factor ,مختصات ,توان ,رابطه ,تسهیل ,quad sum , extbf{min} quad ,تسهیلات قدیمی ,تسهیل جدید