Combinatorial optimization as a major domain of CS
Combinatorial optimization is a field within computer science that focuses on finding the optimal solution among a finite set of possibilities. It involves solving complex problems by determining the best combination of variables to achieve an objective. Some examples of combinatorial optimization problems include:
Tiling problems: The tiling problem is a type of combinatorial problem that asks how to cover a given region with a given set of tiles, without any gaps or overlaps. The region and the tiles can have different shapes and sizes, and the tiles can be placed in different orientations. The tiling problem can have various applications, such as art, cryptography, geometry, and computer science. The tiling problem can also have different variations, such as counting the number of possible tilings, finding a specific tiling, or determining whether a tiling exists or not.
Time tabling: In this problem, the goal is to create an optimal schedule for activities, taking into consideration constraints such as available resources, time slots, and preferences. This is commonly used in school timetables, conference schedules, or employee shift planning.
Cutting and packing problems: These problems involve finding the most efficient way to cut or pack objects into specific shapes or containers. This is commonly used in logistics and manufacturing industries to optimize the use of space, minimize shipping costs, or maximize loading capacity.
Facility location problems: In this problem, the objective is to determine the optimal location for new facilities based on factors such as distance to customers, transportation costs, and capacity requirements. It has applications in urban planning, supply chain management, and network design.
Graph matching: Graph matching problems involve finding the optimal correspondence or alignment between two or more graphs. This is often applied in image recognition, pattern recognition, or DNA sequence alignment.
These examples highlight the broad range of applications and complexity involved in combinatorial optimization, making it an important area of study within computer science.
The Optimization Lab at Math Faculty and many publications of the members are related to this topic.
References
2023
Feature Selection for Anti-Cancer Plant Recommendation
@inproceedings{Amintoosi2023FS-bio-math,title={Feature Selection for Anti-Cancer Plant Recommendation},author={Amintoosi, Mahmood and Kohan-Baghkheirati, Eisa},booktitle={The 2nd International and 4th National Conference on Biomathematics},year={2023},address={Babolsar, Iran},month=feb,organization={University of Mazandaran},pages={470-475},}
2021
On the Minimum of True Matches in Exact Graph Matching with Simulated Annealing
@article{Ezzati99,author={Ezzati, Hashem and Amintoosi, Mahmood and Tabasi, Hashem},title={On the Minimum of True Matches in Exact Graph Matching with Simulated Annealing},journal={Journal of Algorithms and Computation},volume={53},number={1},pages={123--134},year={2021},}
2020
الگوریتم ژنتیکِ آگاه از بهترین عضو با کاربرد در رنگ‌آمیزی و بعدمتریک گراف
@article{ModifiedGA-iranaict99,title={الگوریتم ژنتیکِ آگاه از بهترین عضو با کاربرد در رنگ‌آمیزی و بعدمتریک گراف},author={امین‌طوسی, محمود and عزتی, هاشم},journal={نشریه فناوری اطلاعات و ارتباطات ایران},year={2020},number={42,43},pages={143--154},volume={12},address={انجمن فناوری اطلاعات و ارتباطات ایران},language={persian},note={{The aware genetic algorithm of the best member, applied to graph coloring and metric-dimension of the graph problem}},}
2019
محاسبه بعد متریک گراف با الگوریتم شبیه‌سازی تبریدی
@inproceedings{Ezzati98-TSCO-GD,title={محاسبه بعد متریک گراف با الگوریتم شبیه‌سازی تبریدی},author={عزتی, هاشم and امین‌طوسی, محمود},booktitle={سومین سمینار کنترل و بهینه‌سازی},year={2019},address={دانشگاه حکیم سبزواری},date={1398-08-23},language={persian},pages={39-42},note={{Computing Graph Metric Dimension using Simulated Annealing}},}
2017
Solving uncapacitated facility location problem by cuckoo optimization algorithm
@inproceedings{Hokmabadi96Coco,title={Solving uncapacitated facility location problem by cuckoo optimization algorithm},author={Hokmabadi, Somayye and Amintoosi, Mahmood and Partanian, Mohammad Ali},booktitle={48th Annual Iranian Mathematics Conference},year={2017},address={Hamedan},date={1396-06},}
یک حد بالا برای حداقل تعداد تطابقات درست در مسئله تطابق گراف با روشهای مبتنی بر جستجوی تصادفی
@inproceedings{Ezzati96graph,title={ یک حد بالا برای حداقل تعداد تطابقات درست در مسئله تطابق گراف با روشهای مبتنی بر جستجوی تصادفی},author={عزتی, هاشم and امین‌طوسی, محمود and طبسی, هاشم},booktitle={چهل و هشتمین کنفرانس ریاضی ایران},year={2017},address={همدان},date={1396-06},language={persian},note={{An Upper Bound for Minimum True Matches in Graph Isomorphism with Stochastic Methods}},}
در مسأله مکان‌یابی مراکز سرویس‌دهنده با ظرفیت نامحدود، هدف کمینه کردن هزینه‌های سرویس‌دهی می‌باشد. این مسأله از نوع NP-hard بوده و روشهای فراابتکاری راه‌حل‌های خوبی، در زمان معقول برای این مسائل ارائه می‌نمایند. در این مقاله، سه روش جست‌وجوی تابو، الگوریتم ژنتیک و الگوریتم انبوه‌سازی(ازدحام) ذرات تحت شرایط یکسان پیاده‌سازی شده و نتایج به‌دست آمده با شیوه‌ی جدیدی مورد مقایسه قرار گرفته‌اند. نتایج آزمایشات نشان داده است که به طور کلی الگوریتم ژنتیک روش بهتری برای حل این مسأله است.
@inproceedings{Shahi93UFLP,title={مقایسه سه روش فراابتکاری در حل {UFLP}},author={شاهی, سمیرا and امین‌طوسی, محمود and زعفرانیه, مهدی},booktitle={هفتمین کنفرانس بین‌المللی انجمن ایرانی تحقیق در عملیات},year={2014},address={سمنان},date={1393-03-25},note={{Comparing 3 meta-heuristic methods for solving UFLP}},language={persian},}
در مسئله برش مینیمم هدف مینیمم کردن ظرفیت یالهای برش است. از روشهای تقریبی حل این مسائل میتوان به الگوریتم کارگِر اشاره کرد. که از تلفیق لبه ها به صورت تصادفی استفاده میکند .در این مقاله از شبیه‌سازی تبریدی برای حل این مسئله استفاده شده است و نتایج آن با روش کارگِر مقایسه شده است. نتایج آزمایشات برتری روش پیشنهادی را نسبت به روش کارگِر از منظر سرعت اجرا، نرخ همگرایی و میانگین خطا نشان داده است.
@inproceedings{Hoseini93mincutSA,title={برش کمینه‌ی گراف با شبیه‌سازی تبریدی},author={حسینی, فاطمه‌سادات and امین‌طوسی, محمود},booktitle={هفتمین کنفرانس بین‌المللی انجمن ایرانی تحقیق در عملیات},year={2014},address={سمنان},date={1393-03-25},note={{Graph Minumum Cut using SA}},language={persian},}
مسئله مکان‌یابی p -هاب با ظرفیت نامتناهی در حضور صف M/G/1
مسئله مکان‌یابی هاب یک تعمیم نسبتاً جدید از مسائل مکان‌یابی است. این مسائل با پیدا کردن مکان‌های هاب و تخصیص نقاط تقاضا به این مکان‌ها سرو کار دارد.ما هاب‌ها را که بخش‌های پر ازدحام شبکه هستند، همانند یک صف M/G/1 مدل‌بندی می‌کنیم. در این مقاله ابتدا یک برنامه‌ریزی غیر خطی با محدودیت‌های خطی برای مسئله نمایش می‌دهیم که زمان کلی حمل و نقل بین گره‌های شبکه را مینیمم میکند، سپس این مسئله را با استفاده از الگوریتم ژنتیک حل می‌کنیم و با الگوریتم جستجوی ممنوعه مقایسه می‌کنیم.
@inproceedings{Rezazadeh93hub,title={ مسئله مکان‌یابی {p} -هاب با ظرفیت نامتناهی در حضور صف {M/G/1} },author={رضازاده, معصومه and امین‌طوسی, محمود and زعفرانیه, مهدی},booktitle={چهل و پنجمین کنفرانس ریاضی ایران},year={2014},address={سمنان},date={1393-06},note={{Facility Location Problem in M/G/1 Queue}},language={persian},}
2007
A Fish School Clustering Algorithm: Applied to Student Sectioning Problem
M. Amintoosi, M. Fathy, N. Mozayani, and 1 more author
Dynamics of Continuous Discrete & Impulse Systems, series B: Applications and Algorithms, Dec 2007
Post Proceeding of LSMS2007, Life System Modeling and Simulation 2007, China
@article{Amintoosi07afishschool,title={A Fish School Clustering Algorithm: Applied to Student Sectioning Problem},author={Amintoosi, M. and Fathy, M. and Mozayani, N. and Rahmani, A.T.},journal={Dynamics of Continuous Discrete & Impulse Systems, series B: Applications and Algorithms},year={2007},month=dec,note={Post Proceeding of LSMS2007, Life System Modeling and Simulation 2007, China},pages={696-699},volume={2},}
Using Pattern Matching for Tiling and Packing Problems
@article{Amintoosi07using,title={Using Pattern Matching for Tiling and Packing Problems},author={Amintoosi, M. and SadoghiYazdi, H. and M.Fathy and Monsefi, R.},journal={European Journal of Operational Research},year={2007},note={Indexed by {DBLP} and {SCOPUS}},pages={950-960},volume={183},}
2005
Feature Selection in A Fuzzy Student Sectioning Algorithm
@article{Amintoosi05feature,title={Feature Selection in A Fuzzy Student Sectioning Algorithm},author={Amintoosi, M. and Haddadnnia, J.},journal={Lecture Notes in Computer Science},year={2005},note={Indexed by {DBLP}},pages={147--160},volume={3616},publisher={Springer-Verleg},}
2004
کلاسه‌بندی فازی بهینه دانشجویان با استفاده از یک تابع فازی در حل مسئله برنامه‌ریزی ژنتیکی دروس هفتگی دانشگاه
@inproceedings{Amintoosi04optimum,title={کلاسه‌بندی فازی بهینه دانشجویان با استفاده از یک تابع فازی در حل مسئله برنامه‌ریزی ژنتیکی دروس هفتگی دانشگاه},author={امین‌طوسی, م. and صدوقی‌یزدی, ه.},booktitle={نهمین كنفرانس سالانه انجمن كامپیوتر ایران},year={2004},address={تهران، ایران},month={اسفند},organization={دانشگاه صنعتی شریف},pages={345-352},note={{Student's sectioning using fuzzy inference system}},language={Persian},}
Using Pattern Matching for Tiling and Packing Problems
@inproceedings{Amintoosi04using,title={Using Pattern Matching for Tiling and Packing Problems},author={Amintoosi, M. and Monsefi, R. and Haddadnia, J.},booktitle={Fifth International Conference on Computer Sciences},year={2004},address={Metz,France},month=jul,pages={97-104},publisher={Hermes Science Publishing},series={Modeling, Computation and Optimization in Information Systems and Management Sciences}}
@inproceedings{Amintoosi04fuzzy,title={Fuzzy Student Sectioning},author={Amintoosi, M. and Yazdi, H. Sadoghi and Haddadnnia, J.},booktitle={PATAT04: Practice and Theory of Automated Timetabling},year={2004},address={USA},month=aug,pages={421-424}}
2002
A Genetic-Neuro Algorithm for Tiling Problems with Rotation and Reflection of Figures
@article{Monsefi02agenetic,title={A Genetic-Neuro Algorithm for Tiling Problems with Rotation and Reflection of Figures},author={Monsefi, R. and Amintoosi, M.},journal={Iranian Journal of Science and Technology, Transaction B},year={2002},month=dec,note={Indexed by {{ACM}}},number={B4},pages={693-700},volume={26},address={Shiraz University},}
@incollection{Amintoosi79-NP-Hard,title={مروری بر مسائل {NP-Hard} و {NP-Complete}},author={امین‌طوسی, م.},booktitle={مجله صفر و یک },publisher={گروه کامپیوتر، دانشگاه فردوسی مشهد},year={2000},address={مشهد، ایران},month={بهار},note={شماره سوم, {A review on NP-Hard and NP-Complete Problems}},pages={۲۵-۳۳},language={Persian},}
جورچینی قطعات راست گوشه با استفاده از شبكه های عصبی و الگوریتم ژنتیك
@inproceedings{Monsefi00agenetic,title={جورچینی قطعات راست گوشه با استفاده از شبكه های عصبی و الگوریتم ژنتیك},author={منصفی, ر. and امین‌طوسی, م.},booktitle={پنجمین کنفرانس سالانه انجمن کامپیوتر ایران},year={2000},address={تهران، ایران},month={بهمن},organization={دانشگاه شهید بهشتی},pages={۲۹۸-۳۰۴},note={{Tiling Problem using Neural Networks and Genetic Algorithm}},language={Persian}}
Using Pattern Matching for Tiling and Packing ProblemsIn Fifth International Conference on Computer Sciences, Jul 2004
جورچینی قطعات راست گوشه با استفاده از شبكه های عصبی و الگوریتم ژنتیكIn پنجمین کنفرانس سالانه انجمن کامپیوتر ایران, بهمن 2000Tiling Problem using Neural Networks and Genetic Algorithm