Discrete, Network and Nonlinear Optimization

Introduction and Context

Prescriptive analytics converts data, forecasts, and managerial preferences into recommended actions. Linear programming is powerful when decisions are divisible and relationships are proportional. Many important business decisions, however, are indivisible, logically constrained, connected through networks, or governed by nonlinear economic and physical relationships. A firm cannot open 2.4 distribution centers, assign half an employee to a shift, or select 0.35 of a project when the project must either be undertaken or rejected. Similarly, transportation, telecommunications, energy, and financial systems often require models that represent networks or nonlinear trade-offs.

This chapter develops optimization models for integer, binary, mixed-integer, goal, network, and nonlinear decision problems. It emphasizes formulation, interpretation, computational complexity, and the managerial consequences of modeling choices. The central principle is that a technically sophisticated solver cannot compensate for a poorly specified decision model. Variables must represent real decisions, constraints must reflect feasible operations, and the objective must express the organization’s actual priorities.

Learning Objectives

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

1. Distinguish continuous, integer, binary, mixed-integer, goal, network, and nonlinear optimization models.
2. Formulate allocation, assignment, scheduling, routing, location, pricing, and portfolio problems.
3. Explain relaxations, branch-and-bound, cutting planes, heuristics, and solver optimality gaps.
4. Construct and interpret transportation, transshipment, shortest-path, maximum-flow, and minimum-cost-flow models.
5. Formulate nonlinear objectives and constraints while recognizing convexity and nonconvexity.
6. Select an appropriate solution approach and assess computational, operational, ethical, and governance limitations.

1. Discrete Decision Models

1.1 Integer and binary variables

An integer programming model restricts at least one decision variable to an integer value. A general mixed-integer linear program (MILP) is:

Here, x is a vector of continuous variables, y is a vector of integer variables, c and d are objective coefficients, A and B are constraint-coefficient matrices, and b is a resource vector. Coefficients must use compatible units: for example, if x measures units produced, a resource coefficient may be labor-hours per unit and b may be available labor-hours.

A binary variable yᵢ ∈ {0, 1} represents a yes/no decision. Typical interpretations include:

• yᵢ = 1 if a facility is opened;
• yᵢ = 1 if a customer is served by a particular vehicle;
• yᵢ = 1 if an employee is assigned to a shift;
• yᵢ = 1 if an advertisement is purchased.

Binary variables are especially valuable for logical relationships. If x is production quantity and y indicates whether a plant is activated, the implication “production is possible only when the plant is open” can be modeled as:

where U is a valid upper bound on production. If y = 0, x must be zero; if y = 1, x may range up to U. Choosing U too large weakens the model’s computational performance and may create numerical instability. A tight, defensible bound is therefore a modeling requirement, not merely a technical preference.

1.2 Common logical formulations

If at least one of activities 1 and 2 must be selected:

If at most one is allowed:

If activity 2 may occur only when activity 1 occurs:

If exactly k projects must be selected:

If x may be positive only when y = 1, use x ≤ Uy. If x must be at least L when y = 1, use x ≥ Ly, assuming x ≥ 0 and L is a valid minimum operating level. These formulations are valid only when the stated bounds and logical interpretation are correct.

1.3 Allocation, assignment, and scheduling

An allocation model distributes scarce resources among activities. A basic integer allocation model is:

pᵢ is contribution per unit of activity i, aᵢⱼ is resource j consumed per unit, bⱼ is resource availability, and xᵢ is the integer activity level. The model assumes known coefficients, additive resource consumption, and a linear contribution measure.

An assignment model assigns each worker to one position. Let xᵢⱼ = 1 if worker i performs job j. Then:

cᵢⱼ is the cost, time, or disutility of assigning worker i to job j. If the numbers of workers and jobs differ, equality constraints can be replaced with ≤ constraints or dummy workers/jobs can be introduced, provided the dummy costs have a meaningful interpretation.

