arXiv:cs/0407041v1 [cs.DM] 16 Jul 2004

Exploiting Semidefinite Relaxations in Constraint
Programming
Willem Jan van Hoeve
CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands
W.J.van.Hoeve@cwi.nl
July 16, 2004
Abstract
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.

1

Introduction

Constraint programming models for combinatorial optimization problems consist of variables on finite domains, constraints on those variables and an objective function to be optimized. In general, constraint programming solvers use
domain value enumeration to solve combinatorial optimization problems. By
propagation of the constraints (i.e. removal of inconsistent values), large parts
of the resulting search tree may be pruned. Because combinatorial optimization problems are NP-hard in general, constraint propagation is essential to
make constraint programming solvers practically applicable. Another essential
part concerns the enumeration scheme, that defines and traverses a search tree.
Variable and value ordering heuristics as well as tree traversal heuristics greatly
influence the performance of the resulting constraint programming solver.
In this work we investigate the possibility of using semidefinite relaxations in
constraint programming. This investigation involves the extraction of semidefinite relaxations from a constraint programming model, and the actual use of
the relaxation inside the solution scheme. We propose to use the solution of a
semidefinite relaxation to define search tree ordering and traversal heuristics.
Effectively, this means that our enumeration scheme starts at the suggestion
1

made by the semidefinite relaxation, and gradually scans a wider area around
this solution. Moreover, we use the solution value of the semidefinite relaxation
as a bound for the objective function, which results in stronger pruning. By applying a semidefinite relaxation in this way, we hope to speed up the constraint
programming solver significantly. These ideas were motivated by a previous
work [1], in which a linear relaxation was proved to be helpful in constraint
programming.
We implemented our method and provide experimental results on the stable set problem and the maximum clique problem, two classical combinatorial
optimization problems. We compare our method with a standard constraint
programming solver, and with specialized solvers for maximum clique problems. As computational results will show, our method obtains far better results
than a standard constraint programming solver. However, on maximum clique
problems, the specialized solvers appear to be much faster than our method.
This paper is an extended and revised version of [2]. In the current version, a more general view on the proposed method is presented. Namely, in [2]
the method was proposed for stable set problems only, while in this paper we
propose the method to be applied to any constraint programming problem, although not all problems will be equally suitable. Furthermore, in [2] the method
uses a subproblem generation framework on which limited discrepancy search
is applied. In the current work it has been replaced by limited discrepancy
search on single values, which is more concise while preserving the behaviour
of the algorithm. Finally, more experimental results are presented, including
problem characterizations and instances of the DIMACS benchmark set for the
maximum clique problem.
The outline of the paper is as follows. The next section gives a motivation
for the approach proposed in this work. Then, in Section 3 some preliminaries
on constraint and semidefinite programming are given. A description of our
solution framework is given in Section 4. In Section 5 we introduce the stable
set problem and the maximum clique problem, integer optimization formulations
and a semidefinite relaxation. Section 6 presents the computational results. We
conclude in Section 7 with a summary and future directions.

2

Motivation

NP-hard combinatorial optimization problems are often solved with the use of
a polynomially solvable relaxation. Often (continuous) linear relaxations are
chosen for this purpose. Also within constraint programming, linear relaxations
are widely used, see [3] for an overview. Let us first motivate why in this
paper a semidefinite relaxation is used rather than a linear relaxation. For some
problems, for instance for the stable set problem, standard linear relaxations are
not very tight and not informative. One way to overcome this problem is to
identify and add linear constraints that strengthen the relaxation. But it may
be time-consuming to identify such constraints, and by enlarging the model the
solution process may slow down.

2

On the other hand, several papers on approximation theory following [4]
have shown the tightness of semidefinite relaxations. However, being tighter,
semidefinite programs are more time-consuming to solve than linear programs in
practice. Hence one has to trade strength for computation time. For some (large
scale) applications, semidefinite relaxations are well-suited to be used within a
branch and bound framework (see for instance [5]). Moreover, our intention is
not to solve a relaxation at every node of the search tree. Instead, we propose
to solve only once a relaxation, before entering the search tree. Therefore, we
are willing to make the trade-off in favour of the semidefinite relaxation.
Finally, investigating the possibility of using semidefinite relaxations in constraint programming is worthwile in itself. To our knowledge the cross-fertilization of semidefinite programming and constraint programming has not yet
been investigated. Hence, this paper should be seen as a first step toward the
cooperation of constraint programming and semidefinite programming.

3
3.1

Preliminaries
Constraint Programming

In this section we briefly introduce the basic concepts of constraint programming that are used in this paper. A thorough explanation of the principles of
constraint programming can be found in [6].
A constraint programming model consists of a set of variables, corresponding
variable domains, and a set of constraints restricting those variables. In case
of optimization problems, also an objective function is added. In this work
the variable domains are assumed to be finite. A constraint c is defined as a
subset of the Cartesian product of the domains of the variables that are in c.
Constraints may be of any form (linear, nonlinear, logical, symbolic, etcetera),
provided that the constraint programming solver contains an algorithm to check
its satisfiability, or even to identify globally inconsistent domain values.
Basically, a constraint programming solver tries to find a solution of the
model by enumerating all possible variable-value assignments such that the
constraints are all satisfied. Because there are exponentially many possible
assignments, constraint propagation is needed to prune large parts of the corresponding search tree. Constraint propagation tries to remove inconsistent values
from variable domains before the variables are actually instantiated. Hence, one
doesn’t need to generate the whole search tree, but only a part of it, while still
preserving a complete (exact) solution scheme. The general solution scheme is
an iterative process in which branching decisions are made, and the effects are
propagated subsequently.
Variable and value ordering heuristics, which define the search tree, greatly
influence the constraint propagation, and with that the performance of the
solver. If no suitable variable and value ordering heuristics are available, constraint programming solvers often use a lexicographic variable and value ordering, and depth-first search to traverse the tree. However, when good heuristics

