توصيفگر ها :
برنامه‌ريزي خطي عدد صحيح مختلط , مسئله مجموعه رأس بازخورد كمينه , مسئله مجموعه رأس بازخورد مستقل , مسئله مجموعه رأس بازخورد همبند , مسائل NP –سخت
چكيده فارسي :
مسئله‌ي مجموعه رأس بازخورد كمينه، يك مسئله‌ي NP-سخت است، هدف از حل آن، يافتن حداقل تعداد رأس‌هايي است كه بايد از يك گراف حذف شوند تا گراف حاصل، دور نداشته باشد. مسئله مجموعه رأس بازخورد كمينه در هوش مصنوعي تحت عنوان برش دور نيز شناخته مي‌شود. مسئله مجموعه رأس بازخورد، كاربردهاي فراواني در زمينه‌هاي مختلف دارد. ازجمله، جلو‌گيري و حذف بن‌بست در سيستم‌هاي عامل، طراحي چيپ و تراشه‌هاي VLSI، مسائل ارضاي محدوديت در هوش‌مصنوعي، بيوانفورماتيك و پيش‌بيني ژن‌هاي سرطاني، استنتاج بيزي، درستي‌سنجي برنامه، شبكه‌هاي نوري، طراحي مدارهاي تركيبي. براي حل اين مسئله، رويكردهاي دقيق و غيردقيق زيادي معرفي‌شده است. ازجمله رويكردهاي دقيق، استفاده از برنامه‌ريزي عدد صحيح، الگوريتم شاخه و كران، الگوريتم شاخه و برش، برنامه‌نويسي پويا است. ازجمله رويكردهاي غيردقيق، مي‌توان به جستجوي ممنوعه، جستجوي محلي، جستجوي تصادفي حريصانه، الگوريتم ممتيك اشاره كرد. گونه‌هاي مختلفي از مسئله مجموعه رأس بازخورد كمينه وجود دارد كه برخي از آن‌ها عبارتند از: مجموعه رأس بازخورد زيرمجموعه، مجموعه رأس بازخورد مستقل، مجموعه رأس بازخورد همبند، مجموعه رأس بازخورد متمايز. هدف اين پژوهش، تمركز بر روي گونه‌هاي معيني از اين مسئله و ارائه رويكردهاي دقيق براي حل آن‌هاست. براي دو گونه مجموعه رأس بازخورد مستقل و مجموعه رأس بازخورد همبند، تا آنجا كه اطلاع داريم، تاكنون رويكرد‌ي دقيق ارائه نشده است. به همين دليل، ما در اين پژوهش با بهره‌گيري از دو مدل موجود براي مسئله كلاسيك مجموعه رأس بازخورد، مدل‌هايي فشرده براي مسئله مجموعه رأس بازخورد مستقل و همبند ارائه مي‌دهيم. همچنين، گونه‌ي ديگري از مسئله مجموعه رأس بازخورد را در نظر گرفته كه هدف آن، يافتن كمترين تعداد از رئوس است كه حذف آن‌ها موجب پديد آمدن مؤلفه‌هاي همبندي به اندازه‌هاي كوچك يا بدون دور مي‌شود. دو فرمول برنامه‌ريزي خطي عدد صحيح براي اين گونه جديد ارائه مي‌دهيم. با استفاده از نتايج حاصل از شبيه‌سازي، هردو مدل ارائه‌شده براي هر يك از گونه‌ها را مورد مقايسه قرار مي‌دهيم.
چكيده انگليسي :
The minimum feedback vertex set problem is an NP-hard problem and its goal is to find the minimum number of vertices that must be removed from a graph so that the resulting graph is cycle-free. In artificial intelligence the problem is also known as the cycle cutset problem. This problem has many applications in different fields, including preventing and eliminating deadlocks in operating systems, chip design and VLSI chips, constraint satisfaction problem in artificial intelligence, bioinformatics and cancer gene prediction, Bayesian inference, program verification, optical networks, integrated circuit design, automated storage and retrieval systems. To solve this problem, many exact and inexact approaches have been introduced, including integer linear programming models, branch-and-bound and branch-and-cut routines and dynamic programming. Among the inexact approaches, we can mention tabu search, local search, greedy randomized search, and memetic algorithm. There are different variants of the problem, some of which are: subset feedback vertex set, independent feedback vertex set and connected feedback vertex set. In this research we focus on two variants of this problem, i.e. the independent feedback vertex set problem and the connected feedback vertex set problem and provided some ILP formulations to solve them. As far as we know, no exact approach has been presented for these variants. In this research, by modifying the formulations presented in Rafael et al. (2021),we present some compact ILP models for these variants. We also consider another variant of the problem called as the generalized feedback vertex set problem and present two ILP formulations for it.
