Exact Optimization Methods

Introduction and Context

Route planning and scheduling decisions determine how vehicles, crews, containers, and delivery windows are assigned over time and space. These decisions are difficult because they combine network structure, scarce resources, precedence relationships, service requirements, uncertainty, and combinatorial alternatives. A small vehicle-routing problem may have thousands of feasible sequences; a national distribution problem may have an astronomically large solution space.

Exact optimization methods seek a provably optimal solution, or a mathematically certified bound on how far a computational solution may be from optimality. This distinguishes them from heuristics and metaheuristics, which may find excellent solutions quickly but generally cannot certify optimality. Exact methods are therefore valuable when decisions are high-value, regulations require defensibility, or the problem is small or structured enough for rigorous optimization.

This chapter develops linear programming (LP), integer programming (IP), mixed-integer programming (MIP), dynamic programming, branch-and-bound, branch-and-cut, decomposition, and column generation. It also explains computational limits: an optimality certificate is meaningful only relative to a correctly formulated model, credible data, and a tractable computational experiment.

Learning Objectives

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

1. Formulate route and scheduling decisions as LP, IP, and MIP models.
2. Explain why integrality creates computational difficulty.
3. Apply dynamic programming and interpret its state-space requirements.
4. Explain branch-and-bound, valid inequalities, branch-and-cut, and optimality gaps.
5. Distinguish decomposition and column generation and identify when each is useful.
6. Evaluate model assumptions, computational limits, and the managerial meaning of an optimal solution.

1. Modeling Route and Scheduling Decisions

A mathematical optimization model has four essential components: decision variables, an objective function, constraints, and parameter data. Let a directed transportation network be represented by nodes i and arcs (i,j). A typical binary routing variable is:

The variable is dimensionless and is meaningful only when i ≠ j. Let c_{ij} be the cost of traversing arc (i,j), measured in currency, distance, time, or a weighted combination. A basic route-cost objective is:

This objective assumes that arc costs are additive and known. If cost includes fuel, tolls, driver wages, and emissions, c_{ij} should be defined consistently, or separate objectives and constraints should be used.

For a capacitated vehicle-routing problem, q_i denotes demand at customer i, Q denotes vehicle capacity, and y_{ij} may represent the number of vehicles using arc (i,j). Degree constraints can be written as:

These constraints ensure one arrival and one departure, but do not by themselves prevent disconnected subtours. A subtour-elimination constraint for every nonempty proper subset S of customers is:

The constraint is valid because a cycle entirely within S would contain |S| selected internal arcs. The exponential number of possible subsets makes direct enumeration impractical; this motivates cutting-plane algorithms and separation procedures.

Capacity may be represented by flow variables or by strengthened inequalities. A common aggregate form for a vehicle beginning at depot 0 is:

for symmetric tours when each route must enter and leave S. This inequality assumes that customers in S require total demand ∑q_i, vehicle capacity is Q, and each crossing can support at most Q units. It is not universally valid for every directed or split-delivery variant, so the routing convention must be checked first.

Linear, integer, and mixed-integer models

An LP permits continuous variables. For example, a shipment variable f_{ij} ≥ 0 can represent flow in tonnes on arc (i,j). An IP requires all decision variables to be integer, often binary. A MIP combines continuous and discrete variables, such as continuous arrival times and binary sequencing decisions.

A generic MIP is:

Here x is a vector of continuous variables, y is a vector of binary variables, A and B are coefficient matrices, b is a right-hand-side vector, and c and d are objective coefficients. The objective and constraints must be linear in the variables. Products such as x_{ij}t_i are nonlinear unless reformulated or otherwise handled.

Binary variables are appropriate for yes-or-no decisions, such as whether a vehicle uses an arc. Integer variables are appropriate for counts, such as the number of vehicles assigned to a depot. Continuous variables are appropriate for quantities such as load, time, or flow when fractional values are physically meaningful.

2. Scheduling Formulations

Scheduling models often combine assignment, sequencing, and time feasibility. Let s_i be the service-start time at customer i, p_i its service duration, and t_{ij} travel time from i to j. If i immediately precedes j, then:

