Optimization Basics Lab
Ants find the shortest path to food, bees build honeycombs with the least wax, and delivery companies trim every mile. Optimization means choosing the values of decision variables that make an objective as good as possible while respecting constraints. Every optimization method is, at heart, a search.
Based on Chapter 1, “Introduction to search and optimization,” in Alaa Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning Publications, 2024 (ISBN 978-1633438835).
A search agent mixing exploration (gold) and exploitation (blue) on a landscape with a wide local minimum and a narrow global one.
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 search methods whose goal is an optimal or near-optimal state within the feasible search space: the part of the problem space where every constraint is satisfied.
Optimization is everywhere: nature (foraging ants and bees, bird migration), daily life (planning errands, shopping on a budget), and industry (parcel delivery, cell tower placement, ride-hailing, emergency dispatch, airline crew scheduling, hospital planning, Industry 4.0 and smart cities). Scale matters, though: a small pizzeria with ten deliveries a night gains little from sophisticated routing, while fleet dispatching and crew scheduling gain a lot.
Nature
Ants and bees optimize foraging; honeycombs use hexagons for space, wax and strength; migration routes save energy.
Daily life
Ordering errands to save travel time, stretching a grocery budget, fitting a workout into limited time.
Industry
Delivery routing, tower placement, ride-hailing dispatch, crew scheduling, supply chains, assembly lines.
Cities
Asset assignment, energy, water, pollution, waste management and bushfire containment.
The book’s methodology (Figure 1.1)
From toy problems to the real world
Toy problems are small enough to solve by hand, so every step of an algorithm can be followed. Real-world problems fall into three groups that differ in how long we can wait and how good the answer must be (Figure 1.2).
| Group | Examples | Time to solve | Expected quality |
|---|---|---|---|
| Benchmark and classic | Test functions (Ackley, Rastrigin, Rosenbrock…), n-puzzle, n-queens, bin packing, knapsack, MST, TSP, Chinese postman, assignment, job shop, graph coloring | Varies | Known optimum, for testing |
| Design (strategic) | Suspension and wheel design, VLSI, assembly line balancing, railway scheduling, PID tuning, timetabling, political districting, hospital planning, placing EV chargers | Minutes to days, run rarely | High |
| Planning (tactical) | Motion planning, ride-sharing, shift planning, task allocation, vehicle routing, appointment and patient scheduling, trip itineraries | Seconds to minutes | Medium |
| Control (operational) | Elevator dispatching, communication relaying, vehicle motion control, multirobot control, microrobot drug delivery, truck platooning | Milliseconds to seconds, repeatedly | Lower: speed matters more |
Basic ingredients of optimization problems
Find X that optimizes f(X) subject to equality constraints gi(X) = 0 and inequality constraints hj(X) ≤ 0 (equation 1.1), where
- X = (x1, …, xn) are the decision variables, the inputs we control;
- f(X) = (f1, …, fM) are the objective functions (also called criteria, cost, utility or merit functions);
- g and h are the constraints, plus boundary constraints on each variable.
| Solution | Meaning |
|---|---|
| Feasible | Satisfies all the constraints |
| Optimal | Feasible, with the best objective value |
| Near-optimal | Feasible and very good, but not necessarily the best |
| Global minimum | f(x*) ≤ f(x) for every x in the domain |
| Strong local minimum | f(x*) < f(x) for all other x in a neighborhood |
| Weak local minimum | f(x*) ≤ f(x) in a neighborhood: flat spots and saddle points |
Feasible solutions, global and local minima (Figure 1.3)
Minima inside the bounds
Click the curve to probe a pointDecision variables and objectives: ticket pricing (Sections 1.3.1 and 1.3.2)
An event organizer pays fixed costs a (venue, security, speakers) and a variable cost b per attendee (badges, lunch). Demand falls with the ticket price x: Q = 5,000 − 20x tickets (equation 1.2), so 5,000 attend for free and nobody at $250. The profit is f(x) = Qx − (a + Qb) (equations 1.3 and 1.4). With a = $50,000 and b = $60, f(x) = −20x² + 6,200x − 350,000; setting df/dx = −40x + 6,200 = 0 gives x* = $155 and a profit of $130,500 (Figure 1.5).
Duality: maximizing f is the same as minimizing −f. Scaling f by a positive constant or shifting it by a constant changes the objective value but not the optimal decision (Figure 1.4).
Set the price
Listing 2.4 solves it with SciPyMultiple objectives: electric vehicle design (Figure 1.6)
An EV designer wants to minimize acceleration time (0 to 60 mph) and maximize EPA range. A bigger battery adds range but also weight, so the objectives conflict. Decision variables might be wheel size, motor power and battery capacity.
A preference-based approach scalarizes the objectives with weights; the result depends on the weights you choose. A Pareto approach keeps every nondominated design (no other design is better in one objective without being worse in the other) and decides later. The 13 designs from the book’s notebook are all nondominated: each extra mile of range costs acceleration.
When there is no objective at all, only constraints, the problem is a constraint-satisfaction problem, such as placing 4 queens on a 4 × 4 board without attacks (two equally good solutions exist).
Weigh range against acceleration
Hard and soft constraints: the cargo bike (Section 1.3.3)
Hard constraints must be satisfied; soft constraints are desirable. In school timetabling, two lectures in one room at once is forbidden (hard), while back-to-back lectures in nearby rooms are merely preferred (soft). In a navigation app, avoiding ferries or toll roads can be hard, avoiding school zones at drop-off time soft.
Soft constraints enter the objective as a penalty or reward. A cargo bike can carry 100 kg; choose parcels to maximize profit. As a soft constraint, an overweight load loses a penalty of 50 (equations 1.5 and 1.6). Penalties can also be raised as the search goes on: lenient early to encourage exploration, strict at the end.
Load the bike (Figure 1.7)
Tick the parcelsWell-structured vs. ill-structured problems
Herbert Simon described well-structured problems (WSPs): a clear test for solutions, a problem space that represents the states, legal state changes, and computation that stays tractable. A robot picking defective parts off a conveyor belt is one: the states (arm position, speed, gripper), operators (motion commands), goal, stopping and evaluation criteria (duration, success rate) are all clear, and the workspace is static and fully observable (Figure 1.8).
Ill-structured problems (ISPs) have some of the following: unclear or changing goals, multimodality, no exact model or proven algorithm, hard-to-predict consequences, uncertainty and partial observability, and computational intractability. Dispatching four elevators over ten floors is one: calls cannot be predicted and the state space is enormous (Figure 1.9).
Some problems are WSPs in principle but ISPs in practice: the traveling salesman problem is easy to state, but naive search over 13 cities faces 13! = 6,227,020,800 tours. Most algorithms in the book are stochastic, derivative-free black-box solvers aimed at such problems.
How big is the state space?
Search algorithms and the search dilemma
Exploration (diversification) investigates new regions of the feasible search space; exploitation (intensification) focuses on regions where good solutions were already found (Figure 1.10). Move to a new city and you first try many restaurants, then settle on a few favorites. Honeybee foragers exploit known flowers while scouts (5 to 25% of the foragers) keep exploring.
Pure exploitation behaves like local search and gets trapped in the nearest valley; pure exploration behaves like random search and rarely pins down the exact optimum. Here a searcher has 150 evaluations. At each one it explores (samples anywhere) with probability ε, or exploits (samples near the best point so far). A run counts as a success if it gets within 5% of the global minimum.
| Exploitative | Explorative |
|---|---|
| Local search | Random search |
| Fast, precise near a good solution | Covers the whole space |
| Easily trapped in local optima | Impractically slow to refine |
Good algorithms balance the two.
Explore or exploit?
Minimize: brighter is lowerPython in Google Colab
Open the book’s Chapter 1 notebooks directly in Colab, or the Optimization Basics Lab companion notebook with the from-scratch implementations below. They need only the Python standard library.
Notebooks
From-scratch implementations
# Feasible solutions, global and local minima (Section 1.3, Figure 1.3) import math f = lambda x: 3 * math.cos(x * x) - math.sin(3 * x) * math.exp(-x) # the multimodal function of MathPlots.ipynb LB, UB = -3, 3 # boundary constraints on the decision variable def local_minima(lo, hi, n=60000): """Scan a fine grid and keep the points lower than both neighbors.""" xs = [lo + (hi - lo) * i / n for i in range(n + 1)] return [x for a, x, b in zip(xs, xs[1:], xs[2:]) if f(x) < f(a) and f(x) < f(b)] minima = local_minima(-4, 4) feasible = [x for x in minima if LB <= x <= UB] best = min(feasible + [LB, UB], key=f) # the bounds can hold the optimum too for x in minima: kind = "infeasible" if not LB <= x <= UB else "global minimum" if x == best else "strong local minimum" print(f"x = {x:6.3f} f(x) = {f(x):8.3f} {kind}") print(f"Lowest point overall: x = {min(minima, key=f):.3f}, but it lies outside the bounds [{LB}, {UB}]")
# The ticket pricing problem (Sections 1.3.1 and 1.3.2, Figures 1.4 and 1.5) a, b = 50_000, 60 # fixed costs ($) and variable cost per attendee ($) LB, UB = 0, 250 # boundary constraints on the ticket price Q = lambda x: 5000 - 20 * x # expected tickets sold at price x (equation 1.2) profit = lambda x: Q(x) * x - (a + Q(x) * b) # revenue minus costs = -20x^2 + 6,200x - 350,000 def golden_section(g, lo, hi, tol=1e-6): """Derivative-free search for the maximum of a unimodal function on [lo, hi].""" r = (5 ** 0.5 - 1) / 2 c, d = hi - r * (hi - lo), lo + r * (hi - lo) while hi - lo > tol: if g(c) > g(d): hi, d = d, c c = hi - r * (hi - lo) else: lo, c = c, d d = lo + r * (hi - lo) return (lo + hi) / 2 x_star = 125 + b / 2 # from df/dx = -40x + 5,000 + 20b = 0 print(f"Derivative: x* = ${x_star:.2f}, profit = ${profit(x_star):,.0f}") x_gs = golden_section(profit, LB, UB) print(f"Golden-section search: x* = ${x_gs:.2f}, profit = ${profit(x_gs):,.0f}") best = max(range(LB, UB + 1), key=profit) print(f"Grid search over whole dollars: x* = ${best}, profit = ${profit(best):,.0f}") # Duality and simple operations do not move the optimal decision (Figure 1.4) fk = lambda x: profit(x) / 1000 # profit in K$ grid = [i / 10 for i in range(0, 2501)] for name, g in [("base, f", fk), ("duality, -f (minimize)", lambda x: -fk(x)), ("stretched, f/2", lambda x: fk(x) / 2), ("shifted, f + 3", lambda x: fk(x) + 3)]: pick = min(grid, key=g) if name.startswith("duality") else max(grid, key=g) print(f"{name:24s} best x = {pick:.1f}, value = {g(pick):,.2f} K$")
# Multi-objective electric vehicle design (Section 1.3.2, Figure 1.6, Acceleration_vs_EPA.ipynb) # minimize acceleration time (0-60 mph, s) and maximize EPA range (miles) designs = [(1.7, 210), (1.9, 270), (2.0, 340), (2.2, 350), (2.4, 355), (2.7, 370), (3.2, 380), (3.7, 410), (4.0, 450), (4.5, 470), (5.0, 500), (5.5, 520), (6.0, 530)] def dominates(p, q): """p dominates q if it is no worse in both objectives and better in at least one.""" return p[0] <= q[0] and p[1] >= q[1] and p != q pareto = [p for p in designs if not any(dominates(q, p) for q in designs)] print(f"{len(pareto)} of {len(designs)} designs are nondominated: every gain in range costs acceleration") # Preference-based approach: normalize both objectives to [0, 1] and scalarize with a weight w on range a0, a1 = min(d[0] for d in designs), max(d[0] for d in designs) r0, r1 = min(d[1] for d in designs), max(d[1] for d in designs) for w in (0.0, 0.25, 0.5, 0.75, 1.0): score = lambda d: w * (d[1] - r0) / (r1 - r0) + (1 - w) * (a1 - d[0]) / (a1 - a0) best = max(designs, key=score) print(f"weight on range {w:.2f}: choose {best[0]} s, {best[1]} miles")
# The cargo bike loading problem: hard vs. soft constraints (Section 1.3.3, Figure 1.7) from itertools import product weight = [14.6, 20, 8.5, 10, 13, 9.6, 4.9, 16.5, 8.77, 7.8] # kg, items 1 to 10 profit = [14.54, 15.26, 5.8, 12.12, 8.2, 7.4, 10.3, 13.5, 6.6, 20.9] # $ C, PENALTY = 100, 50 # max payload (kg) and overweight penalty def evaluate(x, soft): w = sum(wi for wi, xi in zip(weight, x) if xi) p = sum(pi for pi, xi in zip(profit, x) if xi) if w > C: return (p - PENALTY if soft else float("-inf")), w, p # hard: infeasible; soft: penalized return p, w, p for soft in (False, True): best = max(product((0, 1), repeat=10), key=lambda x: evaluate(x, soft)[0]) score, w, p = evaluate(best, soft) print(f"{'soft' if soft else 'hard'} constraint: items {[i + 1 for i, b in enumerate(best) if b]}, {w:.2f} kg, ${p:.2f}") everything = evaluate((1,) * 10, True) print(f"Loading all ten parcels: {everything[1]:.2f} kg, profit ${everything[2]:.2f}, penalized score {everything[0]:.2f}") print(f"Search space: 2^10 = {2 ** 10} subsets, checked exhaustively")
# Ill-structured problems and the search dilemma (Sections 1.4 and 1.5) import math import random # 1. Size of the elevator dispatching state space (Figure 1.9) and of a 13-city TSP floors, cars = 10, 4 states = floors ** cars * 2 ** (floors * cars) * 2 ** (2 * (floors - 1)) print(f"Elevator states: 10^4 x 2^40 x 2^18 = {states:.3e}") print(f"13-city asymmetric TSP: 13! = {math.factorial(13):,} tours") # 2. Exploration vs. exploitation on a landscape with a wide local and a narrow global minimum def f(x, y): return -(8 * math.exp(-((x - 2.2) ** 2 + (y + 1.6) ** 2) / 0.12) + 5 * math.exp(-((x + 1.4) ** 2 + (y - 1.2) ** 2) / 2.0) + 3.5 * math.exp(-((x - 1.2) ** 2 + (y - 2.1) ** 2) / 0.5)) def search(eps, rng, budget=150, sigma=0.2): """With probability eps sample anywhere (explore); otherwise sample near the best point (exploit).""" bx, by = rng.uniform(-3, 3), rng.uniform(-3, 3) best = f(bx, by) for _ in range(budget - 1): if rng.random() < eps: x, y = rng.uniform(-3, 3), rng.uniform(-3, 3) else: x = min(3, max(-3, bx + rng.gauss(0, sigma))) y = min(3, max(-3, by + rng.gauss(0, sigma))) if f(x, y) < best: bx, by, best = x, y, f(x, y) return best rng = random.Random(1) for eps in (0, 0.1, 0.3, 0.5, 0.7, 0.9, 1): runs = [search(eps, rng) for _ in range(400)] hits = sum(r < -7.6 for r in runs) / len(runs) # within 5% of the global minimum (-8) print(f"exploration rate {eps:.1f}: found the global minimum in {hits:5.1%} of runs")
To run: open the companion notebook in Colab and press Shift+Enter in each cell, or paste a tab’s code into any notebook.
What to remember
Three ingredients
Decision variables you control, objective functions to minimize or maximize, and hard or soft constraints the solution must respect.
Feasible and optimal
The best solution is the best feasible one; local minima can trap a search, and bounds can move the optimum.
Ill-structured problems
Most real problems are dynamic, uncertain and huge, so near-optimal answers found quickly often beat optimal answers found late.
Explore and exploit
Balancing diversification and intensification lets an algorithm escape local optima without wasting time.
References: H. A. Simon, “The structure of ill structured problems,” Artificial Intelligence, 1973. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 1.
Check your understanding
Two quick questions on Chapter 1. Pick an answer to check it.
Q1. In the electric vehicle design example, what makes a design part of the Pareto set?
A Pareto (nondominated) design cannot be improved in range without losing acceleration time, or vice versa. A weighted sum picks one design whose choice depends on the weights, which is the preference-based approach.Q2. A searcher with a fixed budget of evaluations only exploits, always sampling near the best point found so far. What is the most likely outcome on a landscape with a wide local minimum and a narrow global one?
Pure exploitation behaves like local search and settles in whichever valley it starts near. Covering the space without refining is the failure mode of pure exploration (random search); good algorithms balance the two.For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms.