Carnegie Mellon University
Browse

Exploiting Semidefinite Relaxations in Constraint Programming

Download (169.32 kB)
journal contribution
posted on 1976-01-01, 00:00 authored by Willem-Jan Van HoeveWillem-Jan Van Hoeve
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 generally produces a tight bound for the solution value, which improves the pruning behaviour. Experimental results on stable set problem instances and maximum clique problem instances show that constraint programming can indeed greatly benfiet from semidefinite relaxations.

History

Date

1976-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC