Advanced Optimization and Network Models

Introduction

Managers frequently make decisions under scarce resources, competing objectives, uncertainty, and interdependence. Linear programming is powerful when relationships are proportional and divisible, but many managerial decisions are discrete, nonlinear, hierarchical, or network-based. Advanced optimization extends the decision-science toolkit to these conditions.

This chapter develops integer and binary programming, nonlinear programming, goal and multi-objective programming, and major network models: transportation, assignment, shortest path, maximum flow, routing, and project scheduling. The emphasis is not only on obtaining a numerical solution, but also on formulating a defensible model, interpreting its assumptions, validating its output, and embedding it in managerial judgment.

Learning Objectives

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

1. Formulate and interpret integer, binary, nonlinear, goal, and multi-objective programs.
2. Select appropriate algorithms and recognize their assumptions.
3. Construct transportation, assignment, routing, shortest-path, maximum-flow, and project-scheduling models.
4. Interpret feasibility, optimality, dual information, sensitivity, and computational limitations.
5. Evaluate optimization results in terms of strategy, risk, ethics, and implementation.

1. From Linear to Advanced Optimization

A general optimization model consists of decision variables, an objective function, constraints, and parameter values. In a minimization model:

Here, x is the vector of decisions, f(x) is the objective, g_i(x) and h_j(x) represent inequality and equality constraints, and X specifies domains such as non-negativity, integrality, or binary membership. A model is feasible if at least one x satisfies all constraints; it is optimal if it is feasible and no other feasible solution gives a better objective value.

A linear program (LP) has linear objective and constraint expressions and continuous variables. Advanced models relax one or more of these conditions. The choice of model should reflect the decision, not merely the capabilities of available software.

2. Integer and Binary Programming

2.1 Integer programming

An integer linear program (ILP) has a linear objective and constraints, with some or all variables restricted to integer values:

The coefficient c_j is the contribution of activity j, a_ij is its use of resource i, and b_i is the available resource. Units must be consistent: if c_j is dollars per unit, the objective is dollars; if a_ij is labor-hours per unit, b_i must be labor-hours.

Integer restrictions are appropriate for aircraft, employees, facilities, vehicles, contracts, and batches. They are not appropriate merely because a decision is measured numerically. For example, production quantities may reasonably be continuous when thousands of units are produced, but not when the product is a complete machine.

2.2 Binary programming

A binary variable takes one of two values:

It can represent selection, opening, hiring, scheduling, or logical status. Typical constraints include:

• At most one: x₁ + x₂ ≤ 1.
• Exactly one: x₁ + x₂ = 1.
• At least one: x₁ + x₂ ≥ 1.
• Dependency: if project A requires project B, x_A ≤ x_B.
• Either-or condition: x_A + x_B ≤ 1.

A fixed-charge model illustrates why binary variables matter. If opening facility j incurs fixed cost F_j and variable production cost c_j per unit, then:

The linking constraint prevents production x_j unless facility status y_j equals 1. U_j must be a valid upper bound; an unnecessarily large value weakens the model and can slow computation.

2.3 Solution methods and interpretation

The linear programming relaxation removes integrality restrictions and provides a bound: for a maximization problem, the relaxation objective is at least as large as the integer optimum; for minimization, it is no smaller than the integer optimum. A common exact method is branch-and-bound. The solver branches on a fractional variable, computes bounds for subproblems, and prunes a branch when it is infeasible, dominated by an existing incumbent, or incapable of improving the bound. Cutting planes add valid inequalities that remove fractional solutions without removing any feasible integer solution. Modern mixed-integer solvers combine both methods.

The optimality gap is often reported as:

The exact sign convention varies by software and optimization direction, so the solver definition must be checked. A small gap may be operationally sufficient even when a proof of exact optimality is unavailable.

Illustrative example. A firm selects projects A, B, and C. Their returns are 40, 35, and 30 (thousand dollars), with capital requirements 50, 40, and 30 (thousand dollars), and available capital 70. The binary model is max 40y_A + 35y_B + 30y_C, subject to 50y_A + 40y_B + 30y_C ≤ 70. Feasible pairs are A alone, B alone, C alone, and B with C. Their returns are 40, 35, 30, and 65 respectively; therefore B and C are optimal, yielding $65,000. The fractional LP solution could suggest a combination that cannot actually be implemented, demonstrating the importance of integrality.

