کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478233 | 1446039 | 2014 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An analytical comparison of the LP relaxations of integer models for the k-club problem An analytical comparison of the LP relaxations of integer models for the k-club problem](/preview/png/478233.png)
• Comparison of formulations for the 3-club problem, from the LP relaxation standpoint.
• New enhanced formulation for the 3-club problem.
• New enhanced formulation for the k-club problem (k > 1).
• New formulation for a variant of the 3-club problem with additional robustness constraints.
Given an undirected graph G = (V, E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k = 3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k = 3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k > 1) and show how to modify one of the new formulations for the case k = 3 in order to accommodate additional constraints recently proposed in the literature.
Journal: European Journal of Operational Research - Volume 232, Issue 3, 1 February 2014, Pages 489–498