M is a sufficiently large constant. When x_{ij}=1, the usual precedence relation is enforced; when x_{ij}=0, the constraint is relaxed. M must be large enough to preserve every feasible schedule but not unnecessarily large, because excessive M values weaken the LP relaxation and can cause numerical instability.

For a time window [a_i,b_i]:

If lateness is allowed, let L_i ≥ 0 be lateness and impose s_i ≤ b_i + L_i. A penalty λ_iL_i can be included in the objective. The units of s_i, p_i, t_{ij}, a_i, b_i, and L_i must be consistent, for example minutes from the start of the planning horizon.

An alternative to big-M sequencing is a disjunctive formulation. For two jobs i and j processed on one machine, either i precedes j or j precedes i. Binary order variables express this disjunction. Indicator constraints, supported by many modern solvers, can improve readability and sometimes numerical performance, although their internal implementation still requires a valid mathematical representation.

3. Linear Programming Relaxation and Bounds

The LP relaxation of a MIP is obtained by replacing binary restrictions y ∈ {0,1} with 0 ≤ y ≤ 1. For a minimization problem, the relaxation has a feasible region containing the integer feasible region. Consequently:

where Z_LP is the optimal relaxation value and Z_IP is the optimal integer value, provided the problem is a minimization problem. For maximization, the inequality reverses.

The relaxation supplies a lower bound for minimization and is central to exact algorithms. If the LP solution happens to be integral, it is also an optimal solution to the IP. If it is fractional, it may still provide a useful bound, but it is not implementable as a route plan.

For a feasible incumbent integer solution with objective value Z_inc and a lower bound Z_LB in a minimization problem, the relative optimality gap can be reported as:

provided Z_inc ≠ 0. A solver may use a different denominator or absolute-gap convention, so reported solver documentation should be consulted. If Z_inc = 10,000 and Z_LB = 9,800, the gap is 2%. This certifies that the incumbent is no more than 2% above the bound under the stated convention; it does not prove that its practical cost is 2% above the unknown optimum exactly.

4. Dynamic Programming

Dynamic programming (DP) solves a problem by decomposing it into stages and states. It is applicable when a problem has optimal substructure: an optimal complete solution contains optimal solutions to relevant subproblems. It also relies on a manageable state representation.

For a shortest-path problem, let V_i be the minimum cost from origin to node i. If A(i) is the set of predecessors of i, the Bellman recursion is:

with V_origin = 0. This recursion is valid for an acyclic network or for settings where the algorithm used correctly handles nonnegative cycles and termination conditions.

For a knapsack-style loading subproblem, let F(k,w) be the maximum value using the first k items and capacity w. With item weight a_k and value v_k:

when a_k ≤ w; otherwise F(k,w)=F(k−1,w). The state space has approximately O(nQ) states when capacity Q is an integer, which is pseudo-polynomial rather than polynomial in the length of the binary encoding of Q.

In vehicle routing, a classical subset DP uses a state (S,i), where S is the set of visited customers and i is the last customer visited. Its scale is approximately O(n²2^n), which becomes prohibitive as n grows. DP can nevertheless be powerful for elementary shortest paths with resource constraints, provided dominance rules eliminate states that are no better than another state using fewer resources or lower cost.

A label A dominates label B if A reaches the same node, uses no more of every constrained resource, and has no greater cost, with at least one strict improvement. B can then be discarded without removing an optimal solution. Dominance is exact only when the comparison includes every resource relevant to future feasibility and cost.

5. Branch-and-Bound

Branch-and-bound systematically partitions the integer feasible region. At each node of a search tree, some variables are fixed or restricted. The algorithm solves a relaxation to obtain a bound, then applies three tests:

1. Infeasibility: discard the node if its relaxation is infeasible.
2. Bound dominance: for minimization, discard the node if its lower bound is at least the incumbent value.
3. Integrality: if the relaxation is integral, update the incumbent if appropriate.

Otherwise, the node is branched, often by imposing y_k=0 in one child and y_k=1 in another. The global lower bound is the best lower bound among active nodes. When the incumbent and global bound coincide, optimality is certified.

Branching strategy strongly affects performance. Most-fractional branching selects a variable near 0.5; strong branching tentatively evaluates candidate branches; pseudocost branching uses historical information to predict bound improvement. Node selection may be depth-first, which finds incumbents quickly, or best-bound, which emphasizes proof of optimality.

A key professional distinction is between finding a feasible solution and proving it optimal. A solver may find a high-quality route quickly but spend most of its time proving that no slightly better route exists. In operational settings, a time-limited solution with a documented gap may be preferable to an unqualified claim of optimality.

6. Branch-and-Cut and Valid Inequalities

Branch-and-cut combines branch-and-bound with cutting planes. A valid inequality removes fractional solutions without removing any feasible integer solution. If the current LP solution violates such an inequality, the inequality is added and the relaxation is re-solved.

For routing, subtour-elimination inequalities are classic cuts. Capacity cuts, clique inequalities, cover inequalities, and precedence cuts can also strengthen models. A cut is useful when it substantially improves the bound at reasonable computational cost. Adding every theoretically valid inequality is not necessarily beneficial: the LP may become large, separation may be expensive, and numerical conditioning may deteriorate.

The separation problem asks whether a violated valid inequality can be found for the current fractional solution. Efficient separation algorithms are a major reason branch-and-cut works well in practice. For example, min-cut calculations can identify violated capacity constraints in certain network-routing formulations.

Model strengthening should precede algorithmic sophistication. Tight variable bounds, symmetry reduction, valid inequalities, realistic time horizons, and careful scaling often yield larger benefits than changing solver settings. Symmetry is especially harmful when interchangeable vehicles generate many equivalent solutions. Vehicle-indexing restrictions or symmetry-breaking inequalities can reduce redundant search.

7. Decomposition Methods

Decomposition exploits structure by separating a large model into coordinated subproblems.

Benders decomposition

Benders decomposition is appropriate when complicating variables are often strategic or discrete, while the remaining operational variables form an LP once those decisions are fixed. The master problem selects complicating decisions; a subproblem checks feasibility and evaluates operational cost. If the subproblem is infeasible, a feasibility cut is added. If feasible, an optimality cut transfers information to the master.

In a distribution example, the master may choose depot openings and vehicle assignments, while the subproblem routes flow through the selected network. Benders is attractive when the subproblem is much easier than the full MIP and when cuts are strong enough to guide the master.

Dantzig–Wolfe decomposition and column generation

Dantzig–Wolfe reformulates a problem using columns representing complete patterns. In vehicle routing, a column may be a feasible route r. Let a_{ir}=1 if route r serves customer i, c_r be its cost, and λ_r indicate whether route r is selected:

R may contain an enormous number of feasible routes, so they are not all generated initially. The restricted master problem uses a small route subset. Dual prices from the LP master define a pricing problem that searches for a route with negative reduced cost.

If π_i is the dual price for customer coverage and π_0 is associated with the vehicle limit, the reduced cost of route r has the form:

The exact sign and terms depend on the master formulation. A route with c̄_r < 0 can improve a minimization master and is added as a new column. The pricing problem is commonly an elementary shortest-path problem with resource constraints, solved by labeling DP or specialized algorithms.

Column generation solves the LP relaxation. To obtain integer solutions, it must be embedded in branch-and-price, often with branching rules designed not to destroy the pricing structure. Stabilization techniques, dual bounds, and careful pricing accuracy are important because unstable dual values can cause slow convergence.

Lagrangian relaxation

Lagrangian relaxation moves difficult constraints into the objective with multipliers. If a constraint g(x) ≤ 0 is relaxed, the Lagrangian objective for a minimization problem may be written:

For every u ≥ 0, L(u) is a lower bound when the original problem is a minimization problem and the relaxed constraint has the stated orientation. Optimizing multipliers gives the Lagrangian dual bound. The relaxed problem may decompose by vehicle, customer, time period, or commodity. Lagrangian relaxation can produce strong bounds and useful heuristics, but the dual bound need not equal the integer optimum.

8. Worked Example: A Small Exact Route Model

