As human beings, we constantly strive to optimize our everyday lives. Whether it’s getting to work faster (so you can sleep in a little bit longer), balancing school and leisure time, or even budgeting for personal spending, we try to maximize the benefits and minimize the costs. Likewise, corporations maximize profits by increasing efficiency and eliminating waste. For example, logistics giants like FedEx, UPS, and Amazon spend millions of dollars each year researching new ways to trim the cost of delivering packages. Similarly, telecommunications agencies seek to determine the optimal placement of crucial infrastructure, like cellular towers, to service the maximum number of customers while investing in the minimum level of equipment.

This sort of optimization behavior is not unique to humans; nature likewise tends towards efficiency and optimality. Bacterial colonies, comprised of clusters of between 10 million and 10 billion individual organisms, form an adaptable, complex system that can perform many complicated tasks such as foraging, pathfinding, and learning based on external stimuli. Insects like ants and honeybees have developed their own unique optimization methods, from navigating the shortest path to an existing food source to discovering new food sources in an unknown external environment. Honeybee colonies focus their foraging efforts on only the most profitable patches and build their honeycombs with a shape that economizes labor and wax. Fish swimming in schools or cruising in the same direction minimize total energy usage by exploiting pressure fields created by the other fish. At the same time, migratory birds utilize separation, alignment, and cohesion-based optimization to avoid mid-air collisions and increase flight endurance. Non-biological phenomena also tend towards efficiency. For example, light traveling between two different media will refract along an angle that minimizes the travel time.

As technology has developed, computer-based optimization is now an inescapable reality of the digital era. Transportation network companies (TNCs) like Uber, Lyft, and DiDi route drivers efficiently during passenger trips and direct drivers to ride-hailing hotspots during idle periods to minimize passenger wait time. As urbanization intensifies worldwide, local emergency services depend on efficient dispatching and routing platforms to select and route the appropriate vehicles, equipment, and personnel to respond to incidents across increasingly complex metropolitan road networks. Airliners need to solve several optimization problems such as flight planning, fleet assignment, crew scheduling, aircraft routing and aircraft maintenance planning. Healthcare systems also handle optimization problems such as hospital resource planning, emergency procedure management, patient admission scheduling, surgery scheduling and pandemic containment. Industry 4.0, a major customer of optimization technology, deals with complex optimization problems such as smart scheduling/rescheduling, assembly line balancing, supply-chain optimization, and operational efficiency. Smart cities deal with large-scale optimization problems such as stationary asset optimal assignments, mobile asset deployment, energy optimization, water control, pollution reduction, waste management and bushfire containment. These examples show how ubiquitous and important optimization is as a way to maximize operational efficiency in different domains.

Why care about search and optimization?

Search is the systematic examination of states, starting from an initial state, and ending (hopefully) at the goal state. Optimization techniques are in reality search methods, where the goal is to find an optimal or a near-optimal state within the feasible search space. The feasible search space is a subset of the optimization problem space where all the problem’s constraints are satisfied. It’s hard to come up with a single industry that doesn’t already use some form of search or optimization methods, software, or algorithms. It’s highly likely that somehow in your workplace or industry, you deal with optimization daily; it’s just that you aren’t aware of it. While search and optimization are undoubtedly ubiquitous in almost all industries, it may not always be practical to use complicated algorithms to optimize processes. For example, consider a small pizzeria that offers a food delivery service to its local customers. Let’s assume that the restaurant processes around ten deliveries on an average weeknight. While efficiency-improving strategies (such as avoiding left turns in left-driving countries or right turns in right-driving countries, avoiding major intersections, avoiding school zones during drop-off and pick-up times, avoiding bridges during lift times and favoring downhill roads) may theoretically shorten delivery times and reduce costs, the scale of the problem is so tiny that implementing these kinds of changes may not lead to noticeable impact.

In larger scale problems such as fleet assignment and dispatching, multi-criteria stochastic vehicle routing, resource allocation, crew scheduling, applying search and optimization techniques to a problem must be a qualified decision. Some firms or industries may not benefit from excessive process changes due to a lack of expertise or resources to implement those changes. There may also be the concern of a potential lack of follow-through from stakeholders. Implementing the changes could also cost more than the savings obtained through the optimization process. Later in this book, we will see how these costs can be accounted for when developing search and optimization algorithms.