Scheduling models add time, precedence, labor, machine, and coverage constraints. For example, if task i starts at time sᵢ, has duration pᵢ, and must precede task k:

For two tasks that cannot overlap on one machine, binary variable yᵢₖ can select the order:

where yᵢₖ ∈ {0,1} and M is a valid upper bound on the scheduling horizon. This disjunctive formulation should be tightened whenever possible.

1.4 Routing and location

A traveling-salesperson model uses xᵢⱼ = 1 when a route travels directly from location i to location j. Degree constraints require exactly one departure and arrival at each location:

These constraints alone can produce disconnected subtours. Subtour-elimination constraints are therefore needed. One family, for every proper nonempty subset S of locations, is:

Although conceptually clear, this family may be exponentially large. Modern solvers often generate violated subtour constraints dynamically through separation procedures.

A facility-location model combines fixed opening costs and customer assignment. Let yⱼ indicate whether facility j opens and xᵢⱼ indicate whether customer i is assigned to facility j:

Fⱼ is the fixed cost of opening facility j and cᵢⱼ is the assignment or service cost. Capacity can be added as ∑ᵢ dᵢxᵢⱼ ≤ Kⱼyⱼ, where dᵢ is customer demand and Kⱼ is facility capacity.

2. Solution Methods and Computational Limits

2.1 Linear relaxation

The linear programming relaxation of an integer model removes integrality restrictions. For example, yᵢ ∈ {0,1} becomes 0 ≤ yᵢ ≤ 1. In a maximization problem, the relaxation provides an upper bound on the integer optimum; in a minimization problem, it provides a lower bound, assuming the relaxation is feasible and the objective direction is correctly interpreted. A fractional solution is generally not feasible for the original problem and cannot simply be rounded without checking all constraints.

2.2 Branch-and-bound

Branch-and-bound solves a MILP by repeatedly:

1. Solving a relaxation at a node.
2. Using its bound to discard nodes that cannot improve the incumbent integer solution.
3. Branching on a fractional variable, such as imposing yᵢ ≤ 0 in one branch and yᵢ ≥ 1 in another.
4. Continuing until the best remaining bound and incumbent establish the desired optimality gap.

For a minimization problem, if incumbent value is U and the best lower bound is L, the relative gap may be reported as:

when U ≠ 0. Solver conventions can differ, especially when objective values may be negative, so reported gaps should be interpreted using the solver’s documentation. A zero gap certifies optimality relative to the formulated model; a nonzero gap indicates a bound on unresolved optimization uncertainty, not necessarily forecast or data uncertainty.

2.3 Cutting planes, decomposition, and heuristics

A cutting plane is a valid inequality that removes fractional relaxation solutions without excluding any feasible integer solution. Branch-and-cut combines branching and cuts. Decomposition methods exploit structure: Benders decomposition separates complicating strategic variables from operational recourse, while Dantzig–Wolfe decomposition represents solutions through columns and is particularly useful in routing and scheduling.

Heuristics seek good feasible solutions quickly but do not usually prove optimality. Local search, tabu search, simulated annealing, genetic algorithms, and greedy construction are useful for very large routing and scheduling problems. A practical workflow often combines a heuristic incumbent with exact optimization for a prescribed time limit.

2.4 Modeling for computational performance

Important practices include:

• scale coefficients so that numerical magnitudes are reasonably comparable;
• eliminate redundant variables and constraints;
• provide tight bounds and valid inequalities;
• use symmetry-breaking constraints when interchangeable solutions cause search duplication;
• warm-start with a known feasible solution;
• separate hard constraints from soft preferences;
• test multiple time limits and inspect the optimality gap;
• validate the returned solution independently of the solver.

NP-hardness means that worst-case solution time can grow exponentially with problem size. It does not imply that every practical instance is difficult, but it does require honest reporting of time limits, gaps, infeasibility diagnoses, and modeling assumptions.

