Practical Python AI Projects: Mathematical Models of Optimization Problems with Google OR-Tools

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.