Consider a depot 0 and customers A, B, and C. Two identical vehicles are available, each with capacity 10. Demands are q_A=4, q_B=3, and q_C=5. Every customer must be served once, and split deliveries are prohibited. The route alternatives and costs are:

Assume each listed route begins and ends at the depot and is feasible with respect to time windows. A set-partitioning model chooses routes:

subject to:

At most two routes are available, but this is automatically satisfied by the best feasible combinations here. Candidate combinations include r₁+r₆ with cost 18+12=30, r₂+r₅ with cost 20+10=30, and r₃+r₄ with cost 19+11=30. Thus the optimal cost is 30, with three alternative optimal route plans. This example illustrates why route-based formulations can expose operational alternatives clearly, while a full arc formulation would need additional constraints to ensure route connectivity and capacity.

If the LP relaxation produced a lower bound of 28.5 before integrality was enforced, any integer solution of cost 30 would have a gap of (30−28.5)/30×100%=5%. Once the solver proves that no active node can improve 30, the exact optimum is certified.

9. Illustrative Case: Regional Medical Deliveries

Background. A regional health distributor serves 42 clinics from two warehouses. Vehicles have capacity limits, drivers work eight-hour shifts, and clinics specify delivery windows. Missed windows create substantial service penalties, while refrigerated products require route duration limits.

Problem. The existing planning process used manually adjusted routes. It produced feasible plans but offered no evidence that vehicle count, mileage, and late-delivery penalties were jointly minimized. Management also needed an explainable method for evaluating whether adding a third warehouse would improve service.

Analysis. The planning team formulated a MIP with binary arc-use variables, continuous arrival times, vehicle-use variables, load-flow variables, and lateness variables. Capacity and time-window constraints were included. A direct arc model was initially slow because of weak subtour structure and symmetric vehicles.

Approach and solution. The team first tightened variable bounds using shift and refrigeration limits, added capacity and subtour cuts, and imposed symmetry-breaking rules on identical vehicles. For larger weekly instances, it used a route-based master with column generation. The pricing problem was an elementary shortest-path problem with capacity, duration, and time-window resources. Branch-and-price was used for instances requiring integer certification. For tactical warehouse analysis, Benders decomposition separated warehouse-selection decisions from routing operations.

Outcome. The organization obtained a feasible plan quickly and used the optimality gap to control run time. Small daily instances were solved to proven optimality; larger weekly instances were reported with a documented gap and sensitivity analysis. The model identified that a third warehouse reduced mileage but did not justify its fixed cost under ordinary demand; under a high-service scenario, however, it reduced lateness enough to become economically attractive.

Learning points. Exact optimization improved not merely route distance but the transparency of trade-offs. The result depended on data quality, realistic service times, and explicit treatment of refrigeration and labor rules. A mathematically optimal plan under incorrect travel-time assumptions would still be operationally poor.

10. Assessing Computational Limits and Solution Quality

Exact optimization is limited by both theory and implementation. Mixed-integer routing is generally combinatorial and, for important problem families, NP-hard. This means that no known algorithm guarantees polynomial-time solution for all instances; it does not mean that every practical instance is difficult or that exact methods are unusable.

Important sources of computational difficulty include:

• number of customers, vehicles, periods, and resources;
• weak LP relaxations;
• excessive symmetry;
• large or poorly chosen big-M constants;
• many nearly equivalent routes;
• tight time windows and multiple resources;
• numerical scaling and inaccurate data;
• expensive pricing or separation subproblems.

A credible computational report should state the formulation, solver and version, hardware, time limit, feasibility status, incumbent objective, bound, gap convention, and whether all constraints were enforced. It should distinguish a proven optimum from a time-limited incumbent. Sensitivity analysis should vary demand, travel time, service duration, and penalty assumptions.

The objective function also deserves scrutiny. A single weighted objective can hide unacceptable service outcomes. Better practice may impose hard constraints for regulatory or customer requirements, then optimize cost within that feasible region. Multiobjective methods, lexicographic priorities, ε-constraints, or Pareto analysis can expose trade-offs between cost, emissions, reliability, and workload.

11. Governance, Ethics, and Technology

Exact route models can allocate overtime, workload, difficult customers, and service priority. Governance therefore requires more than mathematical correctness. Managers should document data sources, constraint interpretations, exceptions, and approval rights. Driver safety, legal hours, accessibility, and nondiscrimination constraints should be modeled explicitly rather than treated as informal preferences.

AI and machine learning can support exact optimization by forecasting demand, estimating travel times, detecting anomalous data, or generating warm starts. They do not replace optimization: a predictive model estimates parameters, whereas an optimization model selects actions under constraints. Forecast uncertainty should be represented through scenarios, robust optimization, chance constraints, or replanning policies where appropriate. Automated decisions should remain auditable, and planners should be able to override a mathematically feasible plan when exceptional conditions arise.

12. Best-Practice Workflow

A disciplined workflow is:

1. Define the decision horizon, units, stakeholders, and service commitments.
2. Build the smallest correct formulation before adding detail.
3. Validate conservation, capacity, time, and route-connectivity logic on tiny instances.
4. Solve the LP relaxation and inspect fractional patterns and bound strength.
5. Tighten bounds and add valid inequalities supported by the model structure.
6. Select DP, branch-and-cut, decomposition, or column generation according to structure.
7. Use a feasible heuristic or warm start to obtain an incumbent quickly.
8. Track incumbent, bound, gap, run time, and infeasibility explanations.
9. Stress-test uncertain data and compare alternative objective priorities.
10. Communicate both the route plan and the limits of its optimality claim.

Chapter Summary

Exact optimization methods provide a rigorous framework for route planning and scheduling. LP models continuous flows and supplies relaxations; IP and MIP represent indivisible assignments, sequencing, and vehicle-use decisions. Dynamic programming exploits staged structure and optimal subproblems but can suffer from exponential or pseudo-polynomial state spaces. Branch-and-bound searches a partitioned feasible region using relaxation bounds, while branch-and-cut strengthens that search with valid inequalities. Benders decomposition separates complicating decisions from operational subproblems. Dantzig–Wolfe decomposition and column generation represent complete routes as columns and generate only promising patterns; branch-and-price adds integrality. Lagrangian relaxation produces decomposable bounds by penalizing difficult constraints.

Optimality must be interpreted together with feasibility, data quality, numerical stability, computational gap, and managerial priorities. In practice, a documented near-optimal solution with strong validation may be more useful than an unverified claim of optimality. The central professional skill is matching formulation and algorithm to operational structure while communicating what has—and has not—been proved.

Key Terms

Linear programming: Optimization with continuous variables, linear objectives, and linear constraints.

Integer programming: Optimization requiring some or all variables to take integer values.

Mixed-integer programming: A model containing both continuous and integer variables.

LP relaxation: The model obtained by replacing integer restrictions with continuous bounds.

Incumbent: The best feasible integer solution found so far.

Optimality gap: A measure of the difference between an incumbent and a valid bound.

Branch-and-bound: A search method that partitions the feasible region and prunes by bounds or infeasibility.

Branch-and-cut: Branch-and-bound strengthened with valid inequalities.

Valid inequality: A constraint satisfied by every feasible integer solution.

Subtour: A disconnected cycle in a routing solution.

Dynamic programming: Optimization by recursively solving overlapping subproblems.

State: Information required to characterize a DP subproblem.

Dominance: A condition allowing an inferior DP label or state to be discarded safely.

Benders decomposition: Separation of complicating decisions and resulting operational subproblems.

Column generation: Iterative addition of improving variables or route patterns.

Pricing problem: The subproblem that identifies a column with improving reduced cost.

Reduced cost: The objective improvement measure for a variable relative to dual prices.

Lagrangian relaxation: Penalization of selected constraints in the objective.

Big-M: A sufficiently large modeling constant used to activate or deactivate conditional constraints.

Symmetry breaking: Constraints or strategies that eliminate equivalent representations of the same solution.

Review Questions

Short Answer Questions

