| dc.description.abstract | Artificial intelligence is a wide field covering diverse techniques,
objectives, and measures of success. One branch is concerned with finding
provably optimal solutions to some well-defined problems.
This book is an introduction to the art and science of implementing
mathematical models of optimization problems.
An optimization problem is almost any problem that is, or can be,
formulated as a question starting with “What is the best … ?” For instance,
• What is the best route to get from home to work?
• What is the best way to produce cars to maximize
profit?
• What is the best way to carry groceries home: paper or
plastic?
• Which is the best school for my kid?
• Which is the best fuel to use in rocket boosters?
• What is the best placement of transistors on a chip?
• What is the best NBA schedule?
These questions are rather vague and can be interpreted in a multitude
of ways. Consider the first: by “best” do we mean fastest, shortest, most
pleasant to ride, least bumpy, or least fuel-guzzling? Besides, the question
is incomplete. Are we walking, riding, driving, or snowboarding? Are we
alone or accompanied by a screaming toddler?
To help us formulate solutions to optimization problems, optimizers 1
have established a frame into which we mould the questions; it’s called a
model. The most crucial aspect of a model is that it has an objective and it
has constraints. Roughly, the objective is what we want and the constraints
are the obstacles in our way. If we can reformulate the question to clearly
identify both the objective and the constraints, we are closer to a model.
Let’s consider in more detail the “best route” problem but with an eye
to clarify objective and constraints. We could formulate it as
Given a map of the city, my home address, and the
address of the daycare of my two-year-old son, what
is the best route to take on my bike to bring him to
daycare as fast as possible?
The goal is to find among all the solutions that satisfy the requirements
(that is, paths following either streets or bike lanes, also known as the
constraints) one path that minimizes the time it takes to get there (the
objective).
Objectives are always quantities we want to maximize or minimize
(time, distance, money, surface area, etc.), although you will see examples
where we want to maximize something and minimize something else;
this is easily accommodated. Sometimes there are no objectives. We say that the problem is one of feasibility (i.e. we are looking for any solution
satisfying the requirements). From the point of view of the modeler, the
difference is minimal. Especially since, in most practical cases, a feasibility
model is usually a first step. After noticing a solution, one usually wants
to optimize something and the model is modified to include an objective
function. | vi |
