12.2 Capstone: Model and Optimize a Smart-City Network

This final section is a guided design project. You will not meet a new mathematical topic without preparation. Instead, you will connect ideas already developed across the course: sets describe the objects, logic states the rules, functions and relations connect data, proofs justify claims, algorithms carry out decisions, counting measures possibilities, probability represents uncertainty, trees organize choices, graphs represent routes, Boolean circuits make immediate decisions, and finite-state machines control behavior over time.

Our setting is a small smart city. Ambulances and fire engines must reach incidents quickly, intersections must change signal phases safely, and a limited budget must be spent on upgrades that improve resilience.

1. Translate a Story into a Mathematical Model

Before optimizing anything, identify the objects and the questions.

The city has six important sites:

where $H$ is the hospital, $F$ the fire station, $C$ the central intersection, $N$ and $S$ the north and south districts, and $P$ the power depot.

Roads connect pairs of sites. Let $E$ be the set of roads. Travel time in minutes is a weight function

where $\mathbb{R}_{>0}$ means the set of positive real numbers. Together,

is a weighted graph.

The letters $HC$ denote the edge $\{H,C\}$; they do not mean multiplication. If roads allow travel in both directions with equal time, this is an undirected graph. A closure removes an edge temporarily. Congestion changes an edge weight rather than removing the edge.

Questions determine the right structure

One real system can require several models:

Choosing a graph alone does not finish the model. A good model states what each vertex, edge, weight, bit, state, and event means in the real system.

2. Separate Immediate Decisions from Timed Control

Suppose three input bits are observed at the central intersection:

• $e=1$ means an emergency vehicle has requested priority;
• $r=1$ means an ordinary road sensor reports a waiting queue;
• $p=1$ means the pedestrian crossing is active.

Define a Boolean request signal

This says that an emergency request sets $u=1$, while an ordinary request sets it only when no pedestrian crossing is active. Importantly, $u=1$ does not mean “turn the light green immediately.” It asks the state machine to begin a safe transition.

The signal controller uses four states:

• Normal: the ordinary schedule is running.
• Clear: all vehicle directions are held while the intersection clears.
• Priority: the emergency route receives a green phase.
• Recover: the controller clears the intersection again before returning to normal.

A simplified transition pipeline is

This separation is a design principle:

The circuit answers a current yes-or-no question. The state machine enforces a safe sequence over time.

3. Dispatch Is an Algorithm, Not a Guess

When an incident occurs at $N$, the city compares the hospital route and the fire-station route. Dijkstra’s algorithm from Chapter 11 computes shortest travel times because all road weights are positive.

From $H$, Dijkstra first records tentative labels $d(C)=4$ and $d(N)=6$. It settles $C$ next because $4<6$. Relaxing edge $CN$ proposes $4+2=6$, so the label of $N$ remains $6$. All other unsettled labels are larger, and $N$ is then settled. Therefore:

There are two different shortest routes, $H\!-\!N$ and $H\!-\!C\!-\!N$, both with total time $6$. This is a useful reminder: a shortest distance may be unique even when the shortest path is not.

If road $HN$ closes, the remaining route $H\!-\!C\!-\!N$ still takes $6$. The network has redundancy for that failure. If $CN$ also closes, $N$ may still be reached through $P$, but the travel time changes. Connectivity says whether service remains possible; shortest-path distance says how costly that remaining service is.

Close or congest roads on the live city map, compare dispatch routes, evaluate the priority-request circuit, and advance the signal controller until the chosen vehicle receives a protected phase.

4. State Requirements Before Choosing Upgrades

An upgrade is only “better” relative to stated requirements. We use four:

1. Reachability: every district must remain connected to at least one emergency station after any single road failure. 2. Response: expected emergency travel time should be small. 3. Safety: conflicting traffic directions must never be green together. 4. Budget: the total installation cost may not exceed $B$.

Suppose there are $m$ candidate upgrades. Define a decision bit

If upgrade $i$ costs $c_i$, the budget constraint is

The summation adds the cost of every selected upgrade because terms with $x_i=0$ contribute nothing.

Candidate upgrades may have different effects:

Comparing only purchase cost would ignore these different benefits.

