Optimization and Decision-Modelling Foundations

Introduction

Logistics managers routinely decide how much to ship, which facilities to use, which routes to assign, how to allocate scarce vehicles, and how to balance cost against service, risk, emissions, and resilience. These decisions are interdependent: a cheaper route may increase delivery time; opening an additional warehouse may reduce transport distance but increase fixed cost; and a plan that is optimal under average demand may be fragile under disruption.

Optimization models provide a disciplined way to represent such decisions. A model does not replace managerial judgment. Rather, it makes assumptions explicit, identifies trade-offs, exposes infeasibility, and supports transparent comparison of alternatives. This chapter develops foundations for linear programming, integer and mixed-integer programming, network models, multi-objective optimization, nonlinear models, sensitivity analysis, heuristics, and solver-based decision support.

Learning Objectives

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

1. Formulate logistics problems using objective functions, decision variables, constraints, and parameters.
2. Distinguish linear, integer, mixed-integer, network, multi-objective, and nonlinear models.
3. Formulate and interpret shortest-path, minimum-cost-flow, and maximum-flow models.
4. Explain sensitivity analysis, dual values, reduced costs, and the value of information.
5. Select suitable exact or heuristic solution methods.
6. Critically evaluate model assumptions, data quality, governance, and implementation risks.

1. The Structure of a Decision Model

A mathematical optimization model consists of four basic elements:

• Parameters: known or estimated inputs, such as demand, capacity, distance, cost, and emissions.
• Decision variables: controllable quantities, such as shipment volume, vehicle assignment, or facility opening.
• Objective function: the criterion to minimize or maximize.
• Constraints: physical, contractual, regulatory, or managerial limitations.

A general minimization model can be written as:

Here, x is the vector of decisions, f(x) is the objective, g_r(x) and h_s(x) represent inequality and equality constraints, and X specifies domains such as nonnegative, integer, or binary values. A feasible solution satisfies every constraint. An optimal solution is a feasible solution with the best objective value according to the stated model.

A model is useful only if its abstraction is appropriate. Excessive detail may make a model impossible to solve or difficult to maintain; excessive simplification may produce an operationally misleading answer. Model design is therefore an iterative process involving managers, data specialists, operations experts, and decision-makers.

2. Linear Programming in Logistics

A linear program (LP) assumes that the objective and constraints are linear functions of continuous decision variables. Consider a transportation problem with suppliers i = 1,…,m and customers j = 1,…,n. Let:

• x_ij = units shipped from supplier i to customer j;
• c_ij = cost per unit shipped;
• s_i = supply available at supplier i;
• d_j = demand at customer j.

The balanced transportation model is:

The units are monetary units in the objective and product units in the constraints. The equality demand constraint assumes all demand must be met. If shortages are permitted, a shortage variable can be introduced and penalized in the objective.

Worked Example: Transportation Allocation

A supplier has 40 units and a second supplier has 60 units. Two customers require 30 and 50 units respectively. Shipping costs are:

Total supply is 100 units, while total demand is 80 units. The low-cost allocation sends 30 units from Supplier 1 to Customer 1 and 50 units from Supplier 2 to Customer 2. The remaining 20 units of supply are unused. The transportation cost is:

30 × 4 + 50 × 3 = 270 monetary units.

This allocation is optimal for the stated data because each customer is served by its cheaper supplier and sufficient supply exists. In a larger problem, a solver is preferable because local route comparisons may fail to identify the globally optimal allocation.

3. Integer and Mixed-Integer Models

Continuous variables are inappropriate when decisions involve indivisible objects. Integer programming requires selected variables to take integer values. Binary variables take values 0 or 1 and are particularly useful for yes/no decisions.

For facility location, let:

• y_i ∈ {0,1} indicate whether facility i is opened;
• x_ij ≥ 0 be the quantity shipped from facility i to customer j;
• F_i be the fixed opening cost;
• c_ij be the unit distribution cost;
• K_i be facility capacity;
• d_j be customer demand.

A capacitated facility-location model is:

The linking constraint ∑ⱼx_ij ≤ K_i y_i prevents shipments from a closed facility. If y_i = 0, its right-hand side is zero; if y_i = 1, shipments may reach capacity K_i.

Mixed-integer linear programming (MILP) combines continuous, integer, and binary variables. Typical applications include vehicle routing, fleet sizing, order batching, scheduling, cross-docking, and network design.

Modeling Logic Carefully

A common error is to use a large constant, known as a big-M, without a valid upper bound. For example, x ≤ My links a continuous activity x to binary variable y. The value of M must be no larger than a legitimate maximum for x. An excessively large value can cause numerical instability and weak computational bounds. Whenever possible, indicator constraints or tighter data-derived bounds should be used.