3. Nonlinear Programming

A nonlinear program (NLP) contains a nonlinear objective or constraint. Examples include economies of scale, risk functions, congestion, portfolio variance, and production technologies.

A differentiable constrained NLP can be written as:

For an unconstrained differentiable problem, a necessary condition for an interior local optimum is:

This condition is not sufficient in general. A positive-definite Hessian at x* supports a strict local minimum, while a negative-definite Hessian supports a local maximum. Boundary constraints require additional conditions.

For constrained problems, the Karush–Kuhn–Tucker (KKT) conditions are central. With constraints g_i(x) ≤ 0 and multipliers λ_i ≥ 0, the Lagrangian is:

Necessary conditions, under suitable constraint qualifications, include stationarity ∇_x L = 0, primal feasibility, dual feasibility λ_i ≥ 0, and complementary slackness λ_i g_i(x) = 0. For convex minimization—convex objective, convex inequality-feasible region, and affine equality constraints—KKT conditions are also sufficient for global optimality.

NLP algorithms include gradient and quasi-Newton methods, sequential quadratic programming, interior-point methods, and derivative-free methods. Local algorithms can converge to local rather than global optima. Multiple starting points, convexity analysis, global optimization, and out-of-sample validation help assess robustness.

Example: pricing with a concave demand approximation. Suppose demand is q(p) = 1,000 − 20p for price p in dollars, and unit cost is $10. Profit is:

The derivative is dπ/dp = 1,200 − 40p. Setting it to zero gives p = 30. Since d²π/dp² = −40 < 0, this is the unique maximum over the unconstrained relevant range. Demand is 400 units and profit is (30 − 10) × 400 = $8,000. The result assumes the demand function is valid, price is nonnegative, and no capacity or competitive response changes the relationship.

4. Goal and Multi-Objective Programming

Organizations rarely maximize one measurable outcome. Goal programming handles multiple targets by introducing positive and negative deviations from each target. For goal a_k^T x = b_k, write:

Here, d_k^- is underachievement and d_k^+ is overachievement. If only underachievement is undesirable, minimize d_k^-; if exceeding a budget is undesirable, minimize d_k^+. A weighted model is:

Weights should be based on meaningful priority or penalty units. Arbitrary weights can conceal value judgments. In pre-emptive (lexicographic) goal programming, higher-priority goals are optimized before lower-priority goals; a lower-priority improvement cannot sacrifice a higher-priority achievement.

Multi-objective optimization retains several objective functions, for example minimizing cost and emissions simultaneously. A solution is Pareto efficient if no objective can be improved without worsening at least one other objective. Common approaches include:

• Weighted sum: min ∑_k w_k f_k(x), after appropriate normalization.
• ε-constraint: optimize one objective while imposing bounds on others.
• Goal programming: minimize deviations from managerial targets.
• Interactive methods: allow decision-makers to explore trade-offs iteratively.

Normalization is essential when objectives have different units. A simple range normalization is z_k = (f_k − f_k^min) ÷ (f_k^max − f_k^min), where the reference values must be defined consistently. Weighted sums may miss non-convex portions of a Pareto frontier; the ε-constraint approach is often more reliable for exploring such regions.

5. Network Models

A network consists of nodes and directed or undirected arcs. An arc may have cost, distance, time, capacity, or reliability. Network structure often yields specialized, efficient algorithms and transparent managerial interpretations.

5.1 Transportation model

Let x_ij be units shipped from source i to destination j, c_ij the unit shipping cost, s_i source supply, and d_j destination demand:

For a balanced transportation problem, total supply equals total demand and the inequalities are typically equalities. If supply exceeds demand, a dummy destination absorbs surplus; if demand exceeds supply, a dummy source represents an external supply or unmet-demand decision. Costs must use the same unit, such as dollars per pallet.

The northwest-corner method gives an initial feasible solution but ignores costs. Least-cost and Vogel’s approximation methods generally provide better starting solutions. The stepping-stone or MODI method tests improvement; software commonly uses network simplex or LP algorithms. A transportation model assumes divisible flows, known costs, and no prohibited routes unless explicitly modeled.

