Computational study of separation algorithms for clique inequalities
Computational study of separation algorithms for clique inequalities
复制标题
团不等式分离算法的计算研究
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
S. Smriglio
中科院分区：
文献类型：
--
作者：
Francesca Marzi;F. Rossi;S. Smriglio
团不等式出现在许多组合优化问题的线性描述中。在一般情况下，他们形成一个指数的家庭，此外，相关的分离问题是强NP-困难的，相当于一个最大重量团的问题。因此，大多数已知的（精确的和启发式的）分离过程遵循最大团算法的分解方案。我们引入了一个新的启发式，旨在构建一个集合（违反）团不等式覆盖所有的边缘的基础图形。我们提出了一个广泛的计算经验表明，这非常接近一个确切的分离甲骨文的结果，同时比标准的questiristics更快。
Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.