MILPs are commonly solved by branch-and-bound or branch-and-cut. The continuous relaxation removes integrality restrictions and gives a bound on the best possible integer solution. Branching partitions the search space; cutting planes add valid inequalities that eliminate fractional solutions without excluding feasible integer solutions.

4. Network Optimization Models

A logistics network can be represented as a directed graph G = (N,A), where N is the set of nodes and A is the set of directed arcs. Arcs may represent roads, rail links, pipelines, or shipping lanes. Network models are powerful because their structure often enables efficient algorithms.

4.1 Shortest Path

Let c_ij be the travel cost or time on arc (i,j), and let x_ij equal 1 when arc (i,j) is selected. A shortest-path model from origin o to destination [[MATH,t]] is:

The conservation equations create one unit of flow from origin to destination. Dijkstra’s algorithm applies when all arc costs are nonnegative. Bellman–Ford can handle negative arc costs but not a negative-cost cycle reachable from the origin.

4.2 Minimum-Cost Flow

Minimum-cost flow generalizes transportation and shortest-path problems. Let b_i be the net supply at node i, positive for a supply node and negative for a demand node. Let u_ij be arc capacity. The model is:

Feasibility requires that total supply equals total demand, so ∑ᵢb_i = 0. This model supports transshipment, where intermediate nodes neither create nor consume net flow.

4.3 Maximum Flow

Maximum-flow models maximize the quantity moved from a source s to a sink t, subject to arc capacities. With flow x_ij and capacity u_ij:

The maximum-flow/minimum-cut theorem states that the maximum feasible flow equals the capacity of the minimum cut separating source and sink. Operationally, a cut identifies a bottleneck: increasing capacity elsewhere cannot improve throughput unless the limiting cut is expanded.

Figure: A directed logistics network in which a cut can reveal the system bottleneck.

5. Multi-Objective Optimization

Logistics decisions rarely have one legitimate objective. Cost, delivery time, service reliability, carbon emissions, safety, and employment may all matter. A weighted-sum model is:

where f_k(x) is objective k and w_k ≥ 0 is its weight. Objectives should be normalized before weighting when they have different units. One common normalization for a minimization objective is:

The best and worst reference values must be defined consistently. Weights are not objective probabilities; they express decision-maker preferences or policy priorities. A weighted sum may fail to generate non-convex portions of a Pareto frontier. The ε-constraint method instead optimizes one primary objective while imposing bounds on others, such as minimize cost subject to emissions ≤ ε.

A solution is Pareto-efficient if no objective can improve without worsening at least one other objective. Managers should inspect the frontier rather than accept a single result without understanding the trade-off.

6. Nonlinear and Stochastic Models

Nonlinear programming is appropriate when relationships are nonlinear, such as quantity discounts, congestion, economies of scale, fuel consumption, or risk functions. A nonlinear model may be written as:

If the objective and feasible region are convex, a local optimum is also a global optimum under standard regularity conditions. Nonconvex models may contain multiple local optima and require global optimization, decomposition, or carefully designed heuristics.

Uncertainty can be represented through scenarios. In a two-stage stochastic model, first-stage decisions are made before uncertainty is known, while recourse decisions are made afterward. A simplified objective is:

where x is the first-stage decision, y_s is the scenario-dependent recourse decision, p_s is the probability of scenario s, and ∑ₛp_s = 1. Probabilities should be evidence-based and sensitivity-tested; false precision can make a stochastic model appear more reliable than its data justify.

7. Sensitivity and Post-Optimal Analysis

An optimal solution is conditional on input values. Sensitivity analysis examines how changes in costs, demand, capacity, or constraints affect the solution.

For an LP, the shadow price or dual value of a constraint estimates the marginal change in optimal objective value from increasing its right-hand side by one unit, within the allowable range and assuming the current basis remains valid. For a minimization problem, a positive shadow price for capacity usually means that one additional unit of capacity increases the minimum cost; however, sign conventions depend on model formulation.

The reduced cost of a nonbasic variable indicates how much its objective coefficient must improve before it can enter an optimal basis, subject to standard LP assumptions. These interpretations do not automatically transfer to MILPs, where discrete changes can cause discontinuities.

A useful managerial measure is the value of perfect information (VPI), conceptually defined as:

For a cost-minimization problem, the sign and presentation should be interpreted as a nonnegative potential saving. In practice, the value of information should be compared with the cost of obtaining better forecasts or data.

8. Exact Algorithms, Heuristics, and Solver Practice

Exact methods seek a provably optimal solution or a certified bound. LP solvers use algorithms such as simplex or interior-point methods. MILP solvers commonly use branch-and-bound, branch-and-cut, presolve, primal heuristics, and cutting planes.

A solver may report a relative optimality gap. For a minimization problem with incumbent value Z_inc and valid lower bound Z_lb, one common gap measure is:

The precise convention may vary by software. A small gap provides evidence of near-optimality, but it does not validate the data or the model.