Without assuming any prior knowledge of search and optimization and with an intermediate knowledge of data structures and Python, this book has been written to take most anyone from never solving search and optimization problems to being a well-rounded search and optimization practitioner able to select, implement and adapt the right solver for the right problem. For managers or professionals involved in the high-level technological decisions at their workplace, these skills can be critical in understanding software-based approaches, their opportunities, and limitations when discussing process improvement. In contrast, IT professionals will find these skills more directly applicable when considering options for developing or selecting new software suites and technologies for in-house use. The following subsection describes the methodology we will follow throughout this book.

Going from toy problem to the real world

When discussing algorithms, many books and references will often present them as a formal definition and then apply them to so-called “toy problems.” These trivial problems are helpful because they often deal with smaller datasets and search spaces while being solvable by hand iteration. This book seeks to follow a similar approach but takes it one step further by presenting real-world data implementations. Whenever possible, resources such as real-world datasets and values are used to illustrate the direct applicability and practical drawbacks of the algorithms discussed. Initially, the scaled-down toy problems help the reader appreciate the step-by-step operations involved in the various algorithms. Later, the real-world Python implementations teach the reader how to use multiple datasets and Python libraries to address the increased complexity and scope of actual data.

As illustrated in Figure 1, source of inspiration of each search or optimization algorithm is highlighted followed by presenting the algorithm pseudocode, algorithm parameters and heuristics used. Algorithm pros and cons and adaptation methods are then described. The book contains many examples that allow the learners to fully understand how each algorithm works by carrying out iterations by hand on a scaled-down version of the problem. It also includes many programming exercises in a special problem/solution/discussion format to understand how a scaled-up version of the problem previously solved by hand can be solved using Python. Through programming, learners can optimally tune the algorithm and study its performance and scalability.

Figure 1 The book’s methodology. Each algorithm will be introduced following a structure that goes from explanation to application.

Throughout this book, we consider several classical and real-world optimization problems to show how to use search and optimization algorithms discussed in the book. Figure 2 shows examples of these optimization/search problems.
Real-world design problems or strategic functions deal with situations when time is not as important as the quality of the solution and users are willing to wait (sometimes even a few days) to get optimal solutions. Planning problems or tactical functions need to be solved in a time span between a few seconds to a few minutes. While you need to solve control problems or operational functions repetitively and quickly, in a time span between few milliseconds to a few seconds. In order to find a solution during such a short period of time, optimality is usually traded in for speed gains.

Figure 2 Examples of classical optimization and real-world optimization/search problems.

It is highly recommended that you first perform the necessary hand iterations for the examples following each algorithm and then try to recreate the Python implementations yourself. Feel free to play around with the parameters and problem scale in the code; one of the advantages of running optimization algorithms through software is the ability to tune for optimality.

Basic ingredients of optimization problems

Optimization refers to the practice of finding the “best” solutions to a given problem, where “best” usually means satisfactory or acceptable, possibly subject to a given set of constraints. The solutions can be classified into feasible, optimal, and near-optimal solutions.

• Feasible solutions are solutions that satisfy all the given constraints.
• Optimal solutions are both feasible and provide the best objective function value
• Near-optimal solutions are feasible solutions that provide a superior objective function value but are not necessarily the best.

A global optimum, or a global minimum in case of minimization problems, is the best of a set of candidate solutions. A search space may combine multiple global minima, strong local minima, and weak local minima as illustrated in Figure 3.

Figure 3 Feasible/acceptable solutions fall within the constraints of the problem. Search spaces may display a combination of global, strong local, and weak local minima.

These optimum-seeking methods, also known as optimization techniques, are generally studied as a part of operations research (OR). OR, also referred to as decision or management science is a field that originated at the beginning of World War II due to the urgent need for the assignment of scarce resources in military operations. It is a branch of mathematics concerned with applying advanced scientific analytical methods to decision-making and management problems to find the best or optimal solutions.
Optimization problems can generally be stated as follows:

