2 A Deeper Look at Search and Optimization

This chapter establishes a shared vocabulary for problems and algorithms in search and optimization, motivating why classification matters for selecting effective solution methods under time and quality constraints. It decomposes optimization problems into decision variables, objectives, and constraints, then surveys key axes of variability: number and type of variables (continuous, integer, mixed; combinatorial), objective landscapes (unimodal, multimodal, deceptive), single vs multi-objective and constraint-satisfaction formulations, and linear vs nonlinear structures (including quadratic). Problem hardness (P, NP, NP-complete, NP-hard) is positioned alongside practical expectations on solution quality and available time across design (offline, accuracy-first), planning (seconds to minutes, speed-quality trade-offs), and control (real-time, speed-critical) scenarios, illustrated with examples such as TSP and its variants, clustering, N-Queens, linear programming for blending, nonlinear design and physics problems, political districting, ridesharing, and fast control for UAV/MAV relay networks.

Algorithms are organized by how they explore the search space—local search (neighborhood-based, prone to local optima) versus global search (broader exploration)—and by determinism: deterministic methods (e.g., gradient/Hessian-based optimization; blind and informed graph search like BFS, Dijkstra, A*) produce repeatable paths from the same start, while stochastic methods (e.g., simulated annealing, tabu search, genetic and differential evolution algorithms, particle swarm, ant colony) inject randomness to escape local traps at the cost of repeatability and predictable runtimes. The chapter introduces heuristics as pragmatic rules that find acceptable solutions efficiently without optimality guarantees, and metaheuristics as higher-level strategies that balance diversification and intensification to guide underlying heuristics. It contrasts construction, modification, and recombination search strategies through compact examples (bin packing with first-fit and ordering heuristics; greedy, tweak-and-improve, and combine-and-improve steps for a knapsack-style cargo-bike load).

Finally, the chapter surveys nature-inspired and learning-based paradigms that tackle ill-structured, nonlinear, multimodal, and multiobjective problems: simulated annealing from thermal physics; evolutionary computation (GA, GP, ES, EP, DE); swarm intelligence (PSO, ACO, ABC, Firefly, Grey Wolf, and others); and memory-based strategies like tabu search. It highlights neural networks, graph neural methods, attention mechanisms, self-organizing maps, and reinforcement learning as adaptable optimizers or components within hybrid pipelines. Emphasis is placed on the robustness and problem-agnostic applicability of metaheuristics—with minimal tailoring—across diverse design, planning, and control tasks, setting up the remainder of the book to show how these families of algorithms are applied in practice.

Optimization problem classification. An optimization problem can be broken down into its constituent parts, which form the basis of the classification of such problems.

TSP in Greater Toronto Area (GTA). The traveling salesman must visit all the 13 cities, and wishes to select the “best” path, whether that be distance, time, or some other criterion.

Equation 2.1

Smart Cart Clustering. Unused shopping or luggage carts congregate near designated assembly points to make collection and redistribution easier.

Unimodal, multimodal, and deceptive functions. Unimodal functions have one global optimum, while multimodal functions can have many. Deceptive functions contain false optima close to the value of an objective function at a global minimum, which can cause some algorithms to get stuck.

N-Queen Problem. This problem has no objective function, rather, only a set of constraints that must be satisfied.

N-Queens Solution

N-Queens solution using OR-Tools.

Steps of solving ticket pricing problem using Lagrange method

Plant Layout Problem. What is the optimal location for each department that minimizes the overall material handling costs?

Equation 2.4

MineProbe wheel design problem [5].

Finite Catenary Problem. The catenary (or chain) is suspended from two points G0 and Gn+1 [6].

Equation 2.5

Qualities of solutions vs. Search Time. Some types of problems require fast computations but do not require incredibly accurate results, while others (such as design problems) allow more processing time in return for higher accuracy.

Example of Gerrymandering. The two major political parties, Shield and Bell try to gain an advantage by manipulating the district boundaries to suppress undesired interests, and to promote their own.

Ridesharing Problem. This planning problem needs to be solved in a shorter amount of time, as delays could mean lost trips and a bad user experience.

Communications Relaying Problem. A swarm of MAVs must form an ad hoc communication replay between a base station and a trapped victim. The movement of MAVs is a control problem that must be solved repeatedly, multiple times per second. In this case, speed is more important than accuracy, as minor errors can be immediately corrected during the next cycle.

Deterministic vs. stochastic Algorithms. Deterministic algorithms follow a set procedure, and the results are repeatable, while stochastic searches have elements of randomness built into the algorithms.

Handling bin packing problem using first-fit and first-fit decreasing heuristics.

Bin packing problem. Using heuristics allows us to solve the problem much faster than with a brute-force approach. However, some heuristic functions may result in infeasible or suboptimal solutions, and they do not guarantee optimality.

Bin Packing using the Largest-first heuristic. One object has been excluded, as it does not fit into the remaining space.

Bin Packing Problem using Smallest-first. All five objects have been successfully placed into the container.

Repeated solution recombination. Taking the first two elements of S1 and adding it to the last eight elements of S2 yields a new, better solution.

• Search and optimization problems can be classified based on number of decision variables (univariate, multivariate problems), type of decision variables (continuous, discrete, mixed-integer), number of objective functions (mono-objective, multi-objective, constraint-satisfaction problems), landscape of objective function (unimodal, multimodal, deceptive), number of constraints (unconstrained and constrained problems) and linearity of objective functions and constraints (linear problems and nonlinear problems).
• Based on expected quality of solutions and the permissible search time to find the solutions, optimization problems can also be categorized into design problems/strategic functions, planning/tactical problems, and control problems/operational functions.
• Search and optimization algorithms can be classified based on the way the search space is explored (local versus global search), corresponding optimization speeds (online versus offline search/optimization), determinism of the algorithm (deterministic versus stochastic).
• Heuristics (also known as “mental shortcuts” or “rules of thumb") facilitate finding acceptable (optimal or near-optimal) solutions to a complex problem in a reasonably practical time.
• Metaheuristics are high-level strategies used to guide and modify other heuristics to enhance their performance.
• Nature-inspired algorithms are computational models that mimic or reverse engineer the intelligent behaviors observed in nature to solve complex ill-structured problems.

FAQ