Heuristics seek good solutions quickly without guaranteeing optimality. Examples include nearest-neighbor and savings methods for routing, greedy assignment, local search, tabu search, simulated annealing, genetic algorithms, and large-neighborhood search. A practical workflow is to use heuristics for rapid feasible plans, exact optimization for smaller or critical subproblems, and solver bounds for evaluating solution quality.

Best practices include:

1. Validate units, signs, demand balance, and capacity data before solving.
2. Build a small test instance whose answer can be checked manually.
3. Separate data, model, solver settings, and reporting code.
4. Use tight bounds and avoid unjustified big-M values.
5. Test infeasibility deliberately and use diagnostic tools.
6. Compare model output with historical decisions and operational expertise.
7. Record assumptions, versioned data, solver status, objective value, gap, and run time.
8. Conduct stress tests for demand, disruption, cost, and service changes.

9. Illustrative Case: Regional Medical Supply Distribution

Background

A health-care distributor serves three hospitals from two potential warehouses. Hospital demand is 40, 30, and 50 pallet-equivalents per week. Warehouse A has capacity 80 pallets and Warehouse B has capacity 70. Opening costs are 1,200 and 1,000 monetary units per week. Transport costs differ by hospital, and emergency replenishment is permitted at a high penalty.

Problem

Management must decide which warehouses to open and how to allocate shipments. The organization wants low cost but also requires every hospital to receive its planned demand. A disruption scenario may reduce one warehouse’s capacity by 30 pallets.

Analysis and Approach

The decision team formulates a capacitated facility-location MILP. Binary variables represent warehouse opening; continuous shipment variables represent pallet flows. Emergency variables are added with a large but explicitly justified penalty. A second model evaluates the disruption scenario. A multi-objective extension limits emergency shipments and carbon emissions while minimizing regular cost.

The base model opens only the combination that can satisfy total demand of 120 pallets. If one warehouse alone lacks sufficient capacity, both must be opened. The solver then assigns each hospital to the least-cost feasible combination, respecting warehouse capacities. Under disruption, the team compares the additional operating cost with the service risk of relying on emergency supply.

Outcome

The recommended policy is not selected solely by the lowest base-case cost. The decision-makers compare: (1) the lowest-cost plan, (2) a slightly more expensive plan with spare capacity, and (3) a robust plan that maintains hospital service under the disruption scenario. The final choice depends on the organization’s willingness to pay for resilience and the clinical consequences of shortage.

Learning Points

The case illustrates that facility location is a strategic binary decision linked to tactical flows. Scenario analysis can reveal that a small increase in normal cost buys substantial resilience. It also demonstrates why solver output must be interpreted through service requirements, clinical priorities, and governance rather than treated as an automatic decision.

10. Limitations, Governance, and Contemporary Practice

Optimization models can embed biased demand forecasts, incomplete costs, historical inequities, or legally unacceptable service rules. A model that minimizes average delivery cost might systematically provide poorer service to remote or vulnerable communities. Ethical model governance therefore requires documenting data provenance, objectives, exclusions, fairness considerations, and approval authority.

Regulatory constraints may include driver-hours rules, hazardous-material restrictions, vehicle weight limits, emissions zones, customs requirements, and health-care service obligations. These should be represented explicitly where possible rather than treated as informal afterthoughts.

Artificial intelligence and machine learning increasingly support demand forecasting, ETA prediction, anomaly detection, and parameter estimation. They do not eliminate the need for optimization: forecasts estimate uncertain inputs, while optimization selects actions under constraints. A responsible architecture keeps forecast uncertainty visible, monitors model drift, protects sensitive data, and provides human review for high-impact decisions. Digital twins and real-time reoptimization can improve responsiveness, but frequent replanning may create operational instability unless decision freeze periods and change-control rules are established.

Chapter Summary

Optimization models translate logistics decisions into explicit variables, objectives, constraints, and data. Linear programming handles continuous allocation; integer and mixed-integer models represent indivisible and fixed-charge decisions. Network models support shortest-path, minimum-cost-flow, and maximum-flow analysis, with conservation and capacity providing their central structure. Multi-objective methods expose trade-offs among cost, service, resilience, and sustainability. Nonlinear and stochastic models represent congestion, scale effects, and uncertainty, but require careful attention to convexity, probabilities, and computational complexity.

Sensitivity analysis clarifies the value of capacity, costs, information, and constraints, while heuristics provide practical solutions when exact optimization is too slow or too large. Solver results should be validated, stress-tested, documented, and interpreted through managerial, ethical, and regulatory judgment. The essential professional skill is not merely operating a solver, but constructing a defensible decision system whose assumptions and consequences are understood.

Key Terms

Optimization model: A formal representation used to select the best feasible decision under stated criteria.

Decision variable: A controllable quantity determined by the model.

Parameter: An input value treated as known or estimated.

Feasible solution: A solution satisfying all model constraints.

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

Integer programming: Optimization requiring selected variables to be integers.

Binary variable: A variable restricted to 0 or 1.

MILP: A mixed-integer linear program containing continuous and integer variables.

Big-M: A sufficiently large linking constant used in some logical constraints.

Network model: An optimization model based on nodes and directed or undirected arcs.

Shortest path: The least-cost route between an origin and destination.

Minimum-cost flow: A flow allocation minimizing arc costs subject to balances and capacities.

Maximum flow: The greatest feasible flow between a source and sink.

Shadow price: The marginal objective effect of relaxing a constraint within an applicable range.

Reduced cost: The objective-coefficient improvement needed for a nonbasic LP variable to enter a basis.

Pareto-efficient solution: A solution that cannot improve one objective without worsening another.

Heuristic: A method that seeks good solutions without generally proving optimality.

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

Recourse: A later decision taken after uncertainty is revealed.

Model governance: Controls for assumptions, data, validation, accountability, and responsible use.

Review Questions

Short Answer Questions

1. What are the four principal components of an optimization model?
2. Why are binary variables useful in facility-location models?
3. State the flow-conservation principle at an intermediate network node.
4. What does a shadow price represent in a linear program?
5. Why should objectives with different units be normalized in a weighted-sum model?

Long Answer Questions

1. Compare linear programming, integer programming, and mixed-integer linear programming using logistics examples.
2. Explain the formulation and managerial interpretation of a capacitated facility-location model.
3. Distinguish shortest-path, minimum-cost-flow, and maximum-flow models.
4. Discuss how sensitivity analysis can support logistics capacity and investment decisions.
5. Evaluate the benefits and limitations of exact optimization, heuristics, and hybrid solution approaches.

Analytical / Application Questions

1. A distributor must choose between a low-cost warehouse with no spare capacity and a higher-cost warehouse with resilience capacity. Design a model or scenario-analysis framework for the decision and identify the data required.
2. Construct a small network in which the minimum cut limits throughput. Explain which capacity investment would improve maximum flow and why.
3. Design a multi-objective logistics model balancing cost, delivery time, and emissions. Explain how you would select weights or ε-constraints and test the robustness of the resulting recommendation.

Multiple Choice Questions with Answers

Question 1

Which model component represents a controllable quantity such as shipment volume?

A. Parameter

B. Decision variable

C. Constraint

D. Shadow price

Correct Answer: B. Decision variable

Question 2

In a capacitated facility-location model, what prevents shipments from a closed facility?

A. A demand equality

B. A reduced cost

C. A linking constraint involving the opening binary variable

D. A shortest-path equation

Correct Answer: C. A linking constraint involving the opening binary variable

Question 3

Which algorithm is appropriate for shortest-path problems when all arc costs are nonnegative?

A. Dijkstra’s algorithm

B. Simplex only

C. Apriori

D. K-means

Correct Answer: A. Dijkstra’s algorithm

Question 4

What does a maximum-flow model maximize?

A. The number of facilities opened

B. The total feasible flow from source to sink

C. The average arc cost

D. The number of demand nodes

Correct Answer: B. The total feasible flow from source to sink

Question 5

A Pareto-efficient solution is one for which:

A. All objectives have equal numerical values

B. No objective can improve without worsening at least one other objective

C. The cost objective is always zero

D. Every constraint is binding

Correct Answer: B. No objective can improve without worsening at least one other objective

Question 6

Why should objectives be normalized before applying weighted sums?

A. To make all variables integer

B. To remove all uncertainty

C. To make objectives with different units more comparable

D. To guarantee a nonconvex frontier is found

Correct Answer: C. To make objectives with different units more comparable

Question 7

For a minimization problem, a valid lower bound of 900 and an incumbent solution of 1,000 give an optimality gap of:

A. 1%

B. 10%

C. 90%

D. 111%

Correct Answer: B. 10%

Question 8

Which statement about a big-M value is most accurate?

A. It should always be as large as computationally possible

B. It should be a valid, preferably tight upper bound

C. It must be negative

D. It eliminates the need for binary variables

Correct Answer: B. It should be a valid, preferably tight upper bound

Question 9

In a minimum-cost-flow model, what condition is generally required for total supply and total demand to balance?

A. ∑ᵢb_i = 0

B. ∑ᵢb_i = 1

C. All arc costs must be equal

D. All capacities must be infinite

Correct Answer: A. ∑ᵢb_i = 0

Question 10

What is a key limitation of solver output?

A. It cannot optimize any objective

B. It automatically corrects biased data

C. It validates the model’s assumptions without human review

D. It may be mathematically optimal for an unrealistic model

Correct Answer: D. It may be mathematically optimal for an unrealistic model