Optimization and Prescriptive Decision Models

Introduction

Descriptive analytics explains what has happened, and predictive analytics estimates what may happen. Prescriptive analytics addresses the managerial question: what should be done, given objectives, resources, constraints and uncertainty? Optimization is the central formal approach to prescriptive decision-making. It converts a supply-chain problem into a mathematical model whose solution identifies the best feasible decision according to an explicit criterion.

In supply chains, optimization supports network design, procurement, production planning, inventory allocation, transportation, workforce scheduling, warehouse location, routing and sustainability decisions. The quality of an optimization result depends not only on the solver but also on the quality of the formulation, data, assumptions and managerial interpretation.

This chapter develops linear programming, integer and mixed-integer programming, nonlinear programming, multi-objective optimization, sensitivity analysis and heuristic methods. It also explains how optimization results should be governed and implemented in real organizations.

Learning Objectives

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

1. Formulate supply-chain decisions using variables, objectives and constraints.
2. Distinguish linear, integer, mixed-integer and nonlinear optimization models.
3. Interpret feasible solutions, optimal solutions, shadow prices, reduced costs and sensitivity ranges.
4. Formulate and solve basic multi-objective models.
5. Select heuristics or metaheuristics when exact optimization is impractical.
6. Evaluate optimization results critically, including assumptions, data quality, uncertainty, ethics and implementation risk.

1. The Structure of an Optimization Model

An optimization model contains four essential elements:

• Decision variables: controllable quantities, such as units produced, shipments, facility-opening decisions or vehicle assignments.
• Parameters: known or estimated inputs, such as demand, capacity, cost, distance and emissions coefficients.
• Objective function: a mathematical representation of the outcome to maximize or minimize.
• Constraints: restrictions that feasible decisions must satisfy.

A general minimization model can be written as:

Here, x is the vector of decision variables, f(x) is the objective, g_i(x) are inequality constraints, h_j(x) are equality constraints, and X specifies domains such as non-negativity, integrality or binary restrictions. A solution is feasible if it satisfies every constraint. An optimal solution is a feasible solution with the best objective value under the model.

The model is not the decision itself. It is a structured representation of a decision problem. A mathematically optimal answer can be operationally poor if demand estimates are biased, lead times are ignored, capacity is overstated or service requirements are defined incorrectly.

1.1 Decision variables and units

Units must be explicit. If x_{ij} represents cases shipped from supplier i to plant j, its unit is cases per planning period. A cost coefficient c_{ij} must then be monetary units per case, so c_{ij}x_{ij} is monetary units. Binary variable y_j may represent whether facility j is opened:

A value of 1 means “open” and 0 means “do not open.” Continuous, integer and binary variables may occur in the same model.

1.2 Objective direction and feasibility

Cost, distance, time, risk and emissions are normally minimized. Profit, contribution, service level or throughput may be maximized. The objective must reflect the decision-maker’s actual preference. For example, minimizing transportation cost alone may produce an infeasible service pattern if customer delivery deadlines are omitted.

A model may be:

• Feasible: at least one solution satisfies all constraints.
• Infeasible: no solution satisfies all constraints.
• Unbounded: the objective can improve indefinitely, often indicating a missing constraint or an incorrect sign.
• Degenerate: more constraints are binding than necessary to define the solution, which can complicate sensitivity interpretation.

2. Linear Programming

A linear programming (LP) model has a linear objective and linear constraints, with continuous decision variables. A standard minimization form is:

Here, xᵢⱼ is the quantity shipped from supplier i to customer j, cᵢⱼ is unit shipping cost, dⱼ is customer demand and sᵢ is supplier capacity. The formulation assumes proportional costs, divisible flows, known demand and capacities, and no nonlinear quantity discounts or fixed shipment costs.

2.1 Transportation example

Two plants supply two distribution centres. Plant capacities are 40 and 50 units; distribution-centre demands are 30 and 60 units. Unit costs are:

Let x₁₁, x₁₂, x₂₁ and x₂₂ denote shipments. The model is:

Because total capacity equals total demand, an optimal plan uses all capacity. Plant 2 is cheaper for DC2, while Plant 1 is cheaper for DC1. Assigning Plant 2’s 50 units first to DC2 and the remaining 10 units to DC1 gives x₁₁ = 20, x₁₂ = 20, x₂₁ = 10 and x₂₂ = 40. The cost is:

The solution is feasible and costs 370 monetary units. In a more complex instance, a solver would identify the optimum systematically rather than relying on manual allocation.

2.2 Graphical and simplex interpretation