3

are available, they should be applied.
When ‘perfect’ value and variable ordering heuristics are followed, it will
lead us directly to the optimal solution (possibly unproven). Although perfect
heuristics are often not available, some heuristics come pretty close. In such
cases, one should try to deviate from the first heuristic solution as little as
possible. This is done by traversing the search tree using a limited discrepancy
search strategy (LDS) [7] instead of depth-first search.
LDS is organized in waves of increasing discrepancy from the first solution
provided by the heuristic. The first wave (discrepancy 0) exactly follows the
heuristic. The next waves (discrepancy i, with i > 0), explore all the solutions
that can be reached when i derivations from the heuristic are made. Typically,
LDS is applied until a maximum discrepancy has been reached, say 3 or 4.
Although being incomplete (inexact), the resulting strategy often finds good
solutions very fast, provided that the heuristic is informative. Of course LDS can
also be applied until all possible discrepancies have been considered, resulting
in a complete strategy.

3.2

Semidefinite Programming

In this section we briefly introduce semidefinite programming. A large number
of references to papers concerning semidefinite programming are on the web
pages [8] and [9]. A general introduction on semidefinite programming applied
to combinatorial optimization is given in [10] and [11].
Semidefinite programming makes use of positive semidefinite matrices of
variables. A matrix X ∈ Rn×n is said to be positive semidefinite (denoted by
X  0) when y T Xy ≥ 0 for all vectors y ∈ Rn . Semidefinite programs have the
form
max tr(W X)
s.t. tr(Aj X) ≤ bj (j = 1, . . . , m)
(1)
X  0.
Here tr(X) denotes
Pn the trace of X, which is the sum of its diagonal elements,
i.e. tr(X) = i=1 Xii . The matrix X, the cost matrix W ∈ Rn×n and the
constraint matrices Aj ∈ Rn×n are supposed to be symmetric. The m reals bj
and the m matrices Aj define m constraints.
We can view semidefinite programming as an extension of linear programming. Namely, when the matrices W and Aj (j = 1, . . . , m) are all supposed
to be diagonal matrices1 , the resulting semidefinite program is equal to a linear
program, where the matrix X is replaced by a non-negative vector of variables
x ∈ Rn . In particular, then a semidefinite programming constraint tr(Aj X) ≤ bj
corresponds to a linear programming constraint aT
j x ≤ bj , where aj represents
the diagonal of Aj .
Theoretically, semidefinite programs have been proved to be polynomially
solvable to any fixed precision using the so-called ellipsoid method (see for in1A

diagonal matrix is a matrix with nonnegative values on its diagonal entries only.

4

stance [12]). In practice, nowadays fast ‘interior point’ methods are being used
for this purpose (see [13] for an overview).
Semidefinite programs may serve as a continuous relaxation for (integer)
combinatorial optimization problems. Unfortunately, it is not a trivial task to
obtain a computationally efficient semidefinite program that provides a tight
solution for a given problem. However, for a number of combinatorial optimization problems such semidefinite relaxations do exist, for instance the stable
set problem, the maximum cut problem, quadratic programming problems, the
maximum satisfiability problem, and many others (see [11] for an overview).

4

Solution Framework

The skeleton of our solution framework is formed by the constraint programming
enumeration scheme, or search tree, as explained in Section 3.1. Within this
skeleton, we want to use the solution of a semidefinite relaxation to define the
variable and value ordering heuristics. In this section we first show how to
extract a semidefinite relaxation from a constraint programming model. Then
we give a description of the usage of the relaxation within the enumeration
scheme.

4.1

Building a Semidefinite Relaxation

We start from a constraint programming model consisting of a set of variables
{v1 , . . . , vn }, corresponding finite domains {D1 , . . . , Dn }, a set of constraints
and an objective function. From this model we need to extract a semidefinite
relaxation. In general, a relaxation is obtained by removing or replacing one
or more constraints such that all solutions are preserved. If it is possible to
identify a subset of constraints for which a semidefinite relaxation is known,
this relaxation can be used inside our framework. Otherwise, we need to build
up a relaxation from scratch. This can be done in the following way.
If all domains D1 , . . . , Dn are binary, a semidefinite relaxation can be extracted using a method proposed by [14], which is explained below. In general,
however, the domains are non-binary. In that case, we transform the variables
vi and the domains Di into corresponding binary variables xij for i ∈ {1, . . . , n}
and j ∈ Di :
vi = j ⇔ xij = 1,
(2)
vi 6= j ⇔ xij = 0.
We will then use the binary variables xij to construct a semidefinite relaxation.
Of course, the transformation has consequences for the constraints also, which
will be discussed below.
The method to transform a model with binary variables into a semidefinite
relaxation, presented in [14], is the following. Let d ∈ {0, 1}N be a vector of
binary variables, where N is a positive integer. Construct the (N + 1) × (N + 1)