5.2 Assignment model

The assignment problem matches agents to tasks. Let x_ij = 1 if agent i is assigned to task j:

The Hungarian algorithm solves the square assignment problem efficiently. A rectangular problem can be balanced with dummy rows or columns. Assignment is appropriate when each agent performs exactly one task and each task receives exactly one agent; capacity or multiple-task conditions require a generalized model.

5.3 Shortest path

Given arc lengths c_ij, the shortest-path problem minimizes total path length from an origin to a destination. Dijkstra’s algorithm is valid when all arc lengths are nonnegative. Bellman–Ford accommodates negative arc lengths and can detect negative cycles, but negative costs require careful interpretation. Floyd–Warshall computes all-pairs shortest paths and has higher computational cost for large sparse networks.

Shortest path may represent travel time, financial cost, latency, or risk. A “shortest” route is only meaningful if the selected metric reflects the decision objective; minimizing distance may increase congestion, emissions, or exposure.

5.4 Maximum flow

Let x_ij be flow on arc (i,j) and u_ij its capacity. The model maximizes flow from source s to sink t:

The maximum-flow/minimum-cut theorem states that maximum feasible source-to-sink flow equals the capacity of a minimum cut, under standard finite-capacity assumptions. Ford–Fulkerson and Edmonds–Karp are classical algorithms; modern implementations use more advanced augmenting or push–relabel methods. In practice, arc failures, multiple commodities, and priorities may require extensions.

5.5 Routing and vehicle routing

The traveling salesperson problem (TSP) seeks a minimum-cost tour visiting each location once and returning to the origin. A basic binary formulation uses x_ij = 1 when arc i→j is selected, degree constraints requiring one arrival and one departure at each node, and subtour-elimination constraints. Degree constraints alone permit disconnected cycles; this is a frequent modeling error.

Vehicle routing problems (VRP) add vehicles, depot constraints, capacities, time windows, driver rules, and sometimes heterogeneous fleets. Exact mixed-integer methods are suitable for small instances; savings heuristics, local search, tabu search, genetic algorithms, and adaptive large-neighborhood search are often used for operational-scale problems. A heuristic solution should be accompanied by a bound, benchmark, or gap estimate whenever possible.

5.6 Project scheduling: CPM and PERT

In the critical path method (CPM), activity durations are treated as known. For an activity with early start ES and duration t, early finish is:

For an activity with successors, late finish and late start are computed backward:

Total float is TF = LS − ES = LF − EF. Activities with zero total float form a critical path, although multiple critical paths may exist and the path may change when durations change.

PERT uses three estimates: optimistic a, most likely m, and pessimistic b. The expected activity time and variance are:

These formulas assume a beta-like activity-time distribution and are approximations, not laws of probability. If a project path contains independent activities, its expected duration is the sum of expected times and its variance is the sum of activity variances. The probability of completing by deadline D is commonly approximated by:

where Φ is the standard normal cumulative distribution function. This approximation can be poor when activity times are dependent, distributions are highly skewed, or the critical path changes.

6. Integrated Illustrative Case: Regional Cold-Chain Expansion

The following is a fictional illustrative case.

Background and problem

NorthStar Foods must serve three hospitals from two candidate distribution centers. It must decide which center to open, how much to ship, and which delivery routes to use. Center A has a fixed opening cost of $80,000 and capacity of 600 cases; Center B costs $55,000 and capacity 500 cases. Hospital demands are 300, 400, and 250 cases. Each case must be delivered once, and the company wants to minimize fixed plus transportation cost while ensuring a 95% on-time target.

Analysis and approach

The center-opening decision is binary: y_A, y_B ∈ {0,1}. Shipment variables x_ij are continuous and nonnegative. The integrated model includes:

Since total demand is 950 cases, either center alone is insufficient; both must open unless demand is allowed to be outsourced. A routing submodel then tests feasible vehicle tours with capacity and time-window constraints. The service target can be represented as a hard constraint when probabilities are reliable, or as a goal-programming deviation when the 95% target is aspirational.

Outcome and managerial interpretation