With two decision variables, constraints can be plotted as half-planes. Their intersection forms the feasible region. For a linear objective over a non-empty bounded polyhedron, at least one optimum occurs at an extreme point. The simplex method moves between extreme points, improving the objective until no improving adjacent point exists.

Modern commercial and open-source solvers also use interior-point methods, which move through the interior of the feasible region and are effective for large sparse LPs. The algorithm is important, but formulation and data validation are usually more consequential for managerial quality.

3. Integer and Mixed-Integer Optimization

LP permits fractional values. That is reasonable for litres, tonnes or aggregated flows, but not always for trucks, workers, machines or facility openings. Integer programming requires some or all variables to be integers:

A mixed-integer linear program (MILP) combines continuous, integer and binary variables. MILP is essential when decisions involve fixed charges, yes/no choices, sequencing, minimum batch sizes or logical conditions.

3.1 Fixed-charge facility model

Let xᵢⱼ be quantity shipped from candidate facility i to customer j, and yᵢ indicate whether facility i is opened. Let Fᵢ be the fixed opening cost, cᵢⱼ the unit distribution cost, Kᵢ facility capacity and dⱼ customer demand. A basic capacitated facility-location model is:

The constraint ∑ⱼxᵢⱼ ≤ Kᵢyᵢ links the continuous shipment variables to the opening decision. If yᵢ = 0, shipments from facility i must be zero. This is a big-M-style linking constraint, where Kᵢ is a tight, meaningful upper bound. An excessively large M can weaken computational performance and numerical stability.

3.2 Branch-and-bound

MILP solvers commonly relax integrality, solve the resulting LP, and use branch-and-bound. A fractional variable is selected, and the problem is divided into branches—for example, x ≤ 3 and x ≥ 4. Bounds from LP relaxations allow branches that cannot beat the incumbent solution to be eliminated. Cutting planes may add valid inequalities without removing any integer-feasible solution.

The solver’s optimality gap communicates how close the incumbent is to proven optimality. If the best feasible solution has value U and a valid bound is L for a minimization problem, a common relative gap is:

The formula assumes U ≠ 0 and that L ≤ the true optimum ≤ U. A small gap supports a stronger optimality claim; it does not guarantee that the model itself is realistic.

4. Nonlinear Optimization

Nonlinear programming (NLP) includes nonlinear objectives or constraints. Examples include economies of scale, congestion, risk functions, process yields and nonlinear holding costs. A nonlinear model can be written as:

If f and g_i are convex functions and the feasible region is convex, every local optimum is global. For differentiable unconstrained optimization, a necessary first-order condition is:

This condition is not sufficient for a global minimum in a nonconvex problem. With constraints, the Karush–Kuhn–Tucker conditions provide necessary conditions under suitable regularity assumptions, including constraint qualifications. Nonconvex models may have multiple local optima and require global optimization, multistart methods or carefully designed heuristics.

A common supply-chain example is a convex congestion cost:

Here q is flow and C(q) is cost. The marginal cost is:

The marginal cost rises with flow, representing congestion or overtime pressure. The model is appropriate only when the quadratic approximation is a defensible representation over the relevant operating range.

5. Multi-Objective Optimization

Supply-chain decisions often balance cost, service, resilience, emissions and risk. These objectives conflict. A single “best” solution does not exist until management specifies how trade-offs should be handled.

5.1 Weighted-sum method

If objectives are comparable after normalization, a weighted model is:

Weights satisfy wᵣ ≥ 0 and ∑ᵣwᵣ = 1. Because cost, tonnes of CO₂ and hours of delay have different units, raw objectives should not normally be added. A normalized objective may be:

where the reference values define a meaningful scale and the denominator is non-zero. Weights express trade-off preferences, not objective importance in an absolute scientific sense.

5.2 ε-constraint method and Pareto efficiency

The ε-constraint method optimizes one primary objective while imposing limits on others:

Changing ε values generates alternative efficient solutions. A solution is Pareto efficient if no objective can improve without worsening at least one other objective. Presenting a Pareto frontier allows executives to choose transparently rather than hiding preferences inside arbitrary weights.

6. Duality, Shadow Prices and Sensitivity

Every LP has a related dual model. The primal commonly represents activity decisions; the dual represents the implicit value of scarce resources. A dual value, or shadow price, estimates the change in optimal objective value caused by a one-unit relaxation of a right-hand-side resource, within a valid sensitivity range.

For example, if a capacity constraint has shadow price 12 monetary units per additional unit, one additional unit of capacity is worth approximately 12 monetary units, provided the model’s basis remains unchanged. This does not mean the organization should pay any price for capacity: the interpretation is local, and operational, contractual and strategic conditions may change.

Important sensitivity concepts include:

• Binding constraint: holds at equality at the optimum and restricts improvement.
• Slack: unused amount in a ≤ constraint, or surplus in a ≥ constraint.
• Reduced cost: for a variable at a bound, the objective coefficient must generally improve by at least this amount before the variable can enter the optimal basis, subject to sign convention and solver report conventions.
• Allowable range: interval over which a coefficient or right-hand side can change without changing the current optimal basis.
• Dual value: marginal objective impact of a right-hand-side change within that range.

Sensitivity analysis is local. If demand increases substantially, several constraints may change status, the basis may change and reported shadow prices may no longer apply. Sensitivity analysis also does not capture parameter uncertainty unless scenarios or stochastic models are explicitly used.

7. Uncertainty and Robust Decision-Making

Deterministic optimization uses single values for uncertain inputs. Scenario analysis solves the model under alternative demand, lead-time, price or disruption assumptions. A simple expected-value formulation is:

where pₛ is the probability of scenario s and ∑ₛpₛ = 1. This approach is useful when probabilities are credible, but an expected solution may perform poorly in a severe scenario.

Robust optimization seeks decisions that remain acceptable across a defined uncertainty set. A typical robust objective may minimize worst-case cost:

where u represents uncertain parameters and U is the uncertainty set. Robustness often increases cost under normal conditions in exchange for protection against adverse conditions. The correct choice depends on risk tolerance, disruption consequences and the reversibility of decisions.

8. Heuristics and Metaheuristics

Exact optimization is preferred when a solution can be obtained within acceptable time and with a useful optimality certificate. It may become impractical for very large, highly constrained or dynamic problems, especially routing, scheduling and integrated network decisions.

A heuristic is a problem-specific procedure that seeks good solutions without guaranteeing optimality. A constructive routing heuristic may repeatedly assign the nearest feasible customer. A local-search heuristic begins with a feasible solution and explores neighbourhood moves, such as relocating a customer or swapping two assignments.

Metaheuristics provide general search strategies:

• Simulated annealing: occasionally accepts an inferior move, particularly early in the search, to escape local optima.
• Tabu search: records recent moves or solutions to prevent cycling.
• Genetic algorithms: evolve a population using selection, crossover and mutation.
• Large-neighbourhood search: destroys part of a solution and reconstructs it, often effectively for routing and scheduling.
• Variable-neighbourhood search: systematically changes neighbourhood structures.

A heuristic should be evaluated against lower bounds, known benchmarks, historical decisions, computational time, repeatability and operational feasibility. “Better than the current plan” is not the same as “optimal.” Randomized methods should be run with multiple seeds and reported using consistent performance measures.

9. An Applied Case: Network Design Under Cost and Emissions Trade-offs

The following is an illustrative case. Meridian Foods serves three regional markets from two possible distribution centres. Management must decide which centres to open and how to allocate annual demand. Centre A has a fixed cost of 420,000 monetary units, capacity of 80,000 cases and average emissions of 0.18 kg per case. Centre B has a fixed cost of 300,000, capacity of 60,000 cases and emissions of 0.31 kg per case. Total demand is 110,000 cases. Transportation costs depend on customer-centre combinations. Management wants low cost but has a corporate emissions target.

Background and problem

A cost-only MILP opens the lower-fixed-cost centre B and may use A only if capacity requires it. However, B is farther from the largest market. A cost-only solution can therefore conflict with the emissions target. The decision must include fixed opening costs, capacity, demand fulfilment and an emissions limit.

Model

Let yᵢ be a binary opening variable and xᵢⱼ the cases shipped from centre i to market j. Let cᵢⱼ be transportation cost, Fᵢ fixed cost, eᵢⱼ emissions per case and E the annual emissions limit:

The emissions constraint converts a sustainability aspiration into a testable operational requirement. If the model is infeasible, management must increase the emissions limit, add a centre, permit external transport, reduce demand, or change the service/network design.

Analysis and solution approach

The analyst first validates demand totals, capacities, cost units, emission factors, facility-opening definitions and the planning horizon. Next, three models are solved: cost-only, cost with the emissions limit, and a weighted cost-emissions model. The alternatives are compared by total cost, emissions, centre utilization, market service and sensitivity to demand.

Suppose the cost-only model produces annual cost 1.84 million and emissions 42,000 kg, while the emissions-constrained model produces cost 1.91 million and emissions 35,000 kg. The constrained solution therefore incurs a 70,000 monetary-unit cost increase for a 7,000 kg reduction, or approximately 10 monetary units per kg reduced:

