Exploiting semidefinite relaxations in constraint programming

Constraint programming uses enumeration and search tree pruning to solve combinatorial optimization problems. In order to speed up this solution process, we investigate the use of semidefinite relaxations within constraint programming. In principle, we use the solution of a semidefinite relaxation to guide the traversal of the search tree, using a limited discrepancy search strategy. Furthermore, a semidefinite relaxation produces a bound for the solution value, which is used to prune parts of the search tree. Experimental results on stable set and maximum clique problem instances show that constraint programming can indeed greatly benefit from semidefinite relaxations.

• Publication year

  2004

• Venue

  Computers & Operations Research

• Publication date

  2004-07-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.cor.2005.01.011arXiv cs/0407041
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Exploiting Relaxations in CP

  2004cited by this paper
• Constraint and Integer Programming

  2004cited by this paper
• Using Constraint Programming to Solve the Maximum Clique Problem

  2003cited by this paper
• CPAIOR ’ 03 Solving the Maximum Clique Problem with Constraint Programming

  2003influential reference
• Principles of constraint programming

  2003cited by this paper
• Constraint and Integer Programming: Toward a Unified Methodology (Operations Research/Computer Science Interfaces, 27)

  2003cited by this paper
• A Hybrid Constraint Programming and Semidefinite Programming Approach for the Stabe Set Problem

  2003influential reference
• Reduced Cost-Based Ranking for Generating Promising Subproblems

  2002cited by this paper
• Semidefinite programming and integer programming

  2002cited by this paper
• Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique

  2002cited by this paper
• A fast algorithm for the maximum clique problem

  2002cited by this paper
• Computational Experience with Stable Set Relaxations

  2002cited by this paper
• New trends in high performance computing

  2001cited by this paper
• Solving Graph Bisection Problems with Semidefinite Programming

  2000cited by this paper
• Handbook of Semidefinite Programming

  2000cited by this paper
• Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling

  2000cited by this paper
• The Maximum Clique Problem

  1999cited by this paper
• A C library for semidefinite programming

  1999cited by this paper
• CSDP, A C library for semidefinite programming

  1999cited by this paper
• Handbook of Combinatorial Optimization

  1998cited by this paper
• Combinatorial optimization

  1997cited by this paper
• Connections between semidefinite relaxations of the max-cut and stable set problems

  1997cited by this paper
• Improved Approximation Algorithms for Maximum Cut and Satissability Problems Using Semideenite Programming

  1997cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Limited Discrepancy Search

  1995cited by this paper
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization

  1995cited by this paper
• LAPACK Users' Guide

  1995cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Geometric Algorithms and Combinatorial Optimization

  1988influential reference
• Combinatorial optimization:Algorithms and complexity

  1984cited by this paper
• On the Shannon capacity of a graph

  1979cited by this paper

• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments

  2013cites this paper
• Semidefinite Programming and Constraint Programming

  2012influential citation
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique

  2010cites this paper
• k-Clustering Minimum Biclique Completion via a Hybrid CP and SDP Approach

  2009influential citation
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: 6th International Conference, CPAIOR 2009 Pittsburgh, PA, USA, May 27-31, 2009 Proceedings

  2009cites this paper
• Seventh Cologne Twente Workshop on Graphs and Combinatorial Optimization, gargano, Italy, 13-15 May, 2008

  2008cites this paper
• An Interval Constraint Branching Scheme for Lattice Domains

  2006cites this paper
• Operations research techniques in constraint programming

  2005cites this paper