5

variable matrix X as
X=

 

1
1
(1 dT ) =
d
d

dT
ddT



.

Then X can be constrained to satisfy
X0

Xii = X0i

(3)
∀i ∈ {1, . . . , N }

(4)

where the rows and columns of X are indexed from 0 to N . Condition (4)
expresses the fact that d2i = di , which is equivalent to di ∈ {0, 1}. Note however
that the latter constraint is relaxed by requiring X to be positive semidefinite.
The matrix X contains the variables to model our semidefinite relaxation.
Obviously, the diagonal entries (as well as the first row and column) of this
matrix represent the binary variables from which we started. Using these variables, we need to rewrite (a part of) the original constraints into the form of
program (1) in order to build the semidefinite relaxation.
In case the binary variables are obtained from transformation (2), not all
constraints may be trivially transformed accordingly. Especially because the
original constraints may be of any form. The same holds for the objective
function. On the other hand, as we are constructing a relaxation, we may choose
among the set of constraints an appropriate subset to include in the relaxation.
Moreover, the constraints itself are allowed to be relaxed. Although there is no
‘recipe’ to transform any given original constraint into the form of program (1),
one may use results from the literature [11]. For instance, for linear constraints
on binary variables a straightforward translation is given in Section 3.2.

4.2

Applying the Semidefinite Relaxation

At this point, we have either identified a subset of constraints for which a
semidefinite relaxation exists, or built up our own relaxation. Now we show
how to apply the solution to the semidefinite relaxation inside the constraint
programming framework, also depicted in Figure 1. In general, the solution
to the semidefinite relaxation yields fractional values for its variable matrix.
For example, the diagonal variables Xii of the above matrix will be assigned
to a value between 0 and 1. These fractional values serve as an indication for
the original constraint programming variables. Consider for example again the
above matrix X, and suppose it is obtained from non-binary original variables,
by transformation (2). Assume that variable Xii corresponds to the binary
variable xjk (for some integer j and k), which corresponds to vj = k, where vj
is a constraint programming variable and k ∈ Dj . If variable Xii is close to
1, then also xjk is supposed to be close to 1, which corresponds to assigning
vj = k.
Hence, our variable and value ordering heuristics for the constraint programming variables are based upon the fractional solution values of the corresponding variables in the semidefinite relaxation. Our variable ordering heuristic is
6

CP
model:
variables
domains
constraints
objective function

SDP
solve relaxation:
solution value
fractional solution

search:
variable ordering
value ordering
traversal strategy (LDS)

Figure 1: Communication between constraint programming (CP) and semidefinite programming (SDP).
to select first the constraint programming variable for which the corresponding
fractional solution is closest to the corresponding integer solution. Our value
ordering heuristic is to select first the corresponding suggested value. For example, consider again the above matrix X, obtained from non-binary variables by
transformation (2). We select first the variable vj for which Xii , representing
the binary variable xjk , is closest to 1, for some k ∈ Dj and corresponding
integer i. Then we assign value k to variable vj . We have also implemented a
randomized variant of the above variable ordering heuristic. In the randomized
case, the selected variable is accepted with a probability proportional to the
corresponding fractional value.
We expect the semidefinite relaxation to provide promising values. Therefore the resulting search tree will be traversed using limited discrepancy search,
defined in Section 3.1. A last remark concerns the solution value of the semidefinite relaxation, which is used as a bound on the objective function in the
constraint programming model. If this bound is tight, which is the case in our
experiments, it leads to more propagation and a smaller search space.

5

The Stable Set Problem and Maximum Clique
Problem

This section describes the stable set problem and the maximum clique problem
(see [15, 16] for a survey), on which we have tested our algorithm. First we give
their definitions, and the equivalence of the two problems. Then we will focus
on the stable set problem, and formulate it as an integer optimization problem.
From this, a semidefinite relaxation is inferred.

7

5.1

Definitions

Consider an undirected weighted graph G = (V, E), where V = {1, . . . , n} is the
set of vertices and E a subset of edges {(i, j)|i, j ∈ V, i 6= j} of G, with |E| = m.
To each vertex i ∈ V a weight wi ∈ R is assigned (without loss of generality, we
can assume all weights to be nonnegative).
A stable set is a set S ⊆ V such that no two vertices in S are joined by
an edge in E. The stable set problem is the problem of finding a stable set of
maximum total weight in G. This value is called the stable set number of G and
is denoted by α(G)2 . In the unweighted case (when all weights are equal to 1),
this problem amounts to the maximum cardinality stable set problem, which
has been shown to be already NP-hard [17].
A clique is a set C ⊆ V such that every two vertices in C are joined by an
edge in E. The maximum clique problem is the problem of finding a clique of
maximum total weight in G. This value is called the clique number of G and is
denoted by ω(G)3 .
The complement graph of G is G = (V, E), with the same set of vertices
V = {1, . . . , n}, but with edge set E = {(i, j)|i, j ∈ V, (i, j) ∈
/ E, i 6= j}. It
is well known that α(G) = ω(G). Hence, a maximum clique problem can be
translated into a stable set problem on the complement graph. We will do
exactly this in our implementation, and focus on the stable set problem, for
which good semidefinite relaxations exist.

5.2

Integer Optimization Formulation