This ratio is an incremental trade-off between these two model solutions, not a universal carbon price. It is meaningful only if the alternatives differ solely through the modeled design and use comparable accounting boundaries.

Outcome and learning points

Management may select the constrained solution if the emissions target is mandatory or reputational risk is high. If the target is aspirational, the Pareto frontier can support a policy discussion. The case demonstrates that optimization makes trade-offs visible, but it does not determine the organization’s values. It also shows why fixed costs, capacity, demand and environmental coefficients must be audited before results are presented.

10. Implementation, Governance and Responsible Use

Optimization projects commonly fail at the interface between model and organization. Best practice includes:

1. Define the decision clearly: specify decision horizon, decision rights, service promises and non-negotiable constraints.
2. Build a data dictionary: document every parameter, unit, source, timestamp and transformation.
3. Validate independently: test small instances manually, check conservation equations and challenge extreme solutions.
4. Use appropriate bounds: tighten variable bounds and avoid unjustifiably large big-M values.
5. Separate model versions: preserve input data, code, solver settings and output reports for reproducibility.
6. Communicate uncertainty: provide scenarios, ranges and optimality gaps rather than false precision.
7. Pilot decisions: test recommendations in a controlled region or planning cycle.
8. Monitor drift: update costs, capacities, demand patterns and emissions factors as conditions change.

Ethically, optimization can distribute shortages, allocate overtime, select suppliers or close facilities. A model that minimizes cost may systematically disadvantage remote communities, precarious workers or small suppliers. Governance should therefore examine fairness, legal compliance, worker safety, privacy, environmental justice and explainability. Automated recommendations should retain human accountability, especially when decisions affect employment, access to essential products or supplier survival.

Artificial intelligence can assist with demand forecasting, parameter estimation, anomaly detection and natural-language interfaces to optimization systems. It does not remove the need for mathematical validation. AI-generated constraints or inferred costs may encode bias, omit business rules or produce non-reproducible results. A reliable architecture separates data preparation, optimization, human review and execution monitoring.

Challenges and Limitations

Optimization models necessarily simplify reality. Important limitations include:

• Parameter uncertainty can make a precise optimum fragile.
• Linear costs may misrepresent discounts, congestion and stepwise tariffs.
• Aggregation can hide time, geography and customer-level feasibility.
• A narrow objective can create unintended consequences.
• Computational tractability may require relaxation or approximation.
• Solver status must be interpreted carefully; an incumbent solution with a nonzero gap is not proven optimal.
• Organizational adoption may fail if planners cannot understand or influence the model.
• Local legal, contractual and safety constraints may be absent from the data.

The appropriate response is not to abandon optimization but to combine exact models, scenarios, robust analysis, domain expertise and post-solution review.

Chapter Summary

Optimization provides a formal language for prescriptive supply-chain decisions. A valid model identifies decision variables, parameters, an objective and constraints with consistent units and defensible assumptions. Linear programming handles continuous proportional relationships; integer and mixed-integer models represent indivisibilities, fixed charges and logical choices; nonlinear programming represents congestion, risk and other nonlinear relationships. Multi-objective methods expose trade-offs through weighted sums, ε-constraints and Pareto-efficient solutions. Dual values and sensitivity analysis explain the marginal value of scarce resources, but their interpretation is local. Scenario and robust models address uncertainty, while heuristics and metaheuristics provide practical alternatives when exact optimization is computationally impractical. Successful implementation requires validation, governance, transparency, ethical review and continuous monitoring.

Key Terms

Decision variable: A controllable quantity selected by the model.

Parameter: An input value treated as known or estimated.

Objective function: The mathematical measure being maximized or minimized.

Constraint: A restriction that feasible decisions must satisfy.

Feasible solution: A solution satisfying every model constraint.

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

Integer programming: Optimization requiring selected variables to take integer values.

Mixed-integer linear program: A model containing continuous, integer and/or binary variables with linear relationships.

Binary variable: A variable restricted to 0 or 1.

Big-M constraint: A logical linking formulation using a valid upper bound.

Nonlinear programming: Optimization containing nonlinear objectives or constraints.

Convexity: A property under which local optima are global for suitable minimization models.

Shadow price: Marginal objective change from relaxing a right-hand-side resource constraint within a valid range.

Reduced cost: Objective-coefficient improvement required for a bounded variable to become attractive, subject to reporting conventions.

Sensitivity analysis: Study of how solution values respond to parameter changes.

Pareto-efficient solution: A solution for which no objective can improve without worsening another.

