Solving NP-Complete Problems by Harmony Search - Music-Inspired Harmony Search Algorithm: Theory and Applications - page 52

The HS was also applied to a TSP-like NP-hard generalized orienteering problem
(GOP) which is to find the utmost route under the total distance limit while maximiz-
ing multiple goals. Here, GOP is a variant of an orienteering problem (OP) which is
used to model many practical problems.
Another problem which is considered in this chapter is a school bus routing problem
which is a multi-objective problem with a goal to minimize both the number of operat-
ing buses and the travel time of all buses, with two major constraints (bus capacity and
time window). This kind of problem has many applications such as inventory routing,
customer or vehicle assignment, production scheduling, and postal delivery or school
bus routing. The HS algorithm could find global optimum within far less function
evaluations than total enumeration.
The advent of various real-time multimedia applications in high-speed networks
creates a need for quality of service (QoS) based multicast routing. Two important
QoS constraints are bandwidth constraint and end-to-end delay constraint. The QoS
based multicast routing problem is a known NP-complete problem that depends on (1)
bounded end-to-end delay and link bandwidth along the paths from the source to each
destination, and (2) minimum cost of the multicast tree. This chapter considers the
application of HS in multicast routing to generate multicast trees with minimum cost
satisfying the bandwidth and delay constraint.
Finally, HS is applied to document clustering which has a crucial role in organizing
information and search engine results, enhancing web crawling, and information re-
trieval or filtering. Since a clustering problem has NP-complete nature, the larger the
size of the problem, the harder it is to find the optimal solution and the longer it is to
reach a reasonable result. So it is reasonable to model a clustering problem as an op-
timization and apply metaheuristic algorithms such as HS.

2 Sudoku Puzzle

Sudoku, which is Japanese term meaning 'one-digit number,' is the new craze in logic
puzzles. The Sudoku puzzle consists of 9×9 grids and 3×3 blocks for a total of 81 cells.
Each puzzle, which has a unique solution, has some cells that already have given-
numbers. The objective of the puzzle is to fill in the remaining cells with the numbers 1
through 9 so that every row, column, and 3×3 submatrix has a sum total of 45.

2.1 Problem Formulation for Sudoku Puzzles

The Sudoku puzzle could be formulated as a binary integer programming for general
n n × matrix of Sudoku con-

tains the integer k , and otherwise equal to zero. The formulation is as follows:
Minimize 0 T x (1)

n × puzzles. Let x equal one if element of the n

( i , j )

ijk

s.t.

n

∑
=

x = 1 1 ≤ j , k ≤ n (2)

ijk

i 1