1. Why does an LP relaxation provide a lower bound for a minimization MIP?
2. What routing problem is addressed by subtour-elimination constraints?
3. State the three main pruning conditions in branch-and-bound.
4. What is the purpose of a pricing problem in column generation?
5. Why can an excessively large big-M value be harmful?

Long Answer Questions

1. Formulate a capacitated vehicle-routing model and explain the role of assignment, capacity, time, and connectivity constraints.
2. Compare dynamic programming, branch-and-bound, and branch-and-cut in terms of structure, bounds, and computational effort.
3. Explain Benders decomposition and give a route-planning example in which it is appropriate.
4. Describe how a route-based set-partitioning formulation can be solved using column generation.
5. Discuss why a mathematically optimal route plan may still be operationally inappropriate.

Analytical / Application Questions

1. A minimization model has an incumbent cost of 46,000 and a valid lower bound of 44,850. Calculate the relative optimality gap and explain its managerial interpretation.
2. A delivery model contains identical vehicles, weak time bounds, and many disconnected fractional cycles. Recommend formulation-strengthening and algorithmic actions, and justify each.
3. Design an exact optimization approach for a distribution network with depot-opening decisions, vehicle capacities, time windows, and uncertain travel times. Explain where decomposition, column generation, or robust constraints could be used.

Multiple Choice Questions with Answers

Question 1

For a minimization MIP, which statement about the LP relaxation is correct?

A. Its objective value is always an upper bound on the integer optimum.

B. Its objective value is a lower bound on the integer optimum.

C. It is infeasible whenever the MIP is feasible.

D. It must produce an integer solution.

Correct Answer: B. Its objective value is a lower bound on the integer optimum.

Question 2

If an incumbent minimization solution is 10,000 and the valid lower bound is 9,800, what is the relative gap using (incumbent − bound)/incumbent?

A. 0.2%

B. 1%

C. 2%

D. 20%

Correct Answer: C. 2%

Question 3

Which condition allows a branch-and-bound node to be pruned in a minimization problem?

A. Its lower bound is at least the incumbent value.

B. Its relaxation has a fractional solution.

C. It contains an unfixed binary variable.

D. Its objective coefficients are positive.

Correct Answer: A. Its lower bound is at least the incumbent value.

Question 4

What is the principal purpose of a subtour-elimination constraint?

A. To increase vehicle capacity

B. To prevent disconnected customer cycles

C. To estimate travel times

D. To convert continuous time into integer time

Correct Answer: B. To prevent disconnected customer cycles

Question 5

In column generation for a minimization master problem, which route is normally added?

A. A route with positive reduced cost

B. A route with zero demand

C. A route with negative reduced cost

D. A route that violates all resource constraints

Correct Answer: C. A route with negative reduced cost

Question 6

Which method is especially associated with separating depot-opening decisions from routing operations?

A. Benders decomposition

B. Shortest-path labeling only

C. Simple sorting

D. Inventory averaging

Correct Answer: A. Benders decomposition

Question 7

In dynamic programming, a dominance rule is safe when one label has no greater cost and uses no more of every resource than another label at the same relevant state.

A. True only for maximization problems

B. False because labels may never be discarded

C. True under the stated state and resource conditions

D. True only when all costs are negative

Correct Answer: C. True under the stated state and resource conditions

Question 8

Why can excessive big-M values impair a MIP computation?

A. They eliminate all feasible solutions.

B. They may weaken the relaxation and create numerical instability.

C. They guarantee integer LP solutions.

D. They remove the need for time-window constraints.

Correct Answer: B. They may weaken the relaxation and create numerical instability.

Question 9

Which formulation is most directly associated with selecting complete feasible routes as variables?

A. Set-partitioning formulation

B. Unconstrained regression formulation

C. Pure inventory-balance formulation

D. Single-machine queue formula

Correct Answer: A. Set-partitioning formulation

Question 10

A time-limited solver returns a feasible plan with a documented 3% optimality gap. What is justified?

A. The plan is exactly optimal.

B. No plan can be better than the incumbent.

C. The plan is within the solver's certified bound under the stated gap convention.

D. The data must be error-free.

Correct Answer: C. The plan is within the solver's certified bound under the stated gap convention.