Heuristic: A procedure seeking good solutions without an optimality guarantee.

Metaheuristic: A general search framework for exploring difficult solution spaces.

Optimality gap: Difference between a feasible solution and a valid bound on the optimum.

Robust optimization: Optimization designed to perform acceptably across an uncertainty set.

Review Questions

Short Answer Questions

1. What are the four essential elements of an optimization model?
2. Why are binary variables useful in facility-location models?
3. What does a shadow price represent, and why is its interpretation local?
4. Distinguish a heuristic from an exact optimization method.
5. Why should objective functions with different units be normalized in a weighted-sum model?

Long Answer Questions

1. Explain how a transportation LP is formulated, including decision variables, objective function, demand constraints and capacity constraints.
2. Discuss the role of branch-and-bound, LP relaxations and optimality gaps in mixed-integer optimization.
3. Compare weighted-sum and ε-constraint approaches to multi-objective supply-chain optimization.
4. Explain the assumptions and limitations of sensitivity analysis using shadow prices and allowable ranges.
5. Evaluate the governance, ethical and implementation issues that arise when optimization recommendations are automated.

Analytical / Application Questions

1. A company has two plants, three customers and a fixed cost for opening each plant. Formulate a capacitated facility-location MILP and explain how the opening variables control shipments.
2. A cost-minimizing network emits 50,000 kg of CO₂ at a cost of 2.0 million monetary units. An emissions-constrained network costs 2.12 million and emits 38,000 kg. Calculate the incremental cost per kilogram reduced and explain why it should not automatically be interpreted as a universal carbon price.
3. A routing MILP cannot reach a zero optimality gap within the planning time, but its best feasible solution is operationally valid. Recommend a procedure for deciding whether to use it, including bounds, gap interpretation, benchmarking and managerial review.

Multiple Choice Questions with Answers

Question 1

Which element of an optimization model represents the quantities that management can directly choose?

A. Decision variables

B. Parameters

C. Shadow prices

D. Sensitivity ranges

Correct Answer: A. Decision variables

Question 2

Which variable domain is appropriate for a facility-opening yes/no decision?

A. x ≥ 0

B. x ∈ ℝ

C. y ∈ {0,1}

D. y ∈ [0,100]

Correct Answer: C. y ∈ {0,1}

Question 3

In a minimization MILP, what does a valid optimality gap primarily communicate?

A. The probability that demand is correct

B. How close the best feasible solution is to a proven bound

C. The number of binding constraints

D. The average solver processing speed

Correct Answer: B. How close the best feasible solution is to a proven bound

Question 4

A shadow price of 12 monetary units for one additional unit of capacity means that, within the valid sensitivity range:

A. Total cost must fall by exactly 12 regardless of the change

B. The capacity constraint is necessarily nonbinding

C. The objective is expected to improve by approximately 12 monetary units per added unit

D. The organization should always purchase capacity for less than 12 units

Correct Answer: C. The objective is expected to improve by approximately 12 monetary units per added unit

Question 5

Which condition supports the conclusion that every local optimum is global in a minimization problem?

A. The model is nonconvex

B. The objective and feasible region have appropriate convexity properties

C. At least one variable is binary

D. The objective contains a fixed charge

Correct Answer: B. The objective and feasible region have appropriate convexity properties

Question 6

What is the principal purpose of the ε-constraint method?

A. To remove all constraints except one

B. To optimize one objective while imposing limits on other objectives

C. To force all objectives to have identical units

D. To convert every variable into a binary variable

Correct Answer: B. To optimize one objective while imposing limits on other objectives

Question 7

If a cost-only solution costs 1.84 million and an emissions-constrained solution costs 1.91 million, the additional cost is:

A. 0.07 million monetary units

B. 0.70 million monetary units

C. 7.0 million monetary units

D. 0.007 million monetary units

Correct Answer: A. 0.07 million monetary units

Question 8

Which method deliberately accepts some inferior moves, especially early in the search, to escape local optima?

A. Simulated annealing

B. Simplex method

C. Transportation balancing

D. Dual pricing

Correct Answer: A. Simulated annealing

Question 9

Why should an excessively large big-M value be avoided?

A. It prevents all feasible solutions

B. It can weaken computational performance and numerical stability

C. It guarantees a nonconvex objective

D. It makes binary variables continuous by definition

Correct Answer: B. It can weaken computational performance and numerical stability

Question 10

A Pareto-efficient solution is one in which:

A. Every objective reaches its individual optimum simultaneously

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

C. All objective weights are equal

D. All constraints are nonbinding

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