Network and Combinatorial Optimization

Introduction and Context

Many business decisions involve selecting, assigning, routing, or connecting discrete objects. A retailer must ship products from plants to markets; a hospital must assign specialists to shifts; a logistics firm must route vehicles; a telecommunications provider must connect facilities reliably; and an airline must schedule aircraft across a network. These problems often have a special mathematical structure: decisions are associated with nodes and arcs, and feasible solutions are governed by conservation, capacity, or matching conditions.

Network and combinatorial optimization studies such problems. Unlike general nonlinear or integer optimization, many network models have highly exploitable structure. Their constraint matrices often possess the total unimodularity property, allowing linear programming methods to produce integer solutions without explicitly imposing integrality. Specialized algorithms can therefore solve very large instances efficiently.

A network model normally consists of a directed graph G = (V, A), where V is the set of nodes and A is the set of directed arcs. Each arc may have a cost, capacity, length, or profit. The central modeling task is to translate a managerial problem into nodes, arcs, objective coefficients, and constraints.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Formulate transportation, assignment, transshipment, and general minimum-cost-flow models.
2. Solve and interpret shortest-path, maximum-flow, matching, routing, and spanning-tree problems.
3. Explain why network structure often produces integral optimal solutions.
4. Select suitable algorithms and assess their computational complexity.
5. Analyze a practical network decision, including capacity, uncertainty, fairness, and implementation issues.

1. Graphs, Networks, and Flows

A graph contains nodes and edges. In a directed graph, an arc (i, j) has an origin i and destination j. An undirected edge represents a two-way connection. A path is a sequence of connected arcs; a cycle begins and ends at the same node. A connected graph contains a path between every pair of nodes when direction is ignored.

A network is a graph with additional numerical data. Typical data include:

A flow xᵢⱼ is the quantity sent on arc (i, j). The basic conservation equation at node i is:

Here bᵢ is net supply: positive for a supply node, negative for a demand node, and zero for a transshipment node. The units of xᵢⱼ and bᵢ must be consistent, such as tonnes per day or units per week. Usually, xᵢⱼ ≥ 0 and xᵢⱼ ≤ uᵢⱼ. For a balanced network, ∑ᵢ bᵢ = 0.

The minimum-cost-flow model is:

The objective minimizes total cost. If cᵢⱼ is a cost per unit and xᵢⱼ is measured in units, the objective is measured in monetary units. Negative arc costs may be allowed, but a negative-cost cycle can make an uncapacitated model unbounded; practical models therefore require appropriate capacities or economic interpretation.

Integrality and total unimodularity

The node–arc incidence matrix of a directed network is totally unimodular. If supplies, demands, and capacities are integral, every extreme-point solution of the corresponding feasible linear program is integral, provided the model has the standard network form. Consequently, solving its linear relaxation can produce an integer flow. This does not mean that every integer optimization problem has this property: side constraints such as fixed-charge decisions, logical conditions, or arbitrary vehicle-routing restrictions can destroy network structure.

2. Transportation and Transshipment Models

Transportation problem

The transportation problem distributes a homogeneous product from m sources to n destinations. Let:

• aᵢ = supply at source i;
• dⱼ = demand at destination j;
• cᵢⱼ = unit shipping cost from source i to destination j;
• xᵢⱼ = quantity shipped from source i to destination j.

For a balanced problem, total supply equals total demand. The model is:

If supply exceeds demand, unused supply can be represented by a dummy destination with zero or specified disposal cost. If demand exceeds supply, a dummy source represents emergency purchasing or lost sales. Dummy costs should reflect the real economic consequence rather than automatically being set to zero.

Worked example: transportation

A firm has two plants and three markets. Plant supplies are 40 and 60 units, and market demands are 30, 30, and 40 units. Unit costs are:

A feasible low-cost plan is:

• Plant 1 → Market 1: 30 units;
• Plant 1 → Market 2: 10 units;
• Plant 2 → Market 2: 20 units;
• Plant 2 → Market 3: 40 units.

The total cost is:

This is a feasible plan, but feasibility alone does not prove optimality. Transportation simplex, network simplex, or a linear-programming solver should be used to verify optimality. A useful managerial interpretation is that Plant 2 serves Market 3 heavily because its relative cost advantage is greatest there.

Transshipment problem

Transportation assumes that goods move directly from sources to destinations. Transshipment permits intermediate nodes such as distribution centres, cross-docks, or regional warehouses. At a transshipment node, inflow equals outflow unless inventory, processing loss, or storage is explicitly modeled.