Find X which optimizes ƒ
Subject to a possible set of equality and inequality constraints:
gi(X)= 0, i=1,2,…,m
hj(X)<=0, j=1,2,…,p

where

• X=(x1, x2,…,xn)T is the vector representing the decision variables
• ƒ(X)=(ƒ1(X), ƒ2(X),…, ƒM(X)) is the vector of objectives to be optimized/li>
• gi(X) is a set of equality constraints
• <li>hj(X) is a set of inequality constraints

There are three main components of optimization problems: decision variables, objective functions, and constraints.
We can further classify optimization problems based on their structure (well-structured problems vs. ill-structured problems), and the procedure(s) that exist (or don’t) for solving them. This book explores all of these aspects.

Search Algorithms and the Search Dilemma

The goal of any optimization method is to assign values to decision variables to optimize the objective function. To achieve this, optimization algorithms search the solution space for candidate solutions. Constraints are simply limitations on specific regions in the search space. Thus, all optimization techniques are in reality just search methods, where the goal is to find feasible solutions to satisfy constraints and maximizes (or minimizes) the objective functions. We define “search” as the systematic examination of feasible states, starting from the initial state, and ending (hopefully) at the goal state. However, while we explore the feasible search space, the question is if we find a few reasonably good neighboring solutions, should we exploit this region or should we explore more looking for better solutions in other regions of the feasible search space?

This exploration-exploitation or diversification-intensification dilemma is one of the most important problems in search and optimization and in life as well. We apply exploration-exploitation tactics in our life. When we move to a new city, we start by exploring different stores and restaurants and then focus on shortlisted options around us. During midlife crisis, some middle-aged individuals start to feel bored getting stuck in daily routine and lifestyle without clear satisfactory accomplishment and tend to take more explorative actions. US immigration system tries to avoid exploiting specific segments of applicants (e.g. family, skilled-workers, refugees and asylum seekers) and enables more diversity through computer-generated lottery. In social insects like honeybees, foraging for food sources is performed by two different worker groups, recruits and scouts (5–25% of the foragers). Recruits focus on a specific food source while scouts are novelty seekers who keep scouting around for rich nectar. In search and optimization, exploration-exploitation dilemma represents the tradeoff between exploring new unvisited states/solutions in the search space and exploiting the elite solutions found in a certain neighborhood in the search space (Figure 4).

Exploration (or diversification) is the process of investigating new regions in the feasible search space with the hope of finding other promising solutions. On the other hand, exploitation (or intensification) is the process of directing the search agent to focus on an attractive region of the search space.

Figure 4 Search Dilemma. There is always a tradeoff between branching out to new areas of the search space or focusing on an area with known “good” or elite solutions..

Local search algorithms are exploitation/intensification algorithms that can be easily trapped in local optima if the search landscape is multimodal. On the other extreme, random search algorithms keep exploring the search space with a high chance of reaching global optima at the cost of the impractical search time. Generally speaking, explorative algorithms can find global optima at the cost of processing time, while exploitative algorithms risk getting stuck at local minima.

What will you learn from this book?

Readers can expect to learn the following from this book:

1. 1. Get up to speed with the core concepts of search and optimization.
   2. Deal with discrete and continuous ill-structured optimization problems using deterministic and stochastic derivative-free optimization techniques.
   3. Apply deterministic graph search algorithms to solve graph problems.
   4. Apply nature-inspired search and optimization algorithms to find optimal or near-optimal solutions for practical design, planning and control problems.
   5. Use machine learning methods to solve search and optimization problems.
   6. Solve the search dilemma by achieving optimal trade-off between search space exploration and exploitation using algorithm parameter adaptation.
   7. Use state-of-the-art Python libraries related to search and optimization.

Summary

Optimization is a search process for finding the “best” solutions to a problem that provide the best objective function values, possibly subject to a given set of hard and soft constraints. There are many variables and considerations that go into this and this book explores them deeply.

If you want to learn more, check out the book here.