5. Model Uncertainty with Scenarios

A scenario is one possible incident-day condition: an incident location, congestion pattern, road failure, and controller status. Let the finite scenario set be

Assign probability $\Pr(\omega_j)$ to scenario $\omega_j$, with

For an upgrade plan $x$, let $T(x,\omega_j)$ be the shortest emergency response time in scenario $\omega_j$. Its expected response time is

This is the weighted average from Chapter 9. A rare but disastrous disconnection should not silently disappear, so define $L(x,\omega_j)=1$ if the scenario loses emergency service and $0$ otherwise. Then

6. Make Trade-offs Explicit

An objective function turns a proposed design into a score to minimize. One example is

where $\alpha,\beta,\gamma\ge 0$ are policy weights:

• $\alpha$ expresses the importance of response time;
• $\beta$ expresses the importance of installation cost;
• $\gamma$ expresses the importance of avoiding service loss.

These weights are not probabilities. They encode priorities and make different units comparable. Changing them can change the preferred design, so a responsible report shows the chosen values and tests whether the recommendation remains stable under reasonable alternatives.

Sometimes safety and budget should be hard constraints, not terms that can be traded away:

This formulation never accepts an unsafe design merely because it is fast.

7. Search the Feasible Designs Systematically

With $m$ yes-or-no upgrades there are $2^m$ subsets before applying the budget. For a small capstone, exhaustive search is appropriate:

1. generate each bit vector $(x_1,\ldots,x_m)\in\{0,1\}^m$; 2. reject it if its cost exceeds $B$; 3. test graph and controller constraints; 4. simulate every scenario; 5. compute the objective; 6. keep the best feasible design.

This procedure links several chapters:

For larger $m$, $2^m$ grows quickly, as Chapter 5 explained. Then one might use smarter optimization methods, but exhaustive search is valuable here because it is transparent and produces a complete certificate: every feasible plan was considered.

8. Validate, Stress-Test, and Prove

A simulation is evidence about the scenarios tested. A proof covers every case named by its assumptions. A strong design uses both.

Graph validation

For each allowed single-edge failure $f\in E$:

1. form the remaining graph $G-f$; 2. run BFS from $H$ and from $F$; 3. verify that each district belongs to at least one visited set.

Controller safety invariant

Let $n=1$ mean north-south traffic is green and $s=1$ mean east-west traffic is green. The safety requirement is

To prove it, check the output assigned to every reachable controller state and show that no state outputs $n=s=1$. Then check that every transition stays inside the set of these safe states.

Boundary and adversarial tests

Test more than an ordinary day:

• no emergency requests;
• simultaneous sensor and pedestrian requests;
• an emergency that ends during Clear;
• each single road failure;
• maximum modeled congestion;
• a budget exactly equal to the selected upgrade cost.

These tests target boundaries where definitions change and where implementation mistakes often hide.

Allocate a changing budget among backup roads, sensors, and controllers. Replay a fixed deck of incident days, inspect every scenario contribution, and compete against an exhaustive-search certificate for the best feasible plan.

9. The Final Design Argument

A complete capstone submission is not just a map or a score. It is a chain of claims supported by mathematical evidence:

Use this checklist:

1. Definitions: state what every set, graph element, weight, random variable, bit, state, and input means. 2. Assumptions: state which roads are bidirectional, which failures are considered, and how scenario probabilities were chosen. 3. Correct method: explain why the algorithm applies—for example, Dijkstra requires nonnegative weights. 4. Reproducible calculation: show route totals, transition traces, scenario tables, and the budget sum. 5. Proof obligations: prove the safety invariant and the required failure resilience. 6. Trade-off: explain what improves, what it costs, and what uncertainty remains.

10. Course Synthesis

The city model reveals the unifying idea of discrete mathematics: complex systems become understandable when we identify a finite collection of objects, define exact relations and rules, and reason from those definitions.

You began the course by asking how a real situation becomes a discrete model. You can now answer with a disciplined workflow: define the objects, choose structures that preserve the relevant relationships, compute with explicit algorithms, and justify the result with proofs and tests. That workflow—not any single formula—is the lasting tool of discrete mathematics.