For each node i, the same conservation equation applies:

A transshipment model is usually represented as a minimum-cost-flow problem. This makes it possible to include arc capacities, intermediate handling costs, and alternative paths. However, a model should not assume unlimited intermediate capacity merely because the physical network contains a node.

3. Assignment and Matching

The assignment problem allocates n agents to n tasks, with exactly one task per agent and exactly one agent per task. Let cᵢⱼ be the cost of assigning agent i to task j, and xᵢⱼ equal 1 if the assignment is made and 0 otherwise.

The Hungarian algorithm solves the square assignment problem in O(n³) time. Its efficiency is based on reducing the cost matrix while preserving the set of optimal assignments. For rectangular problems, dummy agents or tasks can be added, with dummy costs representing nonassignment, overtime, or outsourcing.

Assignment models are bipartite matching models. In a bipartite graph, nodes are divided into two sets and arcs connect only nodes from different sets. A maximum matching maximizes the number of matched pairs. A maximum-weight matching maximizes total edge weight. In workforce analytics, weights might represent expected productivity, qualification fit, or service value. These objectives should be validated carefully: maximizing predicted productivity may create systematically inequitable allocations if the prediction model is biased.

4. Shortest-Path Optimization

The shortest-path problem seeks a minimum-length or minimum-cost path from an origin s to a destination t. Let d(v) denote the current best-known distance to node v. For an arc (u, v) with length wᵤᵥ, the fundamental relaxation operation is:

The units of d and w must match, such as minutes or kilometres.

Dijkstra’s algorithm

Dijkstra’s algorithm is appropriate when all arc lengths are nonnegative. It repeatedly selects the unsettled node with the smallest tentative distance and relaxes its outgoing arcs. With a binary heap, its typical complexity is O((|V| + |A|) log |V|); with a simple array it is O(|V|²). The algorithm is not valid for negative arc lengths.

Bellman–Ford algorithm

Bellman–Ford can handle negative arc lengths and can detect reachable negative cycles. It relaxes every arc repeatedly, up to |V| − 1 times, and has complexity O(|V||A|). It is slower than Dijkstra’s algorithm but more general.

Floyd–Warshall algorithm

Floyd–Warshall computes shortest paths between all pairs of nodes. Its dynamic programming recurrence is:

Here dᵏᵢⱼ is the best distance from i to j using only the first k nodes as intermediate nodes. Its time complexity is O(|V|³), and its memory requirement is O(|V|²). It is attractive for dense networks or repeated all-pairs queries, but less attractive for very large sparse networks.

The shortest path should not automatically be interpreted as the best route. A route with minimum distance may have low reliability, unsafe conditions, toll exposure, or insufficient capacity. Multi-criteria routing requires explicit trade-offs or constraints.

5. Maximum Flow and Minimum Cut

In a capacitated network, the maximum-flow problem sends as much flow as possible from source s to sink t. Each arc (i, j) has capacity uᵢⱼ. Flow conservation applies at intermediate nodes:

The source’s net outflow equals the sink’s net inflow. The model maximizes source outflow subject to 0 ≤ xᵢⱼ ≤ uᵢⱼ.

The Ford–Fulkerson method repeatedly finds an augmenting path in the residual network and sends additional flow along it. With integer capacities and suitable path selection, it terminates with an integral flow. The Edmonds–Karp implementation uses breadth-first search to select shortest augmenting paths and has O(|V||A|²) complexity.

The max-flow/min-cut theorem states that the maximum value of a feasible s–t flow equals the minimum capacity of an s–t cut. A cut divides nodes into S and V\S, with s ∈ S and t ∉ S. Its capacity is:

This theorem has direct managerial meaning: a minimum cut identifies a bottleneck set of resources. Increasing capacity outside the bottleneck may have no effect until the bottleneck is expanded.

6. Routing and Vehicle-Routing Problems

The travelling salesperson problem (TSP) seeks a minimum-cost tour visiting each of n locations exactly once and returning to the origin. A common binary formulation uses xᵢⱼ = 1 when arc (i, j) is selected. Degree constraints require one incoming and one outgoing arc at each node, but these constraints alone permit disconnected subtours. Subtour-elimination constraints are therefore necessary.

The TSP is NP-hard. In complexity language, no polynomial-time exact algorithm is known, and the problem is believed not to have one. Exact methods include branch-and-bound and branch-and-cut. For large operational instances, heuristics and metaheuristics such as savings methods, local search, tabu search, and genetic algorithms may provide high-quality solutions, although they do not generally certify optimality.

