A new family of facet defining inequalities for the maximum edge-weighted clique problem
Franklin Djeumou Fomeni (franklinaims.ac.za)
Abstract: This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the maximum edge-weighted clique problem that use cutting planes.
Keywords: Edge-weighted clique problem, Cutting planes, Separation algorithm, In- teger programming, Boolean quadric polytope, facet defining inequalities.
Category 1: Integer Programming (Cutting Plane Approaches )
Category 2: Integer Programming (0-1 Programming )
Category 3: Combinatorial Optimization
Citation: Cahiers du GERAD, G-2015-71. Polytechnique Montreal - GERAD
Entry Submitted: 08/31/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|