Paradigms for Optimization Problems - A Concise and Practical Introduction to Programming Algorithms in Java - page 191

9
Paradigms for Optimization Problems

9.1 Introduction

In this chapter, we consider fundamental optimization problems that occur in
many real-life applications. The few selected core optimization problems are
very representative of a broad class of mathematical problems encountered in
practice. A major characteristic of these problems is that they are all combi-
natorial by essence. This means that the optimization algorithms described in
the following are not approaching an optimal solution numerically (by say, a
Newton-like gradient descent method as seen previously in Chapter 2), but

rather exploring and searching for exact solutions in large but finite discrete
configuration spaces . The optimization techniques presented in the remainder
are broad enough that their underlying schemes can be used for solving various
problems; these different kinds of solving methodologies are called paradigms
since they yield generic algorithms for tackling many similar problems.
We first start by describing the naive brute force method, called exhaustive
search , which consists of visiting all positions of configuration spaces. We
then show how plugging a few structural constraints emanating directly
from problems' properties allows one to significantly shrink the number of
inspected configurations using a so-called backtracking mechanism implicitly
implemented by recursion. As the size of problems grows, these exhaustive
search and backtracking algorithms unfortunately suffer from browsing these
gigantic domains. These exponentially large configuration spaces are too costly
to explore, and solving these problems in practice become intractable .To

§