تحلیلی بر الگوریتمهای برنامهریزی عدد صحیح در بهینهسازی ترکیبیاتی
کلمات کلیدی:
الگوریتمهای بهینهسازی, حدود و قیود, برش انشعاب, عدد صحیحچکیده
بهینهسازی ترکیبیاتی یکی از زمینههای کلیدی در علوم کمپیوتری و ریاضیات کاربردی است که با حل مسائل پیچیده نظیر انتخاب بهینه از مجموعهای گزینهها یا ترکیبها سروکار دارد. بسیاری از این مسائل میتوانند به صورت برنامهریزی عدد صحیح مدلسازی شوند. الگوریتمهای برنامهریزی عدد صحیح به خصوص در بهینهسازی ترکیبیاتی اهمیت زیادی دارند؛ زیرا توانایی حل مسائل با ابعاد بزرگ و پیچیده را دارند. در این مقاله، الگوریتمهای مختلف برنامهریزی عدد صحیح، از جمله الگوریتمهای حدود و قیود، الگوریتمهای صفحات برشی و الگوریتمهای ابتکاری، برای حل مسائل ترکیبیاتی مورد بررسی قرار میگیرند. هدف این مقاله ارائه مروری جامع بر این الگوریتمها برنامهریزی عدد صحیح در بهینهسازی ترکیبیاتی و نتایج حاصلۀ استفاده از هر یک در مسائل مختلف بهینهسازی ترکیبیاتی میباشد. روش تحقیق این مطالعه براساس هدف توسعهای، براساس روش کمی و براساس ماهیت دادهها توصیفی- تحلیلی بوده و جمعآوری دادهها به روش کتابخانهای انجام یافته است. یافتههای این تحقیق نشان میدهد که الگوریتمهای حدود و قیود در مسائل با ابعاد کوچک و متوسط عملکرد بهتری دارند؛ در حالی که برای مسائل بزرگ و پیچیده، الگوریتمهای ابتکاری به دلیل کاهش زمان محاسباتی و کارایی بالاتر ترجیح داده میشوند. در نتیجه میتوان گفت بهینهسازی ترکیبیاتی در علوم کمپیوتری و ریاضیات نقش مؤثری دارد.
مراجع
جهان شاهلو، غلام رضا. (۱۳۸۱). تحقیق در عملیات دو. تهران: پیام نور.
حمدی، طه. (۱۳۹۶). آشنایی با تحقیق در عملیات. ج۱. ترجمه محمد باقر بارزگان، تهران: نشر دانشگاهی.
حمدی، طه. (۱۳۹۹). آشنایی با تحقیق در عملیات. ج۲، ترجمه ابراهیم رضایی نیک، تهران: نما.
حمدی، طه. (۱۴۰۱). کتاب حل تشریحی مسائل تحقیق در عملیات. تهران: نما.
عشقی، کوروش. (۱۳۹۸). برنامهریزی عدد صحیح، مدلسازی و روشهای حل. تهران: مرکز دانشگاهی صنعتی شریف.
عشقی، کوروش .(۱۴۰۱). برنامهریزی عدد صحیح، مدلسازی و روشهای حل. تهران: مرکز دانشگاهی صنعتی شریف.
ملکپور، پرویز .(۱۳۹۳). مبانی پژوهشهای عملیاتی. تهران: بی نا.
Basu, A., Conforti, M., Di Summa, M., & Jiang, H. (2020). Complexity of cutting planes and branch-and-bound in mixed-integer optimization. Optimization Online. Retrieved from https://optimization-online.org/wp-content/uploads/2020/03/7672.pdf
Ma, H., & Chen, J. (2007). An improved mathematical model and a hybrid metaheuristic for cross-docking scheduling problem. Computers & Industrial Engineering, 53(2), 263–278. https://doi.org/10.1016/j.cie.2007.06.029
Mitchell, J. E. (1999). Branch-and-Cut algorithms for combinatorial optimization problems. In P. M. Pardalos & M. G. C. Resende (Eds.), Handbook of Applied Optimization (pp. 65–77). New York: Oxford University Press.
Nogueira, T. H., Santos, G. P. A., & de Carvalho, C. R. V. (2014). A hybrid Lagrangean metaheuristic for single machine scheduling problems with sequence-dependent setup times and due dates. Optimization Online. Retrieved from https://optimization-online.org/wp-content/uploads/2014/08/4486.pdf
Xu, J., Wu, H., Cheng, Y., Wang, L., Yang, X., Fu, X., & Su, Y. (2024). Optimization of Worker Scheduling at Logistics Depots Using Genetic Algorithms and Simulated Annealing. arXiv preprint arXiv:2405.11729. https://arxiv.org/abs/2405.11729