The vehicle-routing problem (VRP) extends the TSP to multiple vehicles and often includes depot constraints, vehicle capacities, time windows, service times, driver regulations, and heterogeneous fleets. These additions increase realism but also complexity. A practical model should include a constraint only when its operational effect justifies the computational and data burden.

A useful distinction is between:

• feasible solution: satisfies all stated constraints;
• optimal solution: has the best objective value among feasible solutions;
• bound: a mathematically justified limit on the best possible objective;
• optimality gap: the difference between an incumbent solution and a bound, usually expressed as a percentage.

For a minimization problem, if a feasible solution has value U and a valid lower bound L, the relative gap may be reported as (U − L)/|U| when U ≠ 0. Solver conventions differ, so the definition should be documented.

7. Spanning Trees and Network Design

A spanning tree of a connected undirected graph connects every node without cycles. A tree with |V| nodes has exactly |V| − 1 edges. A minimum spanning tree (MST) minimizes the total edge weight among all spanning trees.

Kruskal’s algorithm sorts edges by increasing weight and repeatedly adds the next edge that does not create a cycle. With an efficient disjoint-set data structure, its complexity is O(|A| log |A|), dominated by sorting. Prim’s algorithm grows one tree from a starting node, repeatedly adding the least-cost edge connecting the current tree to an unconnected node. With a binary heap, its typical complexity is O(|A| log |V|).

MST models are appropriate when every facility must be connected and cycles are unnecessary, such as designing a basic fibre or utility backbone. They are not appropriate when reliability requires redundant paths, when capacity constraints matter, or when demand must be routed through the network. Those requirements lead to network-design or survivable-network models, often involving integer variables and substantially greater complexity.

8. Integrated Applied Case: Regional Medical-Supply Distribution

Background

The following is an illustrative case. A health authority operates two central warehouses and four hospitals. It must distribute emergency medical kits over a one-week planning horizon. Some shipments can move directly, while others pass through a regional cross-dock. Roads have capacities, and one route is vulnerable to disruption.

Problem

The authority must determine shipment quantities that satisfy hospital requirements at minimum transport and handling cost. The plan must also identify whether the road network has a capacity bottleneck and whether a backup route is economically justified.

Analysis and approach

The warehouses are supply nodes, hospitals are demand nodes, and the cross-dock is a transshipment node. Each arc receives a unit cost and weekly capacity. The authority formulates a minimum-cost-flow model. Hospital demand is represented by negative node balances, warehouse availability by positive balances, and the cross-dock by zero balance.

A separate maximum-flow model is used to test whether the network can physically deliver the total emergency requirement. If maximum flow is below total demand, the min-cut identifies the roads or transfer facilities limiting service. A shortest-path analysis is then used for urgent deliveries, with travel time rather than monetary cost as the arc weight.

Because one road is disruption-prone, the authority evaluates two scenarios: normal operation and closure of that road. The plan is not accepted merely because it is optimal in the normal scenario. It must also be feasible under the defined disruption scenario or include a contingency policy.

Solution interpretation

Suppose the minimum-cost-flow solution uses the cross-dock close to its capacity. This indicates that the cross-dock is economically valuable but operationally sensitive. If the maximum-flow min-cut also contains the cross-dock’s outbound roads, expanding warehouse supply will not increase delivered volume. The authority should compare the cost of expanding the cross-dock, contracting an external carrier, holding local safety stock, or accepting delayed service.

If the model assigns all scarce emergency kits to hospitals according to monetary cost alone, clinical priority constraints may be violated. The optimization model must therefore include service-priority rules, minimum allocations, or a lexicographic objective in which life-critical demand is satisfied before cost minimization.

Outcome and learning points

The case demonstrates that different network problems answer different questions: minimum-cost flow determines economical quantities, maximum flow measures throughput, shortest path selects a route, and matching allocates scarce pairings. Combining these models is often more informative than using one model in isolation.

Key lessons are:

1. Network topology can reveal bottlenecks that cost calculations alone hide.
2. A mathematically optimal solution is only useful if data, capacities, and priorities are credible.
3. Scenario analysis is essential when roads, suppliers, or demand are uncertain.
4. Health-related allocation requires fairness, priority, auditability, and human oversight.

9. Computational Complexity and Algorithm Selection

Algorithm selection depends on graph size, density, data quality, arc weights, and the need for certification. The following summary is a practical guide:

