Read an Excerpt

Stochastic Local Search

Foundations and Applications

Elsevier Science

Excerpt

CHAPTER 1

Introduction

This introductory chapter provides the background and motivation for studying stochastic local search algorithms for combinatorial problems. We start with an introduction to combinatorial problems and present SAT, the satisfiability problem in propositional logic, as well as TSP, the travelling salesman problem, as the central problems used for illustrative purposes throughout the first part of this book. This is followed by a short introduction to computational complexity. Next, we discuss and compare various fundamental search paradigms, including the concepts of systematic and local search, after which we formally define and discuss the notion of stochastic local search, one of the practically most important and successful approaches for solving hard combinatorial problems.

1.1 Combinatorial Problems

Combinatorial problems arise in many areas of computer science and other disciplines in which computational methods are applied, such as artificial intelligence, operations research, bioinformatics and electronic commerce. Prominent examples are tasks such as finding shortest or cheapest round trips in graphs, finding models of propositional formulae or determining the 3D-structure of proteins. Other well-known combinatorial problems are encountered in planning, scheduling, time-tabling, resource allocation, code design, hardware design and genome sequencing. These problems typically involve finding groupings, orderings or assignments of a discrete, finite set of objects that satisfy certain conditions or constraints. Combinations of these solution components form the potential solutions of a combinatorial problem. A scheduling problem, for instance, can be seen as an assignment problem in which the solution components are the events to be scheduled, and the values assigned to events correspond to the time at which these occur. This way, typically a huge number of candidate solutions can be obtained; for most combinatorial optimisation problems, the space of potential solutions for a given problem instance is at least exponential in the size of that instance.

Problems and Solutions

At this point, it is useful to clarify the distinction between problems and problem instances. In this book, by 'problem', we mean abstract problems (sometimes also called problem classes), such as 'for any given set of points in the Euclidian plane, find the shortest round trip connecting these points'. In this example, an instance of the problem would be to find the shortest round trip for a specific set of points in the plane. The solution of such a problem instance would be a specific shortest round trip connecting the given set of points. The solution of the abstract problem, however, is an algorithm that, given a problem instance, determines a solution for that instance. Generally, problems can be defined as sets of problem instances, where each instance is a pair of input data and solution data. This is an elegant mathematical formalisation; however, in this book we will define problems using a slightly less formal, but more intuitive (yet precise), representation.

For instances of combinatorial problems, we draw an important distinction between candidate solutions and solutions. Candidate solutions are potential solutions that may possibly be encountered during an attempt to solve the given problem instance; but unlike solutions, they may not satisfy all the conditions from the problem definition. For our shortest round trip example, typically any valid round trip connecting the given set of points, regardless of length, would be a candidate solution, while only those candidate round trips with minimal length would qualify as solutions. It should be noted that while the definition of any combinatorial problem states clearly what is considered a solution for an instance of this problem, the notion of candidate solution is not always uniquely determined by the problem definition, but can already reflect a particular approach for solving the problem. As an example, consider the variant of the shortest round trip problem in which we are only interested in trips that visit each given point exactly once. In this case, candidate solutions could be either arbitrary round trips which do not necessarily respect this additional condition, or the notion of candidate solution could be restricted to round trips that visit no point more than once.

Decision Problems

Many combinatorial problems can be naturally characterised as decision problems: for these, the solutions of a given instance are specified by a set of logical conditions. As an example of a combinatorial decision problem, consider the Graph Colouring Problem: given a graph G and a number of colours, find an assignment of colours to the vertices of G such that two vertices that are connected by an edge are never assigned the same colour. Other prominent combinatorial decision problems include finding satisfying truth assignments for a given propositional formula (the Propositional Satisfiability Problem, SAT, which we revisit in more detail in Section 1.2) or scheduling a series of events such that a given set of precedence constraints is satisfied. For any decision problem, we distinguish two variants:

the search variant, where, given a problem instance, the objective is to find a solution (or to determine that no solution exists);

the decision variant, in which for a given problem instance, one wants to answer the question whether or not a solution exists.

These variants are closely related because algorithms solving the search variant can always be used to solve the decision variant. Interestingly, for many combinatorial decision problems, the converse also holds: algorithms for the decision variant of a problem can be used for finding actual solutions.

Optimisation Problems

Many practically relevant combinatorial problems are optimisation problems rather than decision problems. Optimisation problems can be seen as generalisations of decision problems, where the solutions are additionally evaluated by an objective function and the goal is to find solutions with optimal objective function values. The objective function is often defined on candidate solutions as well as on solutions; the objective function value of a given candidate solution (or solution) is also called its solution quality. For the Graph Colouring Problem mentioned previously, a natural optimisation variant exists, where a variable number of colours is used and the goal is, given a graph, to find a colouring of its vertices, using only a minimal (rather than a fixed) number of colours.

Any combinatorial optimisation problem can be stated as a minimisation problem or as a maximisation problem, depending on whether the given objective function is to be minimised or maximised. Often, one of the two formulations is more natural, but algorithmically, minimisation and maximisation problems are treated equivalently. In this book, for uniformity and formal convenience, we generally formulate optimisation problems as minimisation problems. For each combinatorial optimisation problem, we distinguish two variants:

the search variant: given a problem instance, find a solution with minimal (or maximal, respectively) objective function value;

the evaluation variant: given a problem instance, find the optimal objective function value (i.e., the solution quality of an optimal solution).

Clearly, the search variant is the more general of these, since with the knowledge of an optimal solution, the evaluation variant can be solved trivially. Additionally, for each optimisation problem, we can define:

associated decision problems: given a problem instance and a fixed solution quality bound b, find a solution with an objective function value smaller than or equal to b (for minimisation problems; greater than or equal to b for maximisation problems) or determine that no such solution exists.

Many combinatorial optimisation problems are defined based on an objective function as well as on logical conditions. In this case, candidate solutions satisfying the logical conditions are called feasible or valid, and among those, optimal solutions can be distinguished based on their objective function value. While the use of logical conditions in addition to an objective function often leads to more natural formulations of a combinatorial optimisation problem, it should be noted that the logical conditions can always be integrated into the objective function in such a way that the feasible candidate solutions correspond to the solutions of an associated decision problem (i.e., to candidate solutions with bounded solution quality).

As we will see throughout this book, many algorithms for decision problems can be extended to related optimisation problems in a rather natural way. However, such simple extensions of algorithms that work well on certain decision problems are not always effective for finding optimal or near-optimal solutions of the corresponding optimisation problems, and consequently, different algorithmic methods need to be considered for this task.

1.2 Two Prototypical Combinatorial Problems In the following, we introduce two well-known combinatorial problems which will be used throughout the first part of this book for illustrating algorithmic techniques and approaches. These are the Propositional Satisfiability Problem (SAT), a prominent combinatorial decision problem which plays a central role in several areas of computer science, and the Travelling Salesman Problem (TSP), one of the most extensively studied combinatorial optimisation problems. Besides their prominence and well established role in algorithm development, both problems have the advantage of being conceptually simple, which facilitates the development, analysis and presentation of algorithms and algorithmic ideas. Both will be discussed in more detail in Part 2 of this book (see Chapters 6 and 8).

The Propositional Satisfiability Problem (SAT)

Roughly speaking, the Propositional Satisfiability Problem is, given a formula in propositional logic, to decide whether there is an assignment of truth values to the propositional variables appearing in this formula under which the formula evaluates to 'true'. In the following, we present a formal definition of SAT. While the details of this definition may not be crucial for comprehending the restricted forms of the problem used in the remainder of this book, they are important for a deeper understanding of the nature and properties of the general SAT problem.

Propositional logic is based on a formal language over an alphabet comprising propositional variables, truth values and logical operators. Using logical operators, propositional variables and truth values are combined into propositional formulae which represent propositional statements. Formally, the syntax of propositional logic can be defined in the following way:

Definition 1.1 Syntax of Propositional Logic

S := V [union] C [union] O [union] {(, )} is the alphabet of propositional logic, with V := {x_i | i [member of] N} denoting the countable infinite set of propositional variables, C := {T, [perpendicular to]} the set of truth values (or propositional constants) true and false, and O := {¬, ^, v} the set of propositional operators negation ('not'), conjunction ('and') and disjunction ('or').
(Continues...)

---

Excerpted from Stochastic Local Search by Holger H. Hoos. Copyright © 2005 by Elsevier Inc.. Excerpted by permission of Elsevier Science.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---