Paper Info
Title
Computational study of separation algorithms for clique inequalities.
Abstract
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.
Year
DOI
Venue
2019
10.1007/s00500-019-03769-y
Soft Comput.
Keywords
Field
DocType
Clique inequalities, Separation problem, Cutting plane algorithm
Graph,Heuristic,Clique,Computer science,Exponential family,Oracle,Algorithm,Heuristics,Separation problem,Clique problem
Journal
Volume
Issue
ISSN
23
9
1433-7479
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Francesca Marzi100.68
Fabrizio Rossi214016.33
Stefano Smriglio315314.81