Suppose the optimized plan opens both centers, assigns 600 cases to A and 350 to B, and produces a transportation cost of $21,500. Total modeled cost is therefore $156,500. This is not automatically the best managerial decision: the solution should be stress-tested for fuel-price changes, hospital demand growth, refrigeration failures, and travel-time variability. If a 5% increase in demand makes the plan infeasible, management may value spare capacity more than the nominal cost minimum.

Learning points

The case illustrates that binary location choices and continuous flows are naturally integrated in a mixed-integer model. It also demonstrates the distinction between optimization and implementation: a mathematically optimal plan may be operationally fragile, socially inequitable, or dependent on unreliable data. Scenario analysis, service-level validation, and stakeholder review are necessary complements to the solver.

7. Governance, Technology, and Best Practice

Optimization models encode institutional priorities. Ethical risks arise when objectives or constraints disadvantage protected groups, exclude remote communities, use personal data without consent, or optimize efficiency at the expense of safety. Managers should document data provenance, objective weights, exclusions, constraints, and override procedures. High-impact decisions require human review, audit trails, privacy protection, and monitoring for disparate outcomes.

AI and machine learning can improve demand forecasts, travel-time estimates, and anomaly detection, but predictions should not be confused with decisions. Forecast error must be propagated through scenario analysis or robust optimization. A robust model may optimize against a set of plausible parameter values rather than one estimate. Stochastic programming explicitly represents scenarios and probabilities, but its results are only as credible as those assumptions.

A disciplined implementation cycle is:

1. Define the decision, scope, horizon, and unit of analysis.
2. Identify variables, objective measures, constraints, and data sources.
3. Validate units, bounds, logical relationships, and extreme cases.
4. Solve and record status, objective, feasibility, and optimality gap.
5. Conduct sensitivity, scenario, and stress tests.
6. Review ethical, legal, operational, and stakeholder implications.
7. Pilot the policy, monitor actual outcomes, and recalibrate the model.

Common failures include optimizing an inappropriate objective, using unrealistic big-M constants, omitting subtour constraints, treating uncertain inputs as certain, confusing local with global optima, and reporting a solver result without explaining assumptions. Reproducible data, version-controlled models, transparent documentation, and independent validation are professional standards.

Challenges and Limitations

Advanced optimization can be computationally difficult. Integer routing problems are often NP-hard, so exact computation may become impractical as the number of locations increases. Nonlinear models may contain local optima or numerical instability. Multi-objective results depend on value judgments about weights and priorities. Network models can oversimplify congestion, reliability, multimodal transport, or human behavior.

Data quality is often more limiting than algorithmic sophistication. Costs may be stale, capacities may be nominal rather than achievable, and travel times may be correlated. A solution with greater numerical precision is not necessarily more accurate. Managers should prefer a transparent, robust, implementable solution to an opaque nominal optimum.

Chapter Summary

Advanced optimization generalizes linear programming to discrete, nonlinear, multi-target, and network decisions. Integer and binary variables represent indivisible choices and logical conditions; branch-and-bound and cutting planes provide exact or gap-certified solutions. Nonlinear programming uses derivatives, KKT conditions, convexity, and specialized algorithms, but local optimality and data assumptions require care. Goal programming minimizes deviations from targets, while multi-objective methods reveal trade-offs and Pareto-efficient alternatives.

Transportation and assignment models allocate flows and agents; shortest-path models identify least-cost routes; maximum-flow models exploit capacity and conservation; routing models coordinate tours under operational constraints; CPM and PERT support project timing and uncertainty analysis. Effective practice combines mathematical formulation with validation, sensitivity analysis, governance, ethical review, and managerial judgment.

Key Terms

Integer programming: Optimization with one or more integer-valued decision variables.

Binary variable: A variable restricted to 0 or 1.

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

Big-M constraint: A logic-linking constraint using a sufficiently large constant.

LP relaxation: A model obtained by removing integer restrictions.

Branch-and-bound: An exact method that partitions the search space and uses bounds to prune it.

Nonlinear programming: Optimization with nonlinear objective or constraint expressions.

KKT conditions: First-order necessary conditions for constrained optimization under regularity assumptions.