3. Goal Programming

Organizations frequently have multiple objectives: reduce cost, meet service targets, limit emissions, and preserve workforce stability. Goal programming introduces positive and negative deviation variables around target values. For goal k with target Tₖ and achieved expression gₖ(x):

nₖ is underachievement and pₖ is overachievement. If only shortfall is undesirable, minimize nₖ; if exceeding a limit is undesirable, minimize pₖ. A weighted preemptive model may be written as:

where weights express relative importance. In lexicographic goal programming, priority level 1 is optimized before priority level 2, and so forth. Weights must be normalized or justified because a deviation measured in dollars is not directly comparable to one measured in hours or customer cases. Goal programming does not eliminate value judgments; it makes them explicit.

4. Network Optimization

A network consists of nodes and directed or undirected arcs. Let xᵢⱼ denote flow on arc (i,j), uᵢⱼ its capacity, and cᵢⱼ its unit cost. Flow conservation at node i is:

where bᵢ is net supply: positive for a source, negative for a demand node, and zero for a transshipment node. Arc capacities are 0 ≤ xᵢⱼ ≤ uᵢⱼ. A minimum-cost-flow objective is:

The units of cᵢⱼ must correspond to the units of flow, such as dollars per pallet, and the objective then has currency units.

4.1 Transportation and transshipment

A transportation model sends supply from plants i to customers j. If sᵢ is supply, dⱼ is demand, and xᵢⱼ is shipped quantity:

If total supply equals total demand, supply constraints may be equalities. With shortages, a dummy source or explicit shortage variable can represent unmet demand and its penalty.

4.2 Shortest path and maximum flow

A shortest-path model minimizes total arc length or cost from an origin to a destination. Binary variables can indicate selected arcs, with flow conservation ensuring a connected path. Dijkstra’s algorithm is appropriate for nonnegative arc lengths; negative arc lengths require other methods, and negative cycles invalidate a finite shortest-path interpretation.

A maximum-flow problem maximizes flow from source s to sink t subject to arc capacities and conservation at intermediate nodes. It supports evacuation planning, bandwidth allocation, and distribution bottleneck analysis. The max-flow/min-cut theorem states that maximum feasible flow equals the capacity of a minimum s–t cut under the standard capacitated network assumptions.

Network models are often computationally attractive because their matrices have special structure. In several classical pure network-flow models with integer capacities, optimal extreme-point solutions are integral even without explicitly imposing integer variables. This integrality property does not automatically apply when arbitrary side constraints, fixed charges, or logical decisions are added.

5. Nonlinear Optimization

Nonlinear programming is required when the objective or constraints contain products, powers, ratios, exponential functions, or other nonlinear relationships. A general nonlinear program is:

The feasible set X may include bounds or discrete variables. A differentiable unconstrained local optimum x satisfies the first-order condition ∇f(x) = 0, but this condition is not sufficient for a global minimum unless additional conditions hold.

5.1 Convexity

A differentiable function f is convex on a convex set if:

for all x,y in the set and 0 ≤ λ ≤ 1. For twice-differentiable f, a positive semidefinite Hessian is a sufficient condition for convexity on the relevant domain. In a minimization problem with convex objective and convex feasible region, every local optimum is global. This is a major computational advantage.

For a twice-differentiable function, the Hessian is the matrix of second partial derivatives:

Positive definiteness at a stationary point implies a strict local minimum, while positive semidefiniteness alone may require further analysis.

5.2 Business applications

In pricing, revenue may be p(q)q, where p(q) is price as a function of quantity q. If inverse demand is p(q) = a − bq, revenue is:

with a,b > 0. The derivative is R′(q) = a − 2bq, giving the unconstrained revenue-maximizing quantity q = a ÷ (2b), provided q lies within the feasible domain and the model’s demand assumptions are credible.

Portfolio optimization commonly uses a quadratic risk measure:

