Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming.
In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-heuristics such as evolutionary algorithms. Their performance is compared for 115 problem instances. All methods are capable of producing high quality solutions in short time. In particular, the greedy heuristic is able to find near optimum solutions a few percent below the best-known solutions, and the local search procedures are sufficient to find the best-known solutions of all problem instances with n  100. The k-opt local searches even find the best-known solutions for all problems of size n  250 and for 11 out of 15 instances of size n &equals; 500 in all runs. For larger problems (n &equals; 500, 1000, 2500), the heuristics appear to be capable of finding near optimum solutions quickly. Therefore, the proposed heuristicsespecially the k-opt local searchoffer a great potential for the incorporation in more sophisticated meta-heuristics.
is given, and a binary vector of length n is searched, such that the quantity
is maximized. This problem is also known as the (unconstrained) quadratic bivalent programming
problem, the (unconstrained) quadratic zero{one programming problem, or the (uncon-
strained) quadratic (pseudo-) Boolean programming problem (Beasley, 1998).
The BQP is known to be NP-hard (Garey & Johnson, 1979) and has a large number
of applications, for example in capital budgeting and nancial analysis problems (Laughunn,
1970; McBride & Yormark, 1980), CAD problems (Krarup & Pruzan, 1978), tra-c message
management problems (Gallo et al., 1980), machine scheduling (Alidaee et al., 1994), and
molecular conformation (Phillips & Rosen, 1994). Furthermore, several other combinatorial
optimization problems can be formulated as a BQP, such as the maximum cut problem, the
maximum clique problem, the maximum vertex packing problem and the maximum independent
set problem (Ivanescu, 1965; Pardalos & Rodgers, 1992; Pardalos & Xue, 1994).
Several exact methods have been developed to solve the BQP (Pardalos & Rodgers, 1990;
Barahona et al., 1989; Billionnet & Sutter, 1994; Helmberg & Rendl, 1998), but due to the
computational complexity of the problem, heuristics have been proposed recently to nd solutions
to large problem instances, including tabu search (Beasley, 1998; Glover et al., 1998b;
Glover et al., 1998a), scatter search (Amini et al., 1999), simulated annealing (Beasley, 1998;
Katayama & Narihisa, 1999) and evolutionary algorithms (Lodi et al., 1998; Merz & Freisleben,
1999b).
In this paper, a greedy heuristic and two local search algorithms for the unconstrained
binary quadratic programming problem (BQP) are presented. The greedy heuristic constructs
a feasible solution in n steps where n denotes the problem size, i.e. the number of elements of
a solution. In each step, the greedy heuristic selects an element and a value for it by making
a most favorable choice. Additionally, a randomized greedy heuristic is described in which
random components are added to the deterministic greedy heuristic.
The local search heuristics iteratively search a better solution in the neighborhood of the
current solution until no better solution exists and thus a local optimum is reached. The
neighborhood of the rst local search algorithm {the 1-opt local search { is dened by the
solutions that can be reached by changing a single element in the current solution. The second
local search is a k-opt local search where k elements in the solution are changed simultaneously.
Due to the computational complexity, only a small fraction of the k-opt neighborhood is searched
by the local search procedure.
The algorithms are tested on a set of 115 problem instances of the BQP. The experiments
show that the local search heuristics are able to nd optimum or best-known solutions for
instances with a problem size of up to 100 easily. The multi{start k-opt local search is capable
of nding best-known solutions in all runs for all problem instances studied with a problem size
less or equal to 250 and for 11 out of 15 instances of size 500.
For larger instances the algorithms are shown to nd near optimum
solutions in 10 to 60 seconds on a state-of-the-art workstation: in most cases, the multi{start
randomized greedy heuristic, the multi{start 1-opt local search, and the multi{start k-opt local
search nd solutions within 1%, 0.5%, and 0.1% below the best-known solution, respectively.
The paper is organized as follows. In section 1, the BQP is described in more detail. Section
2 describes the greedy and local search heuristics for the BQP. The results obtained from various
experiments conducted with these algorithms are discussed in section 3. Section 4 concludes
the paper and outlines areas of future research.
1 The Binary Quadratic Programming Problem
Throughout this paper, a solution vector x of the BQP is a boolean vector of length n:
. Thus, the solution space X of the BQP is of size 2 n ; it grows
exponentially with n.
The density of the matrix Q is sometimes used to characterize a BQP instance. The density
dens(Q) is dened as the number of non-zero entries divided by the number of total entries in
the matrix Q. Thus, the density varies between 0 and 1.
To demonstrate the relevance in various scenarios, some special cases and a generalization
of the BQP are described in the following.
1.1 Special Cases of the BQP
The BQP has been shown to be a generalization of other combinatorial optimization problems.
For example, the maximum clique problem and the maximum independent set problem are
special cases of the BQP. Let E) be an undirected graph and E) be the
complement graph of G, where
Eg. Furthermore, let
be the adjacency matrix of G, I denote the identity matrix, and T
g. Then, the maximum clique problem is
min
If x  solves equation (2), the maximum clique of G is dened as
Similarly, the maximum independent set problem is
min
If x  solves equation (3), the maximum independent set of G is dened as
In the maximum cut problem the objective function
has to be maximized, where w ij denotes the weight of the edge (i; in the graph
which the maximum cut is desired. The maximum cut problem can be formulated
as a 0/1 quadratic programming problem by assigning:
The maximum cut size c(x  ) is equal to the objective f(x  ) of the corresponding BQP, and the
cut itself is
1g.
Another application of the BQP arises in condensed matter physics. The calculation of
ground states in Ising Spin Glasses is a combinatorial optimization problem in which a conguration
of the spins with minimum energy is searched. The energy of an ising spin glass, in
which the spins lie on a two dimensional grid, is given by the Hamiltonian:
denotes the interaction between site i and j on the grid. By setting
the solution of the BQP yields a conguration with minimum energy, where s
and
1.2 A Generalization of the BQP
There is a close relation between binary quadratic programming and NK-landscapes as dened
by Kauman (Kauman & Levin, 1987) to model gene interaction in genetic evolution. This
relation is shown in the following. The objective function of the BQP can be decomposed into
functions. The tness of a BQP solution can thus be rewritten as a sum of functions for each
site, called the tness contributions f i of component i in the bit vector:
Similar to the NK-landscapes dened in (Kauman & Levin, 1987), the tness contribution
f i of a site i depends on the gene value x i and of k(i) other genes x
. While for
NK-landscapes is constant for all i, in the BQP k(i) is dened as the number of
non-zero entries in the i-th column of matrix Q. The mean k of the k(i) is given by
dens(Q). The BQP can be viewed as a special class of NK-landscapes with a special tness
contribution function f i . Alternatively, NK landscapes can be seen as a family of more general
binary programming problems.
Heuristics for the BQP
Heuristics can be divided into construction heuristics and improvement heuristics. The former
construct feasible solutions for a given optimization problem from scratch, while the latter take
a feasible solution as their input and try to nd better solutions by stepwise transformations.
Both types of heuristics can be implemented e-ciently and are often capable of producing
near optimum solutions for combinatorial optimization problems. If, however, the results obtained
are not su-cient, the algorithms can be combined or incorporated into meta{heuristics
such as memetic algorithms (Moscato, 1989), as for example shown in (Merz & Freisleben,
2000) for the graph bipartitioning problem: A dierential greedy heuristic (Battiti & Bertossi,
1998) combined with Kernighan-Lin local search (Kernighan & Lin, 1972) has been shown to
be su-cient for structured problems of small or medium sizes. If larger problems have to be
solved or the problems are unstructured, a memetic algorithm { a genetic algorithm incorporating
the local search and the greedy heuristic { has been shown to be more eective. Since
greedy and local search heuristics are important (components of) algorithms for combinatorial
optimization problems, corresponding approaches for the BQP are desired. Thus, greedy
and local search algorithms for the BQP are described in the following. To the best of our
knowledge, our proposals are the rst algorithms of this kind for the BQP.
2.1 Greedy Heuristics
Greedy algorithms are intuitive heuristics in which greedy choices are made to achieve a certain
goal. In combinatorial optimization, a solution to a given problem is searched which maximizes
or minimizes an objective function. Greedy heuristics are constructive heuristics since they
construct feasible solutions for optimization problems from scratch by making the most favorable
choice in each step of construction. By adding an element to the (partial) solution which
promises to deliver the highest gain, the heuristic acts as a \greedy constructor".
2.1.1 A Simple Greedy Algorithm
In the BQP, a solution is constructed by assigning a binary value to an element in the solution
vector x: a zero or a one. The general outline of the greedy algorithm is provided in Figure 1.
In each step, the heuristic searches for an element k in the solution vector and a value l to
procedure Greedy(x 2 X): X;
begin
repeat
nd k; l with g l
return x;

Figure

1: A Greedy Heuristic for the BQP
assign to it so that a gain function g l
k is maximized. Afterwards, the value l is assigned to the
vector component x k .
To nd an appropriate gain function, we modify the problem by adding a third state: Let
be a vector in which each component y i can have three values 0, 1, and
1. Starting with a vector ^
all i, the greedy heuristic can be viewed as a
transformation algorithm that transforms ^
y into a vector x for which x i 2 f0; 1g for all i and
thus x 2 X. The objective of the solution ^
y is
Let ~
be a vector that is equal to y 2 Y except for component y k . Then
Hence, the gain for changing y k from 0:5 to 0 (denoted g 0
k ) can be dened
as
Using this formula, the greedy heuristic as displayed in Figure 1 has a runtime complexity
of O(n 3 ) since the calculation of all g i takes O(n 2 ) and this has to be done n times before
the algorithm terminates. Thus, the greedy heuristic has an expected running time equal
to an algorithm that calculates the objective function f(x) for n solutions. However, the
greedy algorithm can be implemented more e-ciently. If the matrix Q is not stored in a
two dimensional array, but instead, for each i in ng a list of j's for which q ij 6= 0 is
maintained, the running time is reduced considerably for instances with a low density. To
reduce the running time for nding a choice with a highest gain, the following formula can be
used to calculate the new gain g i after y k has been set to 0 or 1:
1q ik if y
q ik otherwise and g 0
1q ik if y
Thus, once the gains g i have been calculated, they can be e-ciently updated after the
component y k has been set. Since the gains g only change for those i with q ik 6= 0, the running
time for updating the gains has a complexity in O(n). In gure 2, the pseudo code of the fast
greedy heuristic is provided. The running time for the improved heuristic is in O(n 2 ) since the
running time for nding the maximum gain g 0
k and g 1
k is in O(n) and has to be performed n
times to construct a feasible solution. Thus, the greedy heuristic has the same computational
complexity as an algorithm calculating f(x) for a single solution. The running time behavior
of the greedy heuristic can be improved even further if additional data structures are used
to nd the maximum gain in shorter than O(n) time. However, this has no in
uence on the
computational complexity of the algorithm since the time for the initial calculation of the gains
dominates over the times for the greedy choices.
procedure Greedy(x 2 X): X;
begin
for to n do x
calculate gains g i for all i in
repeat
nd k 0 with g 0
nd
then
else
endif
update gains g i for all i 2 C;
return x;

Figure

2: A Greedy Heuristic for the BQP
2.1.2 A Randomized Greedy Algorithm
The greedy heuristic described above is deterministic, since it always produces the same solution
for a given problem instance. Often it is desired that a construction heuristic produces many
dierent solutions, for example in hybrid algorithms. The above procedure can be randomized
as follows.
By making the rst choice randomly, i.e. selecting k and l randomly and setting x
in the rst step, a random component is incorporated. Furthermore, the deterministic choice
among x k 0
and x k 1
can be replaced by a random choice proportional to the gains g 0
and
is set to 0 with probability g 0
and x k 1
is set to 1 with probability
. The pseudo
code of the randomized greedy heuristic is provided in Figure 3.
2.2 Local Search
Local search (LS) algorithms are improvement heuristics that search in the neighborhood of
the current solution for a better one until no further improvement can be made, i.e. there is
no better solution in the neighborhood of the current solution. Local search algorithms can be
categorized by the neighborhoods they consider. For example, the neighborhood of a solution
represented by a binary vector can be dened by the solutions that can be obtained by
ipping
a single or multiple components in the binary vector simultaneously.
procedure
begin
for to n do x
calculate gains g i for all i in
Select k; l randomly and set x k := l;
repeat
nd k 0 with g 0
nd
set
if randomNumber[0,1]< p then
else
endif
update gains g i for all i 2 C;
return x;

Figure

3: A Randomized Greedy Heuristic for the BQP
2.2.1 1-opt Local Search
The simplest form of local search for the BQP is the 1-opt local search: In each step, a new
solution with a higher tness in the neighborhood of the current solution is searched. The
neighborhood of the current solution is dened by the set of solutions that can be reached
by
ipping a single bit. Hence, the 1-opt neighborhood contains all solutions with a hamming
distance of 1 to the current solution. In our implementation, we search for the solution with the
highest tness, i.e. we search for a
ip with the highest associated gain in tness new f old ).
The gain g k of
ipping bit k in the current solution can be calculated in linear time using the
with
The local search algorithm is given in pseudo code in Fig. 4. A straightforward implementation
of the 1-opt local search displayed in the gure has a running time of O(n 2 ) per iteration.
procedure
begin
repeat
nd k with
if
until
return x;

Figure

4: 1-opt Local Search
Analogous to the greedy heuristic, the e-ciency of the algorithm can be increased considerably.
The gains g i do not have to be recalculated each time. Instead, it is su-cient to calculate the
dierence of the gains g i . Assuming that all g i for a BQP solution have been calculated and
the bit k is
ipped, the new gains g 0
i can be calculated e-ciently by the formula:
Thus, the update of the gains can be performed in linear time. This property has also been
used in (Glover et al., 1998a) to speed up tabu search for the BQP. Furthermore, only the gains
have to be updated. The fast 1-opt local search is displayed in Figure 5. The
procedure
begin
calculate gains g i for all i in
repeat
nd k with
if
update gains
endif
until
return x;

Figure

5: Fast 1{opt Local Search for the BQP
running time of this algorithm is O(n) per iteration. The initialization of the gains is in O(n 2 ).
2.2.2 k-opt Local Search
The k-opt neighborhood N k opt of a binary vector of length n is dened by the binary vectors
that can be reached by
ipping one up to k bits in the vectors simultaneously. Hence, the
neighborhood N k opt denotes the hamming distance between
bit vectors) grows exponentially with k: jN k opt
Since it is computationally too expensive to search the complete k-opt neighborhood, Lin
and Kernighan have proposed heuristics for the traveling salesman problem (TSP) and the
graph partitioning problem that e-ciently search a small fraction of the k-opt neighborhood.
These algorithms, known as the Lin-Kernighan algorithm for the TSP (Lin & Kernighan, 1973),
and the Kernighan-Lin algorithm for graph partitioning (Kernighan & Lin, 1972), belong to the
best available heuristics for these two combinatorial optimization problems. In the following, a
local search algorithm for the BQP is presented that is based on the ideas of Lin and Kernighan.
The basic idea of the heuristic is to nd a solution by
ipping a variable number of k bits in
the solution vector per iteration. In each step, a sequence of n solutions is generated by
ipping
the bit with the highest associated gain. Analogous to the 1-opt local search procedure, a vector
of gains is maintained and updated according to equation (15) after each
ip. Furthermore, a
candidate set is used to assure that each bit is
ipped exactly once. The best solution in the
sequence is accepted as the new solution for the next iteration. Thus, in each iteration of the
algorithm a variable number of bits are
ipped to nd a new solution in the neighborhood of
the current solution. The pseudo code of the k-opt local search is presented in Figure 6.
The runtime complexity for the initialization is in O(n 2 ) and the running time per iteration
is also of complexity O(n 2 ).
The reduce the running time, the termination condition of the inner repeat-loop can be
modied so that the loop is terminated if there were no new x best for more than m iterations.
Thus, the resulting fast k-opt procedure has a shorter running time for m  n than the k-opt
procedure described before.
Performance Evaluation
To evaluate the performance of the algorithms, we conducted several experiments on all 105
problem instances contained in ORLIB (Beasley, 1990). The sets glov-a, glov-b, glov-c and
glov-d contain the instances of type a through d described in (Glover et al., 1998b). The set
glov200 (glov500) consists of ve problem instances of size and is denoted
as type e (f) in (Glover et al., 1998b). The six sets described in (Beasley, 1998) with a density
procedure
begin
calculate gains g i for all i in
repeat
repeat
nd j with
G;
x best := x;
endif
update gains g i for all
x := x best ;
else
endif
return x;

Figure

for the BQP
dens(Q) of 0.1 and n 2 f50; 100; 250; 500; 1000; 2500g consist of 10 instances each. They are
denoted beashni. In the experiments, the instances of type g used in (Glover et al., 1998b;
Amini et al., 1999) with between 0:1 and 1 were also considered. They
are denoted as kb-g.
To nd a good parameter value for m in the k-opt procedure, experiments were performed
for beas1000 and beas2500. It appeared that is a good trade-o between running time
and solution quality. For larger values, the running time increased considerably with only small
changes in solution quality. Therefore chosen in all subsequent k-opt local search
experiments.
In the experiments, the performance of the randomized greedy algorithm, the 1-opt local
search applied to randomly generated solutions, the fast k-opt local search applied to randomly
generated solutions, and the combination of the randomized greedy heuristic and fast k-opt
local search was investigated. To enable a fair comparison, all algorithms implemented in C++
were run under the same conditions on a Pentium II PC (300 MHz) under the operating system
Solaris 2.6.2060100140180
time
in
ms
density of Q
greedy
1-opt
k-opt
time
in
ms
Problem size n
greedy
1-opt
k-opt
greedy+k-opt

Figure

7: Average running times of greedy and local search heuristics for the BQP
In a rst experiment, the average running times of the four algorithms and the average
solution quality was studied. In Figure 7, the average running times (in milliseconds) of 10000
runs of the algorithms are provided. In the left plot, the running times are provided for the
ve instances of the set glov500 with and a density dens(Q) contained between 0.1
and 1. As expected, the running time of the algorithms grows linearly with the density of
the matrix Q. The running times of the combination of the randomized greedy heuristic and
k-opt local search are slightly lower than the running times of the k-opt local search applied
to randomly generated solutions, since the number of iterations of the local search is reduced
when it is applied to solutions produced by the greedy heuristic. In the right plot, the running
times are provided for the six sets beas50 to beas2500. For all algorithms, the running times
grow quadratically with n. The k-opt algorithms appear to be 2.5 times slower than the 1-opt
algorithm, and for large n, the greedy heuristic is slower than 1-opt. Thus, the number of
iterations of the 1-opt procedure grows at most linearly with the problem size for the instances
studied.
The average solution quality of the approaches is displayed in Table 1. The solution quality
is measured by the average percentage excess (avg) (100  (1:0 f(x)=f best )) over the best-known
solution for a set of up to 10 instances, and the standard deviation (sdev) is also provided for
each algorithm. The greedy heuristic shows a better average performance on six of the sets
than the 1-opt local search, while the latter performs better on the remaining six. The k-opt
heuristic performs considerably better than the greedy and 1-opt heuristic: with one exception,
the average percentage excess is below 1%. However, the combination of greedy and k-opt local

Table

1: Average solution quality of greedy and local search heuristics for the BQP
instances greedy 1-opt k-opt greedy-k-opt
avg sdev avg sdev avg sdev avg sdev
glov-d 2.81 % 0.42 2.71 % 0.73 0.71 % 0.35 0.42 % 0.27
search performs best on all but one instance with respect to the average quality of the solutions.

Table

2: Time to reach the optimum
instances 1-opt k-opt greedy-k-opt
glov-d 52.11
beas250 { { { 20.00 0.09 0.77 10.30
In a second experiment, the heuristics were repeatedly applied (multi{start) to show their
ability to reach the optimum or best-known solution. Each of the heuristics was started multiple
times and the best solution found was returned. For each instance, runs were performed for
each algorithm, and the times to reach the best-known solutions were recorded. In Table 2,
the times for the algorithms that were capable of nding the optimum in all 30 out of runs
for all instances in a set are displayed. The average number of repetitions needed (rep), the
average time in seconds (avg t) to reach the best-known solution, as well as the maximum time
in seconds (max t) to reach the best-known solution is provided. For problems up to a size of
200, the 1-opt local search is capable of nding the optimum in less than 2 seconds. For the
set glov200 the average number of local searches is about 217. The k-opt heuristic needs only
about 13 local searches on the average to nd the best-known solutions for the instances of this
set. Both k-opt algorithms perform better on the instances up to need less than
0.23 seconds to nd the best-known solutions and are able to nd the best-known solutions of
all the instances of the set beas250. On this set, the greedy k-opt combination performs slightly
better than the k-opt on random solutions: less than 0.53 seconds are needed.

Table

3: Comparison of greedy, 1-opt, k-opt, and greedy-k-opt on large BQP instances
instances greedy 1-opt k-opt greedy-k-opt time
rep avg rep avg rep avg rep avg (sec)
The results show that for small instances (up to simple local search is su-cient
to nd best-known solutions quickly. The more challenging problems have a size of
higher. The third experiment concentrated on these instances. To enable a fair comparison, the
four algorithms were repeatedly applied until a predened time limit was reached. Once again,
runs were performed for each instance. The results are summarized in Table 3. For each
instance and algorithm, the average number of repetitions (rep), and the average percentage
excess (avg) is given. The time limit in seconds (time) used is provided in the last column of
the table.
The greedy heuristic shows to be inferior to the 1-opt local search: The average percentage
excess for the set beas1000 and beas2500 is between 0.727% and 1.170% in case of the greedy
heuristic; for the 1-opt local search the results are between 0.216% and 0.543%. The algorithms
based on k-opt are considerably better. The worst performance lies 0.128% below the optimum
for the beas instances. The kb-g instances appear to be harder; within a time limit of
the average solution quality lies between 0.012 % and 0.489 %. A preference to one of the k-opt
based algorithms can not be given, since their performance does not dier signicantly. Both
are able to nd the best-known solution for the problems glov500-1 and glov500-2 in all
but not for the other problems with and a density dens(Q) greater 0.25. This indicates
that problems with high densities are slightly harder for the k-opt local search. However, as
the results on the kb-g instances show, the average solution quality is not a simple function of
the density: the average percentage access for the problem with density 0.8 (kb-g08) is better
than for the problems with density 0.4 and 0.7 (kb-g04 and kb-g07).
In comparison to the tabu search and simulated annealing for the BQP proposed in (Beasley,
1998), the best found solutions obtained with the greedy heuristic and k-opt local search for
the 10 problems of size 2500 are in 7 out of 10 cases better than the best found solutions
reported in (Beasley, 1998). For tabu search and simulated annealing, the running times on a
Silicon Graphics Indigo workstation (R4000, 100MHz) are between 12721 and 51873 seconds
compared to the 60 seconds for the local search on a Pentium II 300 MHz PC. Thus, the
results produced by the k-opt local search appear to be superior or at least competitive to the
other approaches in solution quality per time. However, a comparison of the methods under
the same conditions (computing hardware, operating system, programming language, coding
is required to support this claim.
More sophisticated algorithms, however, are expected to produce better solutions: the tabu
search utilizing critical event memory (Glover et al., 1998a) found the best-known solution for
7 out of the 10 instances of set kb-g, in a CPU time of four minutes on a Pentium 200 PC. The
scatter search approach proposed in (Amini et al., 1999) found the best-known solutions of all
problems in this set, but no CPU times were reported. The heuristics proposed in this paper
are not intended to be competitive with these approaches. Instead, they have been developed
with the idea of building powerful meta-heuristics called memetic algorithms (Moscato, 1999;
{ evolutionary algorithms incoporating greedy heuristics and local
search.
Conclusions
In this paper, a randomized greedy heuristic and two local search algorithms based on the
1-opt and a k-opt neighborhood for the BQP have been proposed. The runtime behavior
and the average performance of these heuristics has been investigated in experiments on 115
problem instances. Furthermore, four algorithms based on these heuristics have been studied:
the multi{start randomized greedy algorithm, the multi{start 1-opt local search on randomly
generated solutions, the multi{start k-opt local search on randomly generated solutions, and
the multi{start k-opt local search on solutions generated by the randomized greedy heuristic.
The results indicate that multi{start 1-opt local search is able to nd best-known solutions of
the studied instances up to a size of n = 100 in all runs, and multi{start k-opt local search is
capable of nding the best-known solutions in all runs for all studied instances up to
Furthermore, for 11 out of 15 problem instances of size the best-known solution was
found in all runs with multi{start k-opt LS.
Applied to larger instances (n > 500), the multi{start randomized greedy heuristic produces
solutions less than 1% below the best-known solutions in most cases, the multi{start 1-opt local
search solutions below 0.5% in most cases and the multi{start k-opt algorithms solutions less
than 0.5% below the best-known solution in most cases in a CPU time limit of 10 seconds up to
a minute on a state-of-the-art workstation. Thus, the proposed k-opt local search appears to be
highly eective, and the additional coding eort required in comparison to the 1-opt heuristic
is denitely justied.
Both greedy and local search heuristics are well suited as components for meta{heuristics
since their average running time is below 700 milliseconds even for large problems of size
best-known solutions are desired for large problems, the incorporation of the
heuristics in genetic algorithms appears to be a promising approach (Merz & Freisleben, 1999b).
Further studies have shown that the combination of evolutionary algorithms and k-opt local
are highly eective applied to large problem instances (n  500) (Katayama & Narihisa, 2000;
Merz, 2000).
There are several areas of future research. First, the implementation specic parameter m of
the k-opt local search should be studied in more detail; an interesting question is whether there
is an instance independent optimum value for the parameter or whether the parameter has to
be tuned for each instance separately. Second, there may be instances for which the greedy
heuristic performs better than local search, as shown for the graph bipartitioning problem
(Merz & Freisleben, 2000). Additional experiments are necessary to support this claim. Third,
a comparison of the k-opt local search with the recently proposed tabu search algorithms for the
BQP (Beasley, 1998) is another interesting are of study. Finally, the heuristics described in this
paper may be extended to NK landscapes, a generalized unconstrained binary programming
problem. In fact, we are currently working on a greedy and a k-opt heuristic for NK landscapes.
Initial experiments indicate that both heuristics are highly e-cient.



--R


A Scatter Search Approach to Unconstrained Quadratic Binary Programs.





Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem.
Minimization of a Quadratic Pseudo-Boolean Function
European Journal of Operational Research

Quadratic Knapsack Problems.
Computers and Intractability: A Guide to the Theory of NP-Completeness


Solving Quadratic (0

Performance of Simulated Annealing-based Heuristic for the Unconstrained Binary Quadratic Programming Problem
Solving Large Binary Quadratic Programming Problems by E



Quadratic Binary Programming.

An Evolutionary Heuristic for Quadratic 0-1 Programming
An Implicit Enumeration Algorithm for Quadratic Integer Programming.
Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and E




Fitness Landscapes
On Evolution
Memetic Algorithms: A Short Introduction.
Computational Aspects of a Branch and Bound Algorithm for Unconstrained Quadratic Zero-One Programming
A Branch and Bound Algorithm for the Maximum Clique Problem.

A Quadratic Assignment Formulation for the Molecular Conformation Problem.
--TR

--CTR
Kengo Katayama , Akihiro Hamamoto , Hiroyuki Narihisa, Solving the maximum clique problem by k-opt local search, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
Patrick E. Meyer , Kevin Kontos , Frederic Lafitte , Gianluca Bontempi, Information-theoretic inference of large transcriptional regulatory networks, EURASIP Journal on Bioinformatics and Systems Biology, v.2007 n.1, p.8-8, January 2007
Kengo Katayama , Akihiro Hamamoto , Hiroyuki Narihisa, An effective local search for the maximum clique problem, Information Processing Letters, v.95 n.5, p.503-511, 15 September 2005
Peter Merz, Advanced fitness landscape analysis and the performance of memetic algorithms, Evolutionary Computation, v.12 n.3, p.303-325, September 2004
local search;greedy heuristics;unconstrained quadratic binary programming