Convex optimization: Optimization in which appropriate convexity conditions support global optimality.

Goal programming: Optimization that minimizes weighted or prioritized deviations from targets.

Pareto efficiency: A state where no objective can improve without worsening another.

Transportation model: A flow-allocation model from sources to destinations.

Assignment model: A one-to-one matching model.

Shortest path: A minimum-cost route between specified nodes.

Maximum flow: The greatest feasible flow from a source to a sink.

Minimum cut: A partition whose crossing capacity equals maximum flow under theorem conditions.

TSP: The traveling salesperson problem.

Critical path: A sequence of activities determining project duration under CPM assumptions.

Total float: Delay available to an activity without delaying project completion.

Optimality gap: Difference between a feasible solution and a bound on the best possible solution.

Review Questions

Short Answer Questions

1. Why are binary variables useful in facility-selection models?
2. State the complementary-slackness condition in the KKT framework.
3. What is the purpose of a dummy destination in a transportation model?
4. Under what condition is Dijkstra’s algorithm applicable?
5. Define total float in CPM.

Long Answer Questions

1. Explain how branch-and-bound obtains and certifies solutions to mixed-integer programs.
2. Compare weighted-sum, ε-constraint, and lexicographic approaches to multiple objectives.
3. Explain the assumptions and managerial uses of transportation and assignment models.
4. Discuss why subtour-elimination constraints are necessary in TSP formulations.
5. Evaluate the strengths and limitations of PERT for uncertain project planning.

Analytical / Application Questions

1. A firm must select projects with indivisible capital requirements and strategic dependencies. Formulate a binary model and explain two sensitivity tests that should be performed.
2. A delivery network has uncertain travel times and a 95% service target. Compare a hard constraint, goal-programming deviation, and scenario-based formulation.
3. A distribution plan is mathematically optimal but repeatedly fails during fuel-price spikes and demand surges. Diagnose the modeling weaknesses and propose a robust implementation process.

Multiple Choice Questions with Answers

Question 1

Which condition is required for a binary variable?

A. It must be greater than or equal to 1

B. It can take any nonnegative real value

C. It must take either 0 or 1

D. It must equal the objective value

Correct Answer: C. It must take either 0 or 1

Question 2

In a maximization integer program, the LP relaxation generally provides which type of bound?

A. A lower bound on the integer optimum

B. An upper bound on the integer optimum

C. An exact integer solution in every case

D. No bound at all

Correct Answer: B. An upper bound on the integer optimum

Question 3

For the demand function q(p) = 1,000 − 20p and unit cost $10, the illustrative profit maximum occurs at which price?

A. $10

B. $20

C. $30

D. $40

Correct Answer: C. $30

Question 4

Which method is specifically designed for one-to-one assignment problems?

A. Hungarian algorithm

B. Bellman–Ford algorithm

C. Ford–Fulkerson algorithm

D. Northwest-corner method

Correct Answer: A. Hungarian algorithm

Question 5

Dijkstra’s shortest-path algorithm requires what condition on arc lengths?

A. All arc lengths must be negative

B. All arc lengths must be nonnegative

C. All nodes must have equal degree

D. All capacities must be infinite

Correct Answer: B. All arc lengths must be nonnegative

Question 6

In a maximum-flow model, what must occur at an intermediate node?

A. Flow must be created

B. Flow must be destroyed

C. Inflow must equal outflow

D. Its capacity must equal zero

Correct Answer: C. Inflow must equal outflow

Question 7

If an activity has early start 7 days and duration 5 days, its early finish is:

A. 2 days

B. 5 days

C. 12 days

D. 35 days

Correct Answer: C. 12 days

Question 8

Using PERT, if a = 2, m = 5, and b = 8, the expected activity time is:

A. 4 days

B. 5 days

C. 6 days

D. 8 days

Correct Answer: B. 5 days

Question 9

A Pareto-efficient solution is one for 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 removed

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

Question 10

Why are subtour-elimination constraints needed in a TSP model?

A. To force every arc to be selected

B. To prevent disconnected cycles that do not form one complete tour

C. To make all travel costs zero

D. To convert continuous variables into prices

Correct Answer: B. To prevent disconnected cycles that do not form one complete tour