x is the vector of portfolio weights, Σ is the covariance matrix of asset returns, μ is the expected-return vector, R is the required expected return, and 1 is a vector of ones. The risk term has squared-return units when Σ is a return covariance matrix. The model assumes estimated means and covariances are sufficiently informative, short selling is prohibited, and all capital is invested.

5.3 Algorithms and limitations

Gradient-based methods use first derivatives; Newton methods use gradient and Hessian information; sequential quadratic programming solves a sequence of quadratic approximations; and interior-point methods approach constraints from within the feasible region. For nonconvex problems, these methods may return local optima or fail because of poor scaling, infeasibility, or stationary saddle points. Global optimization may use spatial branch-and-bound, convex relaxations, interval methods, or carefully designed enumeration, but computational cost can be substantial.

Mixed-integer nonlinear programs (MINLPs) combine discrete and nonlinear decisions and are often among the most difficult practical optimization problems. A common strategy is to strengthen relaxations, exploit separability, use outer approximation for suitable convex structures, and compare multiple feasible solutions rather than relying on a single solver run.

6. Integrated Illustrative Case: Regional Fulfillment Design

Background

The following is a fictional illustrative case. OmniRetail serves six metropolitan markets from three candidate fulfillment centers. Management must decide which centers to open, how much inventory to process, which market each center serves, and how shipments move through the network. Demand forecasts are uncertain, labor availability is limited, and management has a target of delivering at least 95% of forecast demand while keeping annual cost below a budget.

Problem

Opening center j incurs fixed cost Fⱼ and capacity Kⱼ. Market i has demand dᵢ. Assignment variable xᵢⱼ equals 1 when market i is primarily served by center j, and yⱼ equals 1 when center j opens. Shortfall sᵢ represents unmet demand. The company wants to minimize fixed opening, transport, and shortage costs:

The service constraint should be interpreted carefully. If each market must receive 95% of its own forecast, the shown relationship can be reformulated as ∑ⱼ dᵢxᵢⱼ + sᵢ ≥ 0.95dᵢ, which is dimensionally clearer. If assignment is all-or-nothing, sᵢ can represent the remaining quantity; if partial fulfillment is allowed, continuous shipment variables are preferable to binary assignments.

Analysis and approach

The model is a capacitated facility-location MILP. A solver first obtains a relaxation, then branches on opening and assignment variables. Management should impose realistic upper bounds, prohibit assignments that violate maximum delivery time, and test demand scenarios rather than treating one forecast as certain. If the model is infeasible under the 95% service target and two-center limit, an infeasibility analysis should identify whether capacity, budget, or geographic restrictions are responsible.

A robust extension can protect against demand uncertainty by requiring capacity for a set of plausible scenarios ω:

This may be conservative. A stochastic model could instead minimize expected cost across scenarios, while a chance-constrained model could require a service probability. The choice depends on risk tolerance, scenario quality, and computational resources.

Outcome interpretation

Suppose the resulting solution opens centers 1 and 3, assigns each market to one open center, and leaves a small shortfall in a low-penalty market. The decision is not automatically acceptable. Managers must verify delivery times, labor feasibility, lease commitments, and whether the shortage penalty accurately reflects customer lifetime value. If the solver reports a 2% optimality gap, the solution is feasible and within the stated gap of the best bound, but not proven optimal. Sensitivity analysis should test fixed costs, demand, fuel prices, service targets, and capacity.

Learning points

The case demonstrates that strategic location, tactical allocation, service goals, and network costs can be integrated in one model. It also illustrates why model validation extends beyond solver status: units, business logic, uncertainty, and governance determine whether an apparently optimal solution is operationally sound.

7. Managerial, Ethical, and Governance Considerations

Optimization objectives encode organizational values. A routing model that minimizes cost may increase driver fatigue or neighborhood pollution. A scheduling model may systematically assign undesirable shifts to workers whose historical availability reflects constrained circumstances. A credit or pricing model may produce discriminatory outcomes even when protected attributes are excluded, because geographic and behavioral variables can act as proxies.

