کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4959876 1445957 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The generalized independent set problem: Polyhedral analysis and solution approaches
ترجمه فارسی عنوان
مجموعه ای از مشکلات مجموعه ای مستقل: تجزیه و تحلیل چند بعدی و راه حل های آن
کلمات کلیدی
ترجمه چکیده
در مسئله مجموعه مستقل مستقل، ما یک نمودار، درآمد برای هر رأس و مجموعه ای از لبه های قابل جابجایی با هزینه های مربوط به حذف مربوطه به ما داده می شود، و ما می خواهیم مجموعه ای مستقل پیدا کنیم که سود خالص را به حداکثر برساند، یعنی تفاوت بین درآمد جمع آوری شده برای رأس ها در مجموعه مستقل و هزینه های مربوط به حذف هر لبه با هر دو نقطه پایانی در مجموعه مستقل. ما در بررسی چندضلعی همراه با یک فرمول برنامه نویسی خطی 0-1 از مسئله مجموعه مستقل مستقل، به ایجاد تعدادی از نابرابری های ناشی از نقشی پرداخته و برنامه های مبتنی بر برنامه نویسی مبتنی بر خطی را برای به دست آوردن راه حل های با کیفیت بالا در مدت زمان کوتاه طراحی می کنیم. ما همچنین یک روش اکتشافی مبتنی بر یک فرمول برنامه نویسی درجه یک 0-1 بدون محدودیت مشکلی مستقل مجموعه عمومی را توسعه می دهیم. در یک مطالعه محاسباتی گسترده، عملکرد این اکتشافی را از نظر کیفیت و کارایی ارزیابی می کنیم. سپس بهترین اکتشافی برای تولید یک راه حل اولیه برای یک الگوریتم شاخه ای و برش استفاده می شود که از برخی از نابرابری هایی که باعث ایجاد چهره پیشنهادی می شود استفاده می شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
مجموعه ای از مشکلات مجموعه ای مستقل: تجزیه و تحلیل چند بعدی و راه حل های آن
چکیده انگلیسی
In the Generalized Independent Set Problem, we are given a graph, a revenue for each vertex, and a set of removable edges with associated removal costs, and we seek to find an independent set that maximizes the net benefit, i.e., the difference between the revenues collected for the vertices in the independent set and the costs incurred for any removal of edges with both endpoints in the independent set. We study the polyhedron associated with a 0-1 linear programming formulation of the Generalized Independent Set Problem, deriving a number of facet-inducing inequalities, and we develop linear programming based heuristics to obtain high-quality solutions in a short amount of time. We also develop a heuristic method based on an unconstrained 0-1 quadratic programming formulation of the Generalized Independent Set Problem. In an extensive computational study, we assess the performance of these heuristics in terms of quality and efficiency. The best heuristic is then used to produce an initial solution for a branch-and-cut algorithm which uses some of the proposed facet-inducing inequalities.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 260, Issue 1, 1 July 2017, Pages 41-55
نویسندگان
, , ,