Appendix C. Exercises and Solutions

This appendix gathers a comprehensive, chapter-aligned set of exercises with full solutions designed to bridge theory and practice across the book’s topics. It blends MCQs, true/false, short-answer reasoning, modeling and classification tasks, and hands‑on coding assignments. The material reinforces fundamentals (e.g., computational complexity, problem types, and modeling choices) while steadily moving into algorithmic design, performance trade‑offs, and practical implementation details, encouraging readers to verify concepts, compare strategies, and iteratively improve solutions.

The scope is broad and application‑oriented. Early sections revisit blind and informed search (BFS/DFS, UCS, A*, best‑first, hill climbing, contraction hierarchies), complexity classes (P, NP, co‑NP, NP‑hard/complete), and optimization modeling (decision variable structure, objective types, hard/soft constraints, LP/QP/NLP). Subsequent chapters dive into metaheuristics—simulated annealing, tabu search, genetic algorithms and variants, particle swarm optimization, and ant colony optimization—then expand to supervised/unsupervised learning (SOMs, attention, graph learning) and reinforcement learning (bandits, A2C/PPO, vectorized training). The exercises repeatedly ground ideas in real‑world contexts: routing and trip planning, facility location and districting, feed‑mix and knapsack‑like loading, composite laminates, open‑pit mining, school transport, ridesharing, trilateration, and resource allocation.

Solutions are implementation‑centric, with step‑by‑step Python examples and reproducible workflows. They employ widely used libraries and toolkits—PuLP for LPs, NetworkX and OSMnx for routing, simanneal and custom SA, optalgotools for TS and TSP, pymoo for GA/NSGA‑II, pyswarms for PSO, Stable‑Baselines3 for RL (A2C/PPO), Vowpal Wabbit for contextual bandits, and MIDACO and GEM for specialized ACO and motor‑control settings. Classic benchmarks (Rosenbrock, Ackley, Schwefel, TSP) sit alongside domain cases (e.g., feed‑mix LP, school bus scheduling, cargo bike loading, airliner service design). Throughout, the appendix emphasizes data handling, parameter tuning, visualization, and head‑to‑head method comparisons (e.g., cooling schedules in SA, operator choices in GA, node ordering in CH), equipping readers to experiment, evaluate, and generalize solutions beyond the given instances.

Figure C.1 Each item has a utility and a weight, and we want to maximize the utility of the contents of the knapsack. The problem is constrained by the capacity of the bag.

Figure C.2 Simplified map.

Figure C.3 A graph search exercise

Figure C.4 Blind search crossword puzzle

Figure C.5 Blind search crossword puzzle solution

Figure C.6 Contracting node E

Figure C.7 Directed graph

Figure C.8 Search space

Figure C.9 Informed search word search puzzle

Figure C.10 Informed search word search puzzle solution

Figure C.11 Travelling Salesman Problem (TSP) for 20 largest US cities.

Figure C.12 Simulated annealing crossword puzzle

Figure C.13 Solution of 20 largest US cities TSP using simanneal

Figure C.14 Simulated annealing crossword puzzle solution

Figure C.15 Schwefel function

Figure C.16 Composite Laminate Design - Apple’s US Patent 7790637 B2

Figure C.17 Pairwise strength gain/loss

Figure C.18 TS word search puzzle

Figure C.19 Composite Laminate Design - TS Initialization

Figure C.20 Composite Laminate Design – Iteration-1

Figure C.21 Composite Laminate Design – Iteration-2

Figure C.22 Composite Laminate Design – Iteration-3

Figure C.23 Composite Laminate Design - TS Iterations 4 and Aspiration Criterion

Figure C.24 Frequency-based Memory

Figure C.25 TS word search puzzle solution

Equation 7.7

Figure C.26 Ackley function

Figure C.27 Cargo bike loading problem for 10 items with given weight, profit and efficiency (profit/weight)

Figure C.28 Opencast mining problem

Figure C.29 Cargo bike loading solution

Figure C.30 Precedence graph for extraction of blocks in Level 2 and 3

Equation 9.18

Figure C.31 Ridesharing Problem

Equation 9.19

Equation 9.20

Equation 9.21

Figure C.32 Cell tower trilateration

Figure C.33 Hours worked per each doctor

Figure C.34 School microscopes supply-demand

Equation 10.18

Figure C.35 Optimal route generated by ACO

Figure C.36 Supply-demand problem solution obtained by MIDACO

Figure C.37 Progress of SOM training with increasing numbers of iterations.

Figure C.38 gym-electric-motor (GEM) Environment [6]

Figure C.39 Average reward in each iteration during the learning process

FAQ