Good governance requires:

• documented data sources, assumptions, bounds, and objective weights;
• audit trails for model versions, solver settings, and decision overrides;
• fairness and disparate-impact testing where people are affected;
• human review for high-consequence decisions;
• privacy protection and data minimization;
• scenario and stress testing;
• monitoring for drift in costs, demand, constraints, and outcomes;
• clear responsibility when model recommendations conflict with safety or legal obligations.

AI can assist with demand estimation, constraint extraction, scenario generation, and heuristic search, but generated formulations require expert validation. An AI system should not silently convert a managerial preference into a hard constraint or infer sensitive attributes without authorization. Explainability is particularly important when optimization determines access to employment, credit, healthcare, or essential services.

8. Best-Practice Model Development Workflow

1. Define the decision, decision-maker, planning horizon, and unit of analysis.
2. Identify variables that represent controllable actions rather than predictions.
3. State the objective and distinguish monetary value from service, risk, and social goals.
4. Build constraints from process logic, physical capacity, policy, and legal requirements.
5. Check dimensions, bounds, sign conventions, and extreme cases.
6. Solve a small hand-checkable instance before scaling.
7. Compare the integer model with its relaxation and inspect fractional behavior.
8. Validate feasibility independently and test alternative formulations.
9. Perform sensitivity, scenario, and robustness analysis.
10. Report objective value, feasibility, runtime, optimality gap, assumptions, and limitations.
11. Pilot the recommendation and monitor actual outcomes.

Chapter Summary

Discrete optimization represents indivisible decisions through integer and binary variables and supports allocation, assignment, scheduling, routing, and facility-location applications. Logical implications, capacity limits, precedence relations, and subtour elimination are central formulation devices. Branch-and-bound, cutting planes, decomposition, and heuristics provide alternative ways to obtain or approximate solutions, while optimality gaps communicate unresolved computational uncertainty.

Goal programming handles multiple targets through weighted or lexicographic deviations. Network optimization exploits flow conservation and includes transportation, transshipment, shortest-path, maximum-flow, and minimum-cost-flow models. Nonlinear optimization represents pricing, risk, economies of scale, and other relationships that linear models cannot capture. Convexity is especially important because local solutions are global under appropriate convex minimization conditions; nonconvex and mixed-integer nonlinear models are substantially more difficult.

In practice, model quality depends on formulation validity, data quality, uncertainty treatment, numerical conditioning, and governance. Optimization recommendations should therefore be evaluated not only for mathematical performance but also for operational feasibility, fairness, safety, transparency, and organizational acceptability.

Key Terms

Integer programming: Optimization in which one or more decision variables must take integer values.

Binary variable: A variable restricted to 0 or 1, usually representing a yes/no decision.

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

Big-M formulation: A logical modeling technique using a sufficiently large valid bound M.

Linear relaxation: The model obtained by removing integrality restrictions.

Branch-and-bound: An exact search method that partitions the feasible region and uses bounds to prune nodes.

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

Cutting plane: A valid inequality that removes relaxation solutions without removing feasible integer solutions.

Goal programming: A multiobjective approach that minimizes deviations from target levels.

Network flow: Movement of quantity through nodes and arcs subject to conservation and capacity rules.

Transportation model: A network model that ships supply from origins to destinations.

Transshipment: Movement through intermediate network nodes.

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

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

Convex function: A function satisfying the convex-combination inequality on a convex domain.

Nonlinear programming: Optimization with nonlinear objectives or constraints.

Hessian: The matrix of second partial derivatives of a scalar function.

Mixed-integer nonlinear program: A model containing both discrete variables and nonlinear relationships.

Robust optimization: Optimization designed to perform acceptably across uncertain parameter realizations.

Optimality certificate: Evidence, such as a zero gap, that a solution is optimal for the formulated model.

