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

STUDENT

DEGREE

YEAR

Nowadays models consists of more details in comparison to past because of improving in science and technology so dimensions of modern problems are increasing fast. On the other hand dimensions of problems that we can solve are limited due to available computing power. Mathematicians and on the other hand computer engineers suggest some approach to solve large scale problems but still there are many problems that are unsolvable. One more effective approach to solve large scale problems is parallel processing. That is using several processors concurrently for solving one problem due to dividing the problem to some independent sections. As mathematical models grow larger and more complex, infeasibility happens more often during the process of model formulation. Because of costs of formulation of large scale problems, ignoring infeasible models is not frugal . So mathematicians develop some methods for analysis of infeasible models during two past decades. According to this fact that infeasibility occurs in text of large scale optimization and most approach for solving it is formulated as NP-hard problem, using parallel processing in this context is useful. This thesis is dedicated to study of methods for infeasibility analysis, detection parallel source in their algorithms and designing parallel algorithms. In this way we use distributed memory architecture and message passing model. Implementation of algorithms is done with MPI protocol. Finally numerical results are shown and compered Nowadays models consists of more details in comparison to past because of improving in science and technology so dimensions of modern problems are increasing fast. On the other hand dimensions of problems that we can solve are limited due to available computing power. Mathematicians and on the other hand computer engineers suggest some approach to solve large scale problems but still there are many problems that are unsolvable. One more effective approach to solve large scale problems is parallel processing. That is using several processors concurrently for solving one problem due to dividing the problem to some independent sections. As mathematical models grow larger and more complex, infeasibility happens more often during the process of model formulation. Because of costs of formulation of large scale problems, ignoring infeasible models is not frugal . So mathematicians develop some methods for analysis of infeasible models during two past decades. According to this fact that infeasibility occurs in text of large scale optimization and most approach for solving it is formulated as NP-hard problem, using parallel processing in this context is useful. This thesis is dedicated to study of methods for infeasibility analysis, detection parallel source in their algorithms and designing parallel algorithms. In this way we use distributed memory architecture and message passing model. Implementation of algorithms is done with MPI protocol. Finally numerical results are shown and compered

با پیشرفت علوم و مهندسی، مدل های امروزی جزئیات بیشتری را ارائه می کنند و ابعاد مسایل مدرن به سرعت رو به افزایش است. از طرفی ابعاد مسایلی که ما قادر به حل آنها هستیم از طریق توان محاسباتی موجود محدود می شود. ریاضیدانان و از دیگر سو مهندسان کامپیوتر، رویه هایی را برای حل مسایل بزرگ پیشنهاد کرده اند، اما علیرغم این تلاشها هنوز مسایل بسیاری موجودند که حل آنها از توان روشهای ارایه شده، خارج است. یکی از جدید ترین رویکردهای حل مسایل بزرگ، استفاده از محاسبات موازی است. محاسبات موازی عبارت است از به کارگیری همزمان چندین پردازنده برای حل یک مساله به منظور گرفتن نتایج سریعتر. با بزرگ شدن ابعاد مسایل امروزی، احتمال بروز خطا در مرحله مدلسازی و امکان ناپذیر شدن مدل، افزایش می یابد. از آنجا که مدلسازی مسایل بزرگ هزینه بر می باشد، صرفنظر کردن از مدل های امکان ناپذیر و ساختن مدلهای جدید به صرفه نیست. لذا ریاضیدانان در طی دو دهه اخیر روشهایی را برای تحلیل و بازیافت این مدلها ارایه کرده اند. با توجه به اینکه امکان ناپذیری در بطن مسایل بزرگ مقیاس رخ می دهد و مهم ترین رویکرد حل آن بوسیله یک مساله NP-hard قابل صورتبندی است، استفاده از محاسبات موازی در حل این مساله، مناسب به نظر می رسد. در تحقیق حاضر روشهای تحلیل مساله امکان ناپذیری شناسایی شده و از نقطه نظر محاسبات موازی مورد بررسی قرار گرفته اند. سپس برای آن دسته از روشها که امکان موازی کاری در الگوریتم هایشان وجود دارد، نسخه های موازی بر اساس معماری حافظه توزیع شده و مدل انتقال پیام طراحی گردیده است. در ساختن برنامه های مربوطه، پروتکل MPI استفاده شده است. در نهایت نتایج حاصل از حل عددی الگوریتم های طراحی شده به منظور نشان دادن کارایی آنها آورده شده است و الگوریتم ها مورد مقایسه قرار گرفته اند. با پیشرفت علوم و مهندسی، مدل های امروزی جزئیات بیشتری را ارائه می کنند و ابعاد مسایل مدرن به سرعت رو به افزایش است. از طرفی ابعاد مسایلی که ما قادر به حل آنها هستیم از طریق توان محاسباتی موجود محدود می شود. ریاضیدانان و از دیگر سو مهندسان کامپیوتر، رویه هایی را برای حل مسایل بزرگ پیشنهاد کرده اند، اما علیرغم این تلاشها هنوز مسایل بسیاری موجودند که حل آنها از توان روشهای ارایه شده، خارج است. یکی از جدید ترین رویکردهای حل مسایل بزرگ، استفاده از محاسبات موازی است. محاسبات موازی عبارت است از به کارگیری همزمان چندین پردازنده برای حل یک مساله به منظور گرفتن نتایج سریعتر. با بزرگ شدن ابعاد مسایل امروزی، احتمال بروز خطا در مرحله مدلسازی و امکان ناپذیر شدن مدل، افزایش می یابد. از آنجا که مدلسازی مسایل بزرگ هزینه بر می باشد، صرفنظر کردن از مدل های امکان ناپذیر و ساختن مدلهای جدید به صرفه نیست. لذا ریاضیدانان در طی دو دهه اخیر روشهایی را برای تحلیل و بازیافت این مدلها ارایه کرده اند. با توجه به اینکه امکان ناپذیری در بطن مسایل بزرگ مقیاس رخ می دهد و مهم ترین رویکرد حل آن بوسیله یک مساله NP-hard قابل صورتبندی است، استفاده از محاسبات موازی در حل این مساله، مناسب به نظر می رسد. در تحقیق حاضر روشهای تحلیل مساله امکان ناپذیری شناسایی شده و از نقطه نظر محاسبات موازی مورد بررسی قرار گرفته اند. سپس برای آن دسته از روشها که امکان موازی کاری در الگوریتم هایشان وجود دارد، نسخه های موازی بر اساس معماری حافظه توزیع شده و مدل انتقال پیام طراحی گردیده است. در ساختن برنامه های مربوطه، پروتکل MPI استفاده شده است. در نهایت نتایج حاصل از حل عددی الگوریتم های طراحی شده به منظور نشان دادن کارایی آنها آورده شده است و الگوریتم ها مورد مقایسه قرار گرفته اند.