Big-O notation describes asymptotic growth, not exact run time. A theoretically superior algorithm may perform poorly because of memory access, implementation quality, numerical scaling, or the structure of a particular instance. Computational experiments should therefore complement theoretical analysis.

10. Implementation, Governance, and Contemporary Practice

A robust implementation follows a disciplined process:

1. Define the business decision and service requirements.
2. Build and validate the network from authoritative data.
3. Check units, balance, capacities, and disconnected nodes.
4. Solve a small test instance whose answer can be verified manually.
5. Examine feasibility, binding constraints, dual values, and sensitivity.
6. Stress-test demand, costs, capacities, and disruptions.
7. Communicate assumptions and produce an operational execution plan.
8. Monitor actual flows and update the model.

Dual values can be especially informative. In a linear network model, a capacity shadow price estimates the marginal value of relaxing a binding capacity, subject to local validity and unchanged basis assumptions. It should not be interpreted as a permanent strategic value outside the relevant sensitivity range.

Technology has expanded network optimization through cloud solvers, geographic information systems, streaming data, digital twins, and machine-learning forecasts. AI can estimate travel times, demand, failure probabilities, or service durations, while optimization converts those estimates into decisions. Forecast uncertainty must not be confused with optimization certainty: a precise solution to inaccurate predictions may still be poor.

Governance issues include privacy in location data, discrimination in assignment, transparency of automated routing, cybersecurity of infrastructure models, and accountability when a recommendation causes harm. Ethical design may require fairness constraints, protected-service requirements, explainable rules, and a human override. In critical infrastructure, resilience and recovery should be valued alongside nominal cost efficiency.

Challenges and Limitations

Network models simplify reality. Common limitations include:

• deterministic costs despite uncertain travel times and demand;
• aggregate capacity that ignores time-dependent congestion;
• linear costs despite quantity discounts or fixed charges;
• omitted inventory and labour constraints;
• weak data on arc availability and reliability;
• excessive reliance on a single objective;
• computational difficulty after adding logical or nonlinear conditions.

Robust optimization protects against specified uncertainty sets, while stochastic optimization represents probability distributions and recourse decisions. Both require assumptions that should be documented. A scenario model is often more credible than a single forecast, but it does not automatically capture every possible disruption.

Best-Practice Checklist

• Use directed arcs when direction affects feasibility or cost.
• Balance supply and demand explicitly, including dummy nodes only with meaningful costs.
• Verify whether integrality follows from network structure before adding unnecessary binary variables.
• Use Dijkstra only when all arc lengths are nonnegative.
• Add subtour-elimination logic to TSP formulations.
• Distinguish capacity bottlenecks from cost disadvantages.
• Report feasibility, objective value, assumptions, and optimality gap.
• Test sensitivity and disruption scenarios.
• Treat algorithmic outputs as decision support, not unquestionable decisions.

Chapter Summary

Network and combinatorial optimization represents movement, allocation, connection, and routing decisions through graphs. The minimum-cost-flow framework unifies transportation and transshipment models using flow conservation, arc costs, and capacities. Assignment and matching models allocate agents to tasks, with the Hungarian algorithm providing an efficient solution for classical assignment problems. Shortest-path algorithms find minimum-cost routes, while maximum-flow and minimum-cut analysis identify throughput and bottlenecks. TSP and vehicle-routing models address tours and fleet operations but are generally computationally difficult. Minimum spanning trees connect all nodes at minimum total edge cost when redundancy and capacity are not required.

Network structure can produce integral solutions and enable specialized algorithms, but side constraints may remove these advantages. Computational complexity should guide algorithm choice, and practical implementation requires validated data, scenario analysis, sensitivity interpretation, and governance. In business analytics, the best network solution is not merely the cheapest mathematical answer; it is a feasible, explainable, resilient, and ethically acceptable decision.

Key Terms

Arc: A directed connection from one node to another.

Assignment problem: A one-to-one allocation of agents to tasks.

Bipartite graph: A graph whose nodes are divided into two sets, with edges only between sets.

Capacity: The maximum flow permitted on an arc or through a facility.

Cycle: A closed sequence of connected edges or arcs.

Flow conservation: The requirement that inflow, outflow, supply, and demand balance at each node.

Maximum flow: The greatest quantity that can move from a source to a sink under capacity limits.

Minimum cut: The least-capacity partition separating a source from a sink.

Minimum-cost flow: A flow satisfying balances and capacities at minimum total cost.