Review Questions

Short Answer Questions

1. What distinguishes a binary variable from a general integer variable?
2. Why can directly rounding a linear-programming relaxation produce an infeasible solution?
3. What is the purpose of a subtour-elimination constraint?
4. Explain the difference between a weighted and a lexicographic goal-programming model.
5. Why does convexity matter in nonlinear minimization?

Long Answer Questions

1. Formulate and explain a capacitated facility-location model, including opening, assignment, and capacity decisions.
2. Describe branch-and-bound and explain how bounds and incumbent solutions reduce computational effort.
3. Compare transportation, shortest-path, maximum-flow, and minimum-cost-flow models.
4. Discuss the role of Big-M values and explain the risks of choosing them excessively large.
5. Explain how ethical and governance considerations should influence the deployment of optimization models affecting workers or customers.

Analytical / Application Questions

1. A retailer must choose which stores to open, assign customers, and respect store capacities. Identify the variables, objective components, and three essential constraints for a MILP formulation.
2. A portfolio manager minimizes variance subject to a minimum expected return and full investment. Explain the meaning of each term in the quadratic model and identify two assumptions that should be stress-tested.
3. A delivery model has a feasible solution with objective value 1,020 and a minimization lower bound of 1,000 after the time limit. Calculate the relative gap using the incumbent denominator and explain what the result does and does not establish.

Multiple Choice Questions with Answers

Question 1

Which variable type is most appropriate for representing whether a facility is opened?

A. A nonnegative continuous variable

B. A binary variable

C. An unrestricted real variable

D. A probability variable

Correct Answer: B. A binary variable

Question 2

In a minimization MILP, what does the linear-relaxation objective generally provide?

A. An upper bound on the integer optimum

B. A lower bound on the integer optimum

C. A guaranteed feasible integer solution

D. A forecast of demand

Correct Answer: B. A lower bound on the integer optimum

Question 3

What is the primary purpose of the constraint x ≤ Uy when y is binary?

A. To force x to equal U

B. To allow x to be positive only when y equals 1

C. To make x an integer

D. To eliminate all capacity limits

Correct Answer: B. To allow x to be positive only when y equals 1

Question 4

Why are subtour-elimination constraints needed in a traveling-salesperson model?

A. To permit multiple disconnected cycles

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

C. To convert costs into capacities

D. To remove all binary variables

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

Question 5

At an intermediate transshipment node, standard flow conservation requires that:

A. Inflow equals outflow

B. Inflow must be zero

C. Outflow must exceed inflow

D. All arcs must be selected

Correct Answer: A. Inflow equals outflow

Question 6

Which condition provides a strong basis for concluding that a local minimum is global in a minimization problem?

A. A convex objective and convex feasible region

B. A nonconvex objective and disconnected feasible region

C. A large Big-M value

D. A fractional binary solution

Correct Answer: A. A convex objective and convex feasible region

Question 7

In goal programming, what do deviation variables measure?

A. Solver runtime only

B. Departure from a specified target

C. The number of network nodes

D. The covariance between assets

Correct Answer: B. Departure from a specified target

Question 8

A portfolio model minimizes xᵀΣx. What does Σ typically represent?

A. A vector of prices

B. A covariance matrix of asset returns

C. A facility-capacity matrix

D. A vector of binary decisions

Correct Answer: B. A covariance matrix of asset returns

Question 9

A minimization solver reports an incumbent value of 1,020 and a lower bound of 1,000. What is the relative gap using the incumbent denominator?

A. 0.98%

B. 1.96%

C. 2.00%

D. 20.00%

Correct Answer: B. 1.96%

Question 10

Which statement about a solver’s nonzero optimality gap is correct?

A. The solution is necessarily infeasible

B. The solution is feasible but optimality has not been fully certified

C. The data are necessarily unbiased

D. The model has no objective function

Correct Answer: B. The solution is feasible but optimality has not been fully certified