Let us first consider an integer linear programming formulation for the stable
set problem. We introduce binary variables to indicate whether or not a vertex
belongs to the stable set S. So, for n vertices, we have n integer variables xi
indexed by i ∈ V , with initial domains {0, 1}. In this way, xi = 1 if vertex i is
in S, and xi = 0 otherwise. We can now state P
the objective function, being the
n
sum of the weights of vertices that are in S, as i=1 wi xi . Finally, we define the
constraints that forbid two adjacent vertices to be both inside S as xi + xj ≤ 1,
for all edges (i, j) ∈ E. Hence the integer linear programming model becomes:
Pn
α(G) = max
i=1 wi xi
s.t. xi + xj ≤ 1 ∀(i, j) ∈ E
(5)
xi ∈ {0, 1} ∀i ∈ V.
Another way of describing the same solution set is presented by the following
integer quadratic program
Pn
α(G) = max
i=1 wi xi
s.t.
xi xj = 0 ∀(i, j) ∈ E
(6)
x2i = xi ∀i ∈ V.
2 In the literature α(G) usually denotes the unweighted stable set number. The weighted
stable set number is then denoted as αw (G). In this work, it is not necessary to make this
distinction.
3 ω (G) is defined similar to α (G) and also not distinguished in this paper.
w
w

8

Note that here the constraint xi ∈ {0, 1} is replaced by x2i = xi , similar to
condition (4) in Section 4. This quadratic formulation will be used below to
infer a semidefinite relaxation of the stable set problem.
In fact, both model (5) and model (6) can be used as a constraint programming model. We have chosen the first model, since the quadratic constraints
take more time to propagate than the linear constraints, while having the same
pruning power. To infer the semidefinite relaxation, however, we will use the
equivalent model (6).

5.3

Semidefinite Programming Relaxation

The integer quadratic program (6) gives rise to a well-known semidefinite relaxation introduced by Lovász [18] (see [12] for a comprehensive treatment).
The value of the objective function of this relaxation has been named the theta
number of a graph G, indicated by ϑ(G). For its derivation into a form similar
to program (1), we will follow the same idea as in Section 4 for the general case.
As our constraint programming model uses binary variables already, we can
immediately define the (n + 1) × (n + 1) matrix variable X of our relaxation as


1 xT
X=
x xxT
where the binary vector x again represents the stable set, as in Section 5.2. First
we impose the constraints
X0
Xii = X0i ∀i ∈ {1, . . . , n}

(7)
(8)

as described in Section 4. Next we translate the edge constraints xi xj = 0 from
program (6) into Xij = 0, because Xij represents xi xj . In order to translate
the objective function, we first define the (n + 1) × (n + 1) weight matrix W as
Wii = wi
Wij = 0

∀i ∈ {1, . . . , n},
∀i ∈ {0, . . . , n}, j ∈ {0, . . . , n}, i 6= j.

Then the objective function translates into tr(WX). The semidefinite relaxation
thus becomes
ϑ(G) = max tr(WX)
s.t. Xii = X0i ∀i ∈ V
(9)
Xij = 0 ∀(i, j) ∈ E
X  0.
Note that program (9) can easily be rewritten into the general form of program (1). Namely, Xii = X0i is equal to tr(Ai X) = 0 where the (n + 1) × (n + 1)
matrix Ai consists of all zeroes, except for (Ai )ii = 1, (Ai )i0 = − 12 and
(Ai )0i = − 21 , which makes the corresponding right-hand side (bi entry) equal to
0 (similarly for the edge constraints).

9

The theta number also arises from other formulations, different from the
above, see [12]. In our implementation we have used the formulation that has
been shown to be computationally most efficient among those alternatives [19].
Let us introduce that particular formulation (called ϑ3 in [12]). Again, let
x ∈ {0, 1}n be a vector of binary variables representing
a stable set. Define
√
wi
T
√
the n × n matrix X̃ = ξξ where ξi = P n w x xi . Furthermore, let the
√ j=1 j j
n × n cost matrix U be defined as Uij = wi wj for i, j ∈ V . Observe that in
these definitions we exploit the fact that wi ≥ 0 for all i ∈ V . The following
semidefinite program
ϑ(G) =

max
tr(U X̃)
s.t. tr(X̃) = 1
X̃ij = 0 ∀(i, j) ∈ E
X̃  0

(10)

has been shown to also give the theta number of G, see [12]. When (10) is solved
to optimality, the scaled diagonal element ϑ(G)X̃ii (a fractional value between
0 and 1) serves as an indication for the value of xi (i ∈ V ) in a maximum stable
set (see for instance [19]). Again, it is not difficult to rewrite program (10) into
the general form of program (1).
Program (10) uses matrices of dimension n and m + 1 constraints, while
program (9) uses matrices of dimension n + 1 and m + n constraints. This gives
an indication why program (10) is computationally more efficient.

6

Computational Results

All our experiments are performed on a Sun Enterprise 450 (4 X UltraSPARCII 400MHz) with maximum 2048 Mb memory size, on which our algorithms
only use one processor of 400MHz at a time. As constraint programming solver
we use the ILOG Solver library, version 5.1 [20]. As semidefinite programming
solver, we use CSDP version 4.1 [21], with the optimized ATLAS 3.4.1 [22]
and LAPACK 3.0 [23] libraries for matrix computations. The reason for our
choices is that both solvers are among the fastest in their field, and because
ILOG Solver is written in C++, and CSDP is written in C, they can be hooked
together relatively easy.
We distinguish two algorithms to perform our experiments. The first algorithm is a sole constraint programming solver, which uses a standard enumeration strategy. This means we use a lexicographic variable ordering, and
we select domain value 1 before value 0. The resulting search tree is traversed
using a depth-first search strategy. After each branching decision, its effect is
directly propagated through the constraints. As constraint programming model
we have used model (5), as was argued in Section 5.2.
The second algorithm is the one proposed in Section 4. It first solves the
semidefinite program (10), and then calls the constraint programming solver.
In this case, we use the randomized variable ordering heuristic, defined by the
10

10000

n=30
n=40
n=50
n=60

1e+06

n=30
n=40
n=50
n=60

1000

100000

log time (s)

log number of backtracks

1e+07

10000
1000
100

100
10
1
0.1

10

0.01
0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1

0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

edge density

1

edge density

Figure 2: Performance of the constraint programming solver on random instances with n vertices.
10000

n=30
n=40
n=50
n=60

log time (s)

1000
100
10
1
0.1
0.01
0

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
edge density

1

Figure 3: Performance of the semidefinite programming solver on random instances with n vertices.
solution of the semidefinite relaxation. The resulting search tree is traversed
using a limited discrepancy search strategy. In fact, in order to improve our
starting solution, we repeat the search for the first solution n times, (where n
is the number of variables), and the best solution found is the heuristic solution
to be followed by the limited discrepancy search strategy.

6.1

Characterization of Problem Instances

We will first identify general characteristics of the constraint programming solver
and the semidefinite programming solver applied to stable set problems. It
appears that both solvers are highly dependent on the edge density of the graph,
i.e. 1 (nm
2 −n) for a graph with n vertices and m edges. We therefore generated
2
random graphs on 30, 40, 50 and 60 vertices, with density ranging from 0.01 up
to 0.95. Our aim is to identify the hardness of the instances for both solvers,
parametrized by the density. Based upon this information, we can identify the
kind of problems our algorithm is suitable for.
11

We have plotted the performance of both solvers in Figure 2 and Figure 3.
Here the constraint programming solver solves the problems to optimality, while
the semidefinite programming solver only solves the semidefinite relaxation. For
the constraint programming solver, we depict both the number of backtracks
and the time needed to prove optimality. For the semidefinite programming
solver we only plotted the time needed to solve the relaxation. Namely, this
solver does not use a tree search, but a so-called primal-dual interior point
algorithm. Note that we use a log-scale for time and number of backtracks in
these pictures.
From these figures, we can conclude that the constraint programming solver
has the most difficulties with instances up to density around 0.2. Here we see
the effect of constraint propagation. As the number of constraints increases,
the search tree can be heavily pruned. On the other hand, our semidefinite
relaxation suffers from every edge that is added. As the density increases, the
semidefinite program increases accordingly, as well as its computation time. Fortunately, for the instances up to 0.2, the computation time for the semidefinite
relaxation is very small. Consequently, our algorithm is expected to behave best
for graphs that have edge density up to around 0.2. For graphs with a higher
density, the constraint programming solver is expected to use less time than the
semidefinite programming solver, which makes the application of our method
unnecessary.

6.2

Random Weighted and Unweighted Graphs

Our first experiments are performed on random weighted and unweighted graphs.
We generated graphs with 50, 75, 100, 125 and 150 vertices and edge density
from 0.05, 010 and 0.15, corresponding to the interesting problem area. The
results are presented in Table 1. Unweighted graphs on n vertices and edge
density r are named ‘gndr’. Weighted graphs are similarly named ‘wgndr’.
The first five columns of the table are dedicated to the instance, reporting
its name, the number of vertices n and edges m, the edge density and the
(best known) value of a stable set, α. The next three columns (CP) present
the performance of the constraint programming solver, reporting the best found
estimate of α, the total time and the total number of backtracks needed to prove
optimality. The last five columns (SDP+CP) present the performance of our
method, where also a column has been added for the discrepancy of the best
found value (best discr), and a column for the time needed by the semidefinite
programming solver (sdp time).
Table 1 shows that our approach always finds a better (or equally good)
estimate for α than the standard constraint programming approach. This becomes more obvious for larger n. However, there are two (out of 30) instances in
which our method needs substantially more time to achieve this result (g75d015
and wg75d010). A final observation concerns the discrepancy of the best found
solutions. Our method appears to find those (often optimal) solutions at rather
low discrepancies.

12

Table 1: Computational results on random graphs, with n vertices and m edges.
All times are in seconds. The time limit is set to 1000 seconds.
instance
name
g50d005
g50d010
g50d015
g75d005
g75d010
g75d015
g100d005
g100d010
g100d015
g125d005
g125d010
g125d015
g150d005
g150d010
g150d015
wg50d005
wg50d010
wg50d015
wg75d005
wg75d010
wg75d015
wg100d005
wg100d010
wg100d015
wg125d005
wg125d010
wg125d015
wg150d005
wg150d010
wg150d015

6.3

n
50
50
50
75
75
75
100
100
100
125
125
125
150
150
150
50
50
50
75
75
75
100
100
100
125
125
125
150
150
150

m
70
114
190
138
282
426
254
508
736
393
791
1160
545
1111
1566
70
126
171
128
284
409
233
488
750
372
767
1144
588
1167
1630

edge
density
0.06
0.09
0.16
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.14
0.06
0.10
0.14
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15
0.05
0.10
0.15

α
27
22
17
36
≥ 25
21
43
≥ 31
≥ 24
≥ 49
≥ 33
≥ 27
≥ 52
≥ 38
≥ 29
740
636
568
1761
1198
972
2302
≥ 1778
≥ 1412
≥ 3779
≥ 2796
≥ 1991
≥ 4381
≥ 3265
≥ 2828

α
27
22
17
≥ 35
≥ 25
21
≥ 40
≥ 30
≥ 24
≥ 44
≥ 30
≥ 24
≥ 44
≥ 32
≥ 26
740
636
568
1761
1198
972
≥ 2176
≥ 1778
≥ 1412
≥ 3390
≥ 2175
≥ 1899
≥ 3759
≥ 2533
≥ 2518

CP
total
backtime
tracks
5.51
50567
28.54
256932
5.83
48969
limit
limit
170.56 1209019
limit
limit
limit
limit
limit
limit
limit
limit
limit
4.41
30528
3.12
19608
4.09
25533
744.29 4036453
325.92 1764478
40.31
208146
limit
limit
limit
limit
limit
limit
limit
limit
limit

α
27
22
17
36
≥ 25
21
43
≥ 31
≥ 24
≥ 49
≥ 33
≥ 27
≥ 52
≥ 38
≥ 29
740
636
568
1761
1198
972
2302
≥ 1778
≥ 1412
≥ 3779
≥ 2796
≥ 1991
≥ 4381
≥ 3265
≥ 2828

SDP + CP
best
sdp
total
discr
time
time
0
0.26
0.27
0
0.35
0.36
0
0.49
0.49
0
0.72
0.73
5
1.4
limit
0
2.81 664.92
0
2.07
2.1
0
4.94
limit
4
9.81
limit
1
4.92
limit
6
12.58
limit
1
29.29
limit
3
10.09
limit
4
27.48
limit
8
57.86
limit
0
0.29
0.3
0
0.41
0.41
0
0.59
4.93
0
1.05
1.07
13
1.9
924.2
0
3.62
51.08
0
2.59
2.62
2
6.4
limit
2
15.21
limit
3
5.39
limit
0
18.5
limit
4
38.24
limit
3
13.57
limit
9
40.68
limit
11
82.34
limit

backtracks
0
0
0
0
1641692
0

0
0
13042
0
1974913
87490
0

Graphs Arising from Coding Theory

The next experiments are performed on structured (unweighted) graphs arising
from coding theory, obtained from [24]. We have used those instances that
were solvable in reasonable time by the semidefinite programming solver (here
reasonable means within 1000 seconds). For these instances, the value of α
happened to be known already.
The results are reported in Table 2, which follows the same format as Table 1. It shows the same behaviour as the results on random graphs. Namely, our
method always finds better solutions than the standard constraint programming
solver, in less time or within the time limit. This is not surprising, because the
edge density of these instances are exactly in the region in which our method is
supposed to behave best (with the exception of 1dc.64 and 1zc.128), as analyzed
in Section 6.1. Again, our method finds the best solutions at a low discrepancy.
Note that the instance 1et.64 shows the strength of the semidefinite relaxation
with respect to standard constraint programming. The difference in computation time to prove optimality is huge.

13

Table 2: Computational results on graphs arising from coding theory, with n
vertices and m edges. All times are in seconds. The time limit is set to 1000
seconds.
instance
name
1dc.64
1dc.128
1dc.256
1et.64
1et.128
1et.256
1tc.64
1tc.128
1tc.256
1tc.512
1zc.128

n
64
128
256
64
128
256
64
128
256
512
128

m
543
1471
3839
264
672
1664
192
512
1312
3264
2240

edge
density
0.27
0.18
0.12
0.13
0.08
0.05
0.10
0.06
0.04
0.02
0.28

α
10
16
30
18
28
50
20
38
63
110
18

α
10
≥ 16
≥ 26
18
≥ 28
≥ 46
≥ 20
≥ 37
≥ 58
≥ 100
≥ 18

CP
total
time
11.44
limit
limit
273.06
limit
limit
limit
limit
limit
limit
limit

backtracks
79519

2312832

α
10
16
30
18
≥ 28
≥ 50
20
38
≥ 63
≥ 110
≥ 18

best
discr
0
0
0
0
0
0
0
0
4
2
4

SDP + CP
sdp
total
time
time
5.08
5.09
49.95
49.98
882.21 882.33
1.07
1.08
11.22
limit
107.58
limit
0.78
0.79
8.14
8.18
72.75
limit
719.56
limit
129.86
limit

backtracks
0
0
0
0

0
0

Table 3: Computational results on graphs from the DIMACS benchmark set
for maximum clique problems, with n vertices and m edges. All times are in
seconds. The time limit is set to 1000 seconds.
instance
name
hamming6-2
hamming6-4
hamming8-2
johnson8-2-4
johnson8-4-4
johnson16-2-4
MANN a9
MANN a27
MANN a45
san200 0.9 1
san200 0.9 2
san200 0.9 3
sanr200 0.9

6.4

n
64
64
256
28
70
120
45
378
1035
200
200
200
200

m
192
1312
1024
168
560
1680
72
702
1980
1990
1990
1990
2037

edge
density
0.095
0.651
0.031
0.444
0.232
0.235
0.072
0.010
0.004
0.100
0.100
0.100
0.102

α
32
4
128
4
14
8
16
126
345
70
60
44
42

α
32
4
≥ 128
4
14
≥ 8
16
≥ 103
≥ 156
≥ 45
≥ 36
≥ 26
≥ 34

CP
total
backtime
tracks
20.22
140172
0.28
804
limit
0.05
255
15.05
100156
limit
162.81 1738506
limit
limit
limit
limit
limit
limit

α
32
4
128
4
14
8
16
≥ 125
≥ 338
70
60
44
≥ 41

best
discr
0
0
0
0
0
0
1
3
1
0
0
0
4

SDP + CP
sdp
total
time
time
0.68
0.69
27.29
28.10
45.16
45.55
0.35
0.35
4.82
4.83
43.29
43.32
0.17
82.46
70.29
limit
1047.06
limit
170.01 170.19
169.35 169.51
157.90 157.99
131.57
limit

backtracks
0
706
0
0
0
0
411104

0
0
0

Graphs from the DIMACS Benchmarks Set

Our final experiments are performed on a subset of the DIMACS benchmark set
for the maximum clique problem [25]. Although our method is not intended to
be competitive with the best heuristics and exact methods for maximum clique
problems, it is still interesting to see its performance on this standard benchmark
set. As pointed out in Section 5, we have transformed these maximum clique
problems to stable set problems on the complement graph.
The results are reported in Table 3, which again follows the same format as
Table 1. The choice for this particular subset of instances is made by the solvability of an instance by a semidefinite programming solver in reasonable time
(again, reasonable means 1000 seconds). For all instances with edge density
smaller than 0.24, our method outperforms the standard constraint programming approach. For higher densities however, the opposite holds. This is exactly

14

Table 4: A comparison of different methods on graphs from the DIMACS benchmark set for maximum clique problems, with n vertices and m edges. All times
are in seconds.
instance
edge
density
0.095
0.651
0.031
0.444
0.232
0.235
0.073
0.010
0.004
0.100
0.100
0.100
0.102

name
hamming6-2
hamming6-4
hamming8-2
johnson8-2-4
johnson8-4-4
johnson16-2-4
MANN a9
MANN a27
MANN a45
san200 0.9 1
san200 0.9 2
san200 0.9 3
sanr200 0.9

α
32
4
128
4
14
8
16
126
345
70
60
44
42

Östergård
total
α
time
32
0.01
4
0.01
128
0.04
16
0.01
14
0.01
8
0.27
16
0.01
> 10000
> 10000
70
0.27
60
4.28
> 10000
> 10000

α
32
4
128
4
14
8
16
126
≥ 345
70
60
44
42

Régin
total
time
0.00
0.00
0.00
0.00
0.00
11.40
0.00
55.44
> 43200
3.12
7.86
548.10
450.24

backtracks
17
42
65
14
140
250505
50
1258768
1040
6638
758545
541496

α
32
4
128
4
14
8
16
≥ 125
≥ 338
70
60
44
≥ 41

CP + SDP
total
backtime
tracks
0.69
0
28.10
706
45.55
0
0.35
0
4.83
0
43.32
0
82.46 411104
> 1000
> 1000
170.19
0
169.51
0
157.99
0
> 1000

what could be expected from the analysis of Section 6.1. A special treatment
has been given to instance MANN a45. We stopped the semidefinite programming solver at the time limit of 1000 seconds, and used its intermediate feasible
solution as if it were the optimal fractional solution. We then proceeded our algorithm for a couple of seconds more, to search for a solution up to discrepancy
1.
In Table 4 we compare our method with two methods that are specialized for
maximum clique problems. The first method was presented by Östergård [26],
and follows a branch-and-bound approach. The second method is a constraint
programming approach, using a special constraint for the maximum clique problem, with a corresponding propagation algorithm. This idea was introduced by
Fahle [27] and extended and improved by Régin [28]. Since all methods are performed on different machines, we need to identify a time ratio between them.
A machine comparison from SPEC4 shows that our times are comparable with
the times of Östergård. We have multiplied the times of Régin with 3, following
the time comparison made in [28]. In general, our method is outperformed by
the other two methods, although there is one instance on which our method
performs best (san200 0.9 3).

7

Conclusion and Future Work

We have presented a method to use semidefinite relaxations within constraint
programming. The fractional solution values of the relaxation serve as an indication for the corresponding constraint programming variables. Moreover,
the solution value of the relaxation is used as a bound for the corresponding
constraint programming objective function.
4 http://www.spec.org/

15

We have implemented our method to find the maximum stable set in a graph.
Experiments are performed on random weighted and unweighted graphs, structured graphs from coding theory, and on a subset of the DIMACS benchmarks
set for maximum clique problems. Computational results show that constraint
programming can greatly benefit from semidefinite programming. Indeed, the
solution to the semidefinite relaxations turn out to be very informative. Compared to a standard constraint programming approach, our method obtains far
better results. Specialized algorithms for the maximum clique problem however,
generally outperform our method.
The current work has investigated the possibility of exploiting semidefinite
relaxations in constraint programming. Possible future investigations include
the comparison of our method with methods that use linear relaxations, for
instance branch-and-cut algorithms. Moreover, one may investigate the effects
of strengthening the relaxation by adding redundant constraints. For instance,
for the stable set problem so-called clique-constraints (among others) can be
added to both the semidefinite and the linear relaxation. Finally, the proof of
optimality may be accelerated similar to a method presented in [1], by adding
so-called discrepancy constraints to the semidefinite or the linear relaxation,
and recompute the solution to the relaxation.

Acknowledgements
Many thanks to Michela Milano, Monique Laurent and Sebastian Brand for
fruitful discussions and helpful comments while writing (earlier drafts of) this
paper. Also thanks to the anonymous referees for useful comments.

References
[1] M. Milano and W.J. van Hoeve. Reduced cost-based ranking for generating promising subproblems. In P. van Hentenryck, editor, Eighth International Conference on the Principles and Practice of Constraint Programming (CP’02), volume 2470 of LNCS, pages 1–16. Springer Verlag, 2002.
[2] W.J. van Hoeve. A Hybrid Constraint Programming and Semidefinite Programming Approach for the Stable Set Problem. In F. Rossi, editor, Ninth
International Conference on Principles and Practice of Constraint Programming (CP’03), volume 2833 of LNCS, pages 407–421. Springer Verlag,
2003.
[3] F. Focacci, A. Lodi, and M. Milano. Exploiting relaxations in CP. In
M. Milano, editor, Constraint and Integer Programming: toward a unified
methodology, chapter 5. Kluwer Academic Publishers, 2004.
[4] M.X. Goemans and D.P. Williamson. Improved Approximation Algorithms
for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6):1115–1145, 1995.
16

[5] S. E. Karisch, F. Rendl, and J. Clausen. Solving graph bisection problems with semidefinite programming. INFORMS Journal on Computing,
12(3):177–191, 2000.
[6] K.R. Apt. Principles of Constraint Programming. Cambridge University
Press, 2003.
[7] W. D. Harvey and M. L. Ginsberg. Limited Discrepancy Search. In C. S.
Mellish, editor, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95); Vol. 1, pages 607–615, 1995.
[8] C. Helmberg. Semidefinite Programming website.
http://www-user.tu-chemnitz.de/∼helmberg/semidef.html.
[9] F. Alizadeh. The Semidefinite Programming Page.
http://new-rutcor.rutgers.edu/∼alizadeh/sdp.html.
[10] M. Goemans and F. Rendl. Combinatorial Optimization. In H. Wolkowicz,
R. Saigal, and L. Vandenberghe, editors, Handbook of Semidefinite Programming, pages 343–360. Kluwer, 2000.
[11] M. Laurent and F. Rendl. Semidefinite Programming and Integer Programming. In K.Aardal, G. Nemhauser, and R. Weismantel, editors, Discrete
Optimization, Handbooks in Operations Research and Management Science. Elsevier, 2004. Also available as Technical Report PNA-R0210, CWI,
Amsterdam.
[12] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. John Wiley & Sons, 1988.
[13] F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal on Optimization,
5(1):13–51, 1995.
[14] M. Laurent, S. Poljak, and F. Rendl. Connections between semidefinite
relaxations of the max-cut and stable set problems. Mathematical Programming, 77:225–246, 1997.
[15] P.M. Pardalos and J. Xue. The Maximum Clique Problem. SIAM Journal
of Global Optimization, 4:301–328, 1994.
[16] I.M. Bomze, M. Budinich, P.M. Pardalos, and M. Pelillo. The Maximum
Clique Problem. In D.-Z. Du and P.M. Pardalos, editors, Handbook of
Combinatorial Optimization, volume 4. Kluwer, 1999.
[17] C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982.
[18] L. Lovász. On the Shannon capacity of a graph. IEEE Transactions on
Information Theory, 25:1–7, 1979.
17

[19] G. Gruber and F. Rendl. Computational experience with stable set relaxations. SIAM Journal on Optimization, 13(4):1014–1028, 2003.
[20] ILOG. ILOG Solver 5.1, Reference Manual, 2001.
[21] B. Borchers. A C Library for Semidefinite Programming. Optimization
Methods and Software, 11(1):613–623, 1999.
http://www.nmt.edu/~borchers/csdp.html.
[22] R.C. Whaley, A. Petitet, and J.J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1–
2):3–35, 2001.
http://math-atlas.sourceforge.net/.
[23] E. Anderson, Z. Bai, C. Bischof, L.S. Blackford, J. Demmel, J.J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and
D. Sorensen. LAPACK Users’ Guide. SIAM, third edition, 1999.
http://www.netlib.org/lapack/.
[24] N.J.A. Sloane. Challenge Problems: Independent Sets in Graphs.
http://www.research.att.com/∼njas/doc/graphs.html.
[25] DIMACS. DIMACS maximum clique benchmark, 1993.
ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique.
[26] P.R.J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120:197–207, 2002.
[27] T. Fahle. Simple and Fast: Improving a Branch-And-Bound Algorithm
for Maximum Clique. In 10th Annual European Symposium on Algorithms
(ESA 2002), volume 2461 of LNCS, pages 485–498. Springer Verlag, 2002.
[28] J.-C. Régin. Using Constraint Programming to Solve the Maximum Clique
Problem. In F. Rossi, editor, Ninth International Conference on Principles
and Practice of Constraint Programming (CP’03), volume 2833 of LNCS,
pages 634–648. Springer Verlag, 2003.

18