Minimum spanning tree: A least-weight tree connecting all nodes of an undirected graph.

Matching: A set of edges with no shared endpoint.

Network simplex: A specialized simplex method for network-flow models.

Node: A location, entity, or activity in a network.

Shortest path: A least-cost path between specified nodes.

Subtour: A disconnected cycle occurring within a routing solution.

Total unimodularity: A matrix property that supports integral extreme-point solutions with integral right-hand sides.

Transportation problem: Shipment allocation from multiple sources to multiple destinations.

Transshipment: Movement through intermediate nodes before reaching final destinations.

Vehicle-routing problem: Routing multiple vehicles subject to operational constraints.

Review Questions

Short Answer Questions

1. What is the role of node-balance constraints in a minimum-cost-flow model?
2. Why can a transportation problem require a dummy source or destination?
3. Under what condition is Dijkstra’s algorithm valid?
4. What does a minimum cut reveal in a capacitated network?
5. Why do TSP formulations need subtour-elimination constraints?

Long Answer Questions

1. Formulate a transshipment model and explain how it differs from a direct transportation model.
2. Compare the Hungarian algorithm, Dijkstra’s algorithm, and Kruskal’s algorithm in terms of problem type and assumptions.
3. Explain total unimodularity and its significance for network optimization.
4. Discuss why vehicle-routing problems are more difficult than classical shortest-path problems.
5. Evaluate the governance risks of using predictive analytics within an automated assignment model.

Analytical / Application Questions

1. A distribution network has adequate total supply but cannot satisfy all customer demand because of road capacities. Explain how maximum-flow and minimum-cut analysis would diagnose the problem and guide investment.
2. A hospital must assign nurses to shifts using predicted performance scores, but some shifts are legally required to meet minimum staffing levels. Design an assignment-based model and identify fairness and governance constraints.
3. A logistics firm faces uncertain travel times and occasional road closures. Recommend a modeling and solution strategy that combines shortest-path analysis, scenario testing, and operational resilience.

Multiple Choice Questions with Answers

Question 1

In a balanced transportation problem, which constraint ensures that each destination receives its required quantity?

A. The source-capacity constraint

B. The destination-demand constraint

C. The subtour-elimination constraint

D. The minimum-cut constraint

Correct Answer: B. The destination-demand constraint

Question 2

Dijkstra’s algorithm is guaranteed to produce correct shortest paths when arc lengths are:

A. All negative

B. Nonnegative

C. Randomly distributed

D. Equal to zero only

Correct Answer: B. Nonnegative

Question 3

The maximum-flow/minimum-cut theorem states that maximum flow equals:

A. The number of nodes

B. The sum of all arc costs

C. The capacity of the minimum source–sink cut

D. The shortest-path length

Correct Answer: C. The capacity of the minimum source–sink cut

Question 4

Which algorithm is classically used for the square assignment problem?

A. Hungarian algorithm

B. Floyd–Warshall algorithm

C. Kruskal’s algorithm

D. Bellman–Ford algorithm

Correct Answer: A. Hungarian algorithm

Question 5

A spanning tree of a connected graph with |V| nodes contains:

A. |V| edges

B. |V| + 1 edges

C. |V| − 1 edges

D. 2|V| edges

Correct Answer: C. |V| − 1 edges

Question 6

What is the principal reason that a basic TSP degree formulation may be infeasible as a tour description?

A. It has no cost coefficients

B. It may contain disconnected subtours

C. It requires negative arc costs

D. It cannot represent binary decisions

Correct Answer: B. It may contain disconnected subtours

Question 7

In a minimum-cost-flow model, a transshipment node normally has:

A. Outflow greater than inflow with no supply

B. Inflow equal to outflow

C. Demand greater than total network supply

D. No incident arcs

Correct Answer: B. Inflow equal to outflow

Question 8

For the transportation example in the chapter, the cost of the displayed feasible plan is:

A. 400

B. 440

C. 460

D. 500

Correct Answer: C. 460

Question 9

Which problem is generally NP-hard in its standard form?

A. Minimum spanning tree

B. Classical assignment

C. Travelling salesperson problem

D. Single-source shortest path with nonnegative lengths

Correct Answer: C. Travelling salesperson problem

Question 10

If a network’s minimum cut has capacity below required demand, the most direct interpretation is that:

A. The demand is automatically reduced

B. The network has a throughput bottleneck

C. All arc costs are incorrect

D. The shortest path is optimal for every shipment

Correct Answer: B. The network has a throughput bottleneck