Operations Research

Operations research concerns computable optimal solutions under decision variables and constraints. Linear, integer, and nonlinear models are studied through solver algorithms, mathematical optimality conditions, and numerical validation. Resource allocation, scheduling, and flow problems in software systems provide computational applications.

Unit 1: Mathematical Modeling of Optimization Problems

1.1. Decision Variables and the Feasible Region

Decision variables, objective functions, and constraints are distinct mathematical objects. The feasible region is the set of points satisfying all constraints simultaneously; objective values are compared only on this region. Parameters represent observed data whereas variables represent decisions selected by the algorithm. Measurement units and sign restrictions belong in the model specification.

1.2. Numerical Representation of Constraints

For task placement, binary variable xᵢⱼ equals 1 when task i is assigned to server j. Exactly-one constraints are imposed for each task and capacity limits for every server. Input validation checks variable types and constraint dimensions before optimization. A modeling error can lead a solver to produce a mathematically valid but operationally invalid result.

min[x∈ℱ] cᵀx;   ℱ = {x : Ax ≤ b, x ∈ X}

1.3. Model Consistency and Unit Checks

Small instances should first be checked by exhaustive enumeration to verify feasibility and the optimum. For larger instances, feasibility, objective value, and solver tolerances are reported separately. The optimal objective must not be confused with the best feasible upper bound returned by an incomplete search.

1.4. Numerical and Algorithmic Example

With three tasks and two servers of capacities two and one, binary placement variables xᵢⱼ produce six decisions. Each task must be placed exactly once while both capacity inequalities hold. With fixed per-task costs, exhaustive enumeration supplies a reference optimum for this small instance.

1.5. Structural Properties of Constraint Matrices

Reducing a model to Ax ≤ b is not merely an algebraic rearrangement. Sparsity, row scaling and variable types govern the data structures and factorization costs of a solver. An assignment model needs exactly-one constraints for each task and capacity restrictions for each resource. Every cost coefficient must have an explicit unit such as time, energy or monetary cost. Dimensional inconsistency can turn a mathematically feasible point into an operationally meaningless decision.

A ∈ ℝᵐˣⁿ;  ℱ = {x ∈ X : Ax ≤ b}

1.6. Separating Feasibility from Optimality

The first validation stage seeks any point satisfying the constraints without considering the objective. Feasibility identifies contradictory obligations, whereas optimality compares feasible decisions. Exhaustive enumeration of a small binary model provides an independent reference against which to test a sophisticated solver. For larger instances, violations and variable bounds should be checked before comparing objective values.

1.7. Data Indexing and Model Construction

Tasks, servers and time slots need explicit, stable indices. Missing costs must not silently become zero costs; impossible assignments are excluded from variable domains or explicitly forbidden. Duplicating a constraint may leave the mathematical solution unchanged while increasing presolve and solution costs. The number of rows, columns, nonzero coefficients and input-data version should therefore be recorded for reproducibility.

1.8. Computational Example and Calculation

For three tasks and two servers with capacities of two and one tasks, the model has six binary assignment variables. Each task must have exactly one server; both capacity limits and a total assignment count of three must hold.

∑ⱼxᵢⱼ = 1;  ∑ᵢxᵢ₁ ≤ 2;  ∑ᵢxᵢ₂ ≤ 1

1.9. Independent Verification and Implementation Constraints

All 2³ assignments can be enumerated independently. Tests should also verify that index ranges update correctly when the number of servers changes.

Unit 2: Linear Programming and the Feasible Region

2.1. Linearity and Convex Geometry

Linear programming uses linear objectives and constraints. Their intersection forms a convex polyhedron, which may be empty, bounded, or unbounded. A basic feasible solution corresponds to a set of independent active constraints. When a finite optimum exists and the polyhedron has vertices, at least one optimum can be attained at a vertex.

2.2. Transformation to Standard Form

Converting to standard form may introduce slack variables and split free variables into positive and negative parts. Mathematical unboundedness differs from a search that has not yet established a bound. Two-variable models permit geometric inspection; larger models require matrix representations.

min cᵀx;   Ax = b;   x ≥ 0

2.3. Vertices and Numerical Conditioning

For low-dimensional instances, evaluate all candidate vertices and compare objectives; inspect the linear independence of active constraints to assess conditioning. Mixing extremely small and large coefficients can compromise numerical stability.

2.4. Numerical and Algorithmic Example

For x+y≤6, 2x+y≤8, x,y≥0, point (2,4) is a feasible vertex. With maximization objective 3x+2y its value is 14, but the other vertices must also be evaluated before concluding optimality. Changing objective coefficients may change the maximizing vertex.

2.5. Polyhedral Geometry and Extreme Points

Intersecting linear inequalities produces a convex polyhedron. A nonempty bounded linear program admits an optimum at an extreme point; a feasible set containing a line need not have an extreme point. Degeneracy is associated with more active restrictions than required to determine a basic solution. Geometric reasoning must therefore be connected to basis matrices and linear independence in higher dimensions.

x* ∈ arg min{x∈ℱ} cᵀx

2.6. Phase I and Infeasibility Certificates

When no initial feasible basis is known, Phase I can introduce artificial variables. A strictly positive optimum of its auxiliary objective indicates infeasibility of the stated standard-form model, subject to numerical tolerance. For linear inequalities, Farkas' lemma characterizes infeasibility by an alternative separating certificate. A solver reporting infeasibility must be distinguished from a run that merely failed to find a solution before its time limit.

2.7. Scaling and Sparse Linear Algebra

Large coefficient scale differences can damage pivot selection and residual evaluation. Row and column scaling preserves the intended feasible region under the corresponding variable transformations while changing numerical behavior. Sparse matrix structures should store nonzero coefficients rather than dense zeros. After recovering a solution in original units, residuals must be recomputed against the original unscaled constraints.

2.8. Computational Example and Calculation

Consider maximizing 3x+2y under x+y≤6, 2x+y≤8 and nonnegative variables. Vertices (0,0), (0,6), (2,4) and (4,0) have objective values 0, 12, 14 and 12. Hence (2,4) is a global optimum.

max 3x+2y = 14   at (x,y)=(2,4)

2.9. Independent Verification and Implementation Constraints

Changing an objective coefficient may change the optimal vertex. An independent checker should evaluate linear constraints first and compute costs only for feasible vertices.

Unit 3: Simplex and Interior-Point Methods

3.1. Basic Solutions and Reduced Costs

The simplex method pivots between feasible bases according to reduced costs. Revised simplex methods factorize the basis matrix rather than maintaining a complete tableau, reducing storage. Degeneracy may cause zero-length pivots; unsuitable pivot rules may cause cycling.

3.2. Pivot and Primal–Dual Iterations

Interior-point methods follow iterates through the interior while reducing primal and dual residuals. Newton directions and step sizes determine factorization costs. Comparisons must consider sparse matrix structure, tolerances, and total time rather than iteration counts alone.

c̄[N] = c[N] − A[N]ᵀ (A[B]ᵀ)⁻¹ c[B]

3.3. Solution Residuals and Convergence Criteria

For small models, compare simplex basic solutions with interior-point solutions through objective values and residuals. Feasibility, optimality, and complementarity residuals should be checked independently at matched tolerances.

3.4. Numerical and Algorithmic Example

Given a basis matrix B, solve Bᵀy=c[B] for dual multipliers. Reduced-cost signs test optimality without forming an explicit dense matrix inverse. Interior-point methods instead decrease primal/dual residuals and complementarity simultaneously.

3.5. Revised Simplex and Basis Matrix Operations

Revised simplex updates sparse factorizations of the basis instead of rebuilding a full tableau at every iteration. Reduced costs are obtained from dual prices and the entering variable depends on the pricing strategy. The ratio test selects a leaving variable, but nearly zero pivots may lead to poor conditioning. A low iteration count is not necessarily a low computational cost: refactorization and pricing work must be measured as well.

Bᵀy = cᴮ;   rᴺ = cᴺ − (Aᴺ)ᵀy

3.6. Primal-Dual Interior-Point Systems

Primal feasibility, dual feasibility and complementarity residuals are reduced together. Solving the Newton system through normal equations or an augmented KKT system has different stability and memory implications. Reducing the barrier parameter too quickly may force tiny steps and stall progress. A crossover procedure can convert an interior-point result to a basic solution when downstream operations require a vertex representation.

3.7. Independent Verification of Stopping Criteria

A solver's optimal status should be audited by recomputing original Ax=b residuals, variable bounds, reduced costs and primal-dual objective differences. Timing comparisons between algorithms are meaningful only under matched feasibility and optimality tolerances. Separately recording matrix construction, presolve, solution and postprocessing time distinguishes mathematical algorithm cost from software infrastructure cost.

3.8. Computational Example and Calculation

For a two-variable standard-form example, select a basis matrix B; solve Bᵀy=cᴮ for dual prices and then obtain reduced costs. Linear system solves are preferred to constructing a full dense inverse.

Bᵀy = cᴮ;   rⱼ = cⱼ − Aⱼᵀy

3.9. Independent Verification and Implementation Constraints

After every pivot, verify primal feasibility and signs of reduced costs. An interior-point solution must be compared using the same original objective scale.

Unit 4: Duality Theory and Sensitivity Analysis

4.1. Primal and Dual Models

Primal and dual programs are related representations of one optimization problem. Weak duality states that any dual feasible objective is a lower bound on the value of a minimization primal. Under the applicable conditions strong duality equates optimal values, while complementary slackness characterizes active constraints.

4.2. Shadow Prices and Parameter Changes

Dual multipliers can describe the local effect of small right-hand-side changes on optimal value. This interpretation may cease to apply when the optimal basis or active set changes. Sensitivity intervals should be distinguished from actual reoptimization results.

cᵀx − bᵀy ≥ 0;   Aᵀy ≤ c;   y ∈ ℝᵐ

4.3. Duality Gap and Complementary Slackness

Validate primal and dual candidate solutions independently. A small duality gap does not establish optimality if constraint violations are substantial; scaled residuals are also required.

4.4. Numerical and Algorithmic Example

Increasing one right-hand-side capacity by a small amount can change the optimum according to its dual multiplier yᵢ, locally. Re-solve the model at multiple capacity values to identify where this shadow-price sensitivity ceases to be valid.

4.5. Weak and Strong Duality

For a primal minimization problem, a dual-feasible vector provides a lower bound on the primal objective. Weak duality makes this bound valid for every feasible primal-dual pair. Under suitable conditions, strong duality equates their optimal values. The distinction also explains bounds from linear relaxations of integer problems; linear strong duality does not directly imply strong duality for an arbitrary integer program.

bᵀy ≤ cᵀx;   Aᵀy ≤ c;   Ax = b;   x ≥ 0

4.6. Validity Range of Shadow Prices

A dual price approximates the local effect of perturbing the right-hand side of a resource constraint. This derivative interpretation is valid only while the relevant basis or regularity assumptions remain applicable. Large capacity changes may alter the active basis and make the response nonlinear. In software capacity planning, a shadow price is not automatically the monetary procurement or operating cost of a resource.

4.7. Parametric Reoptimization

New demand, cost or capacity data need not always require solving a model from scratch. Warm starts may reuse bases or candidate solutions, depending on how the constraint structure changed. Comparing parameter scenarios requires tracking input versions, solution statuses, valid lower and upper bounds, and computation times. A change in objective value alone does not establish what caused the change.

4.8. Computational Example and Calculation

Given primal-feasible x and dual-feasible y for a minimization LP, cᵀx−bᵀy cannot be negative. A near-zero duality gap together with small feasibility residuals supports optimality.

gap = cᵀx − bᵀy ≥ 0

4.9. Independent Verification and Implementation Constraints

Perturb one resource right-hand side and compare the locally predicted change using its dual price against the actual reoptimized solution.

Unit 5: Integer and Mixed-Integer Programming

5.1. Discrete Decisions and Linear Relaxation

Integer variables express discrete selection and logical decisions. The linear relaxation has a larger feasible region and therefore supplies a lower bound for minimization. Binary semantics, variable bounds, and big-M coefficients materially affect numerical reliability.

5.2. Assignment and Logical Constraints

In task assignment, exactly-one placement and per-server resource budgets can be expressed with linear constraints. When a big-M implication is unavoidable, derive a tight valid bound; an arbitrarily huge coefficient is not acceptable.

xⱼ ∈ {0,1};   ∑[j] xᵢⱼ = 1;   ∑[i] rᵢxᵢⱼ ≤ Cⱼ

5.3. Feasibility and Optimality Certificates

Finding an integer-feasible solution is not an optimality certificate. Report the relative difference between the best incumbent and the relaxation bound separately.

5.4. Numerical and Algorithmic Example

For a three-task binary placement model, its linear relaxation may assign one task fractionally to several machines. Such assignments are infeasible when tasks are indivisible; the lower relaxed cost is a bound, not a deployable assignment.

5.5. Linear Modeling of Logical Constraints

Binary variables encode activation, assignment and selection decisions. To forbid assigning work to an inactive server, assignment totals are linked to activation capacity. A big-M coefficient must be derived from a valid bound; an arbitrarily huge value weakens the relaxation and may cause numerical instability. Indicator constraints or stronger formulations should be preferred when supported.

∑ᵢ xᵢⱼ ≤ Cⱼyⱼ;   xᵢⱼ,yⱼ ∈ {0,1}

5.6. Linear Relaxation and Integrality Gap

Dropping integrality produces an LP relaxation, usually giving a valid lower bound for a minimization model. The integrality gap measures how far the relaxation can be from the discrete optimum. A stronger formulation may contain more rows but reduce the search tree through better bounds. Model comparisons should record root bounds, explored nodes and total time, not merely variable counts.

5.7. Verifiable Discrete Solutions

Floating-point values returned by a solver must not be rounded and accepted without checks. Integrality tolerances are examined first, then the rounded candidate is validated against the original constraints. Assigning one task to two servers is invalid even when its cost appears attractive. For critical applications, integer-coefficient constraints can be independently evaluated using exact arithmetic.

5.8. Computational Example and Calculation

Consider three items of weights 2, 3 and 4, values 4, 5 and 7, and knapsack capacity 5. Selecting the first two gives value 9; the third alone gives 7, while combining first and third violates capacity.

max 4x₁+5x₂+7x₃ = 9;  2x₁+3x₂+4x₃ ≤ 5

5.9. Independent Verification and Implementation Constraints

Enumerate the eight binary selections to confirm the optimum of 9. Compare with the LP relaxation to illustrate why a fractional bound can differ from the discrete optimum.

Unit 6: Branch-and-Bound and Cutting-Plane Methods

6.1. Branching Tree and Pruning Conditions

Branch-and-bound partitions the search space into subproblems. A node can be pruned when its optimistic bound cannot improve the best incumbent. Branching choices, bound quality, and node selection determine computational expense.

6.2. Valid Inequalities and Cutting Planes

Cutting planes remove fractional relaxation points while retaining every feasible integer solution. An invalid cut can eliminate the true optimum. Branch-and-cut combines both mechanisms to strengthen bounds.

gap = |z[inc] − z[bound]| / max(1, |z[inc]|)

6.3. Bound Quality and Stopping Criteria

Track explored nodes, incumbent value, best bound, and relative gap. Time-limited runs must state the achieved guarantee instead of claiming an unproved global optimum.

6.4. Numerical and Algorithmic Example

If a relaxed node assigns integer variable x=2.4, branch into x≤2 and x≥3. Together they cover all integer possibilities without overlap. A child can be pruned when its lower bound is no better than the incumbent.

6.4.1. Illustrative Pseudocode

best = +infinity; bound = -infinity
push(root relaxation)
while open_nodes:
    node = select(open_nodes)
    if infeasible(node) or lower_bound(node) >= best: continue
    if integral(node.solution): best = min(best, objective(node)); continue
    branch_on_fractional_variable(node)

6.5. Node Bounds and Branching Strategies

Branch-and-bound partitions discrete decisions into subproblems and computes a valid relaxation bound at each node. Best-bound and depth-first node selection trade memory requirements against early incumbent discovery. The branching variable may be selected using strong branching or pseudocost estimates. A valid lower bound must not be confused with the incumbent feasible upper bound.

LB ≤ z* ≤ UB;   bağıl boşluk = (UB − LB) / max(1, |UB|)

6.6. Valid Inequalities and Cutting Planes

A cutting plane must exclude the current fractional LP point without eliminating any integer-feasible point. Gomory, cover and problem-specific cuts tighten different relaxations. Adding unlimited cuts increases factorization overhead, so separation routines must be assessed for strength and numerical reliability. A single invalid cut can invalidate the claimed optimum.

6.7. Reporting Under Time Limits

At a time limit, a valid incumbent can be reported, but optimality may be claimed only when the gap has closed to the specified tolerance. Bounds from active nodes and valid cutting planes contribute to the final global bound. Reports should include the incumbent, certified bound, absolute and relative gaps, explored nodes and termination reason.

6.8. Computational Example and Calculation

Suppose a minimization search has incumbent 93 and a valid global lower bound of 82. The absolute gap is 11 and the normalized relative gap is approximately 11.83 percent, so optimality has not been certified.

absolute gap = 93 − 82 = 11;  relative gap = 11/93 ≈ 0.1183

6.9. Independent Verification and Implementation Constraints

Check that the reported bound is global across active nodes rather than a single-node estimate. A time-limited run must not be labeled optimal.

Unit 7: Transportation and Assignment Problems

7.1. Supply–Demand Balance and Transportation Models

Transportation models connect supply nodes to demand nodes through shipment costs. Balanced instances have equal total supply and demand; unbalanced models may be expressed with appropriate dummy nodes. Each admissible link is assigned a nonnegative flow variable.

7.2. Bipartite Matching Algorithms

The assignment problem is a one-to-one matching in a bipartite graph. Prohibited assignments should be modeled explicitly in the cost matrix. Hungarian and minimum-cost-flow methods solve the model through different data structures.

min ∑[i,j] cᵢⱼxᵢⱼ;   ∑[j] xᵢⱼ = sᵢ;   ∑[i] xᵢⱼ = dⱼ

7.3. Flow Conservation and Model Correctness

Supply and demand balances are validated by flow-conservation equations at every node. Misconfigured zero-cost dummy arcs may produce mathematically optimal but semantically invalid allocations.

7.4. Numerical and Algorithmic Example

Consider two sources with supplies (3,2) and two destinations with demands (2,3). The transportation model is balanced. Every row and column sum must match supply or demand. A flow imbalance makes a low-cost candidate infeasible.

7.5. Network Representation of Transportation Models

The transportation problem can be represented as a bipartite network where flows from supply nodes to demand nodes incur costs. A dummy node may balance unequal totals, but its penalty must reflect the actual operational assumption. Every feasible solution must respect node balances and nonnegativity. When the constraint matrix is totally unimodular, integer supplies and demands yield integer extreme-point solutions to its LP relaxation.

min ∑ᵢ∑ⱼ cᵢⱼxᵢⱼ;   ∑ⱼxᵢⱼ = sᵢ;   ∑ᵢxᵢⱼ = dⱼ

7.6. Hungarian Algorithm and Assignment Matching

For a square cost matrix, assignment reduces to minimum-weight perfect matching. The Hungarian algorithm maintains dual labels and constructs matching edges with zero reduced cost. Padding rectangular cases requires an explicit interpretation of dummy rows or columns. Assignment quality must be checked not only by total cost but also by forbidden pairings and one-to-one capacity.

7.7. Data Scale and Algorithm Selection

A dense assignment matrix has very different memory requirements from a sparse allowed-pair graph. Generating all task-resource pairs may be unnecessary when many links are forbidden or unreachable. A general-purpose MILP solver and a specialized min-cost-flow implementation may perform differently on the same mathematical model. Experiments require independently checking that both solve identical costs and feasibility restrictions.

7.8. Computational Example and Calculation

Let supplies be 3 and 2 and demands be 2 and 3, with cost rows (1,3) and (2,1). Sending two units from source one to destination one, one unit to destination two, and two units from source two to destination two gives cost 7.

cost = 2·1 + 1·3 + 2·1 = 7

7.9. Independent Verification and Implementation Constraints

Verify flow balances at every source and destination. Route exclusions and cost units must be represented explicitly.

Unit 8: Network Flows and Network Optimization

8.1. Node Balances and Edge Capacities

Network-flow models combine node-balance equations with edge capacities. Maximum flow seeks throughput, whereas minimum-cost flow minimizes cost subject to a specified flow requirement. Negative-cost cycles and capacity bounds affect model interpretation.

8.2. Residual Networks and Augmenting Paths

Residual networks contain forward and reverse arcs. Augmenting-path algorithms update residual capacities; Dinic builds blocking flows. Shortest-path and node-potential methods can be used for minimum-cost flow.

max |f|;   0 ≤ f[u,v] ≤ c[u,v];   ∑[u] f[u,v] = ∑[w] f[v,w]

8.3. Max-Flow Min-Cut Validation

Equality between an s–t cut capacity and a flow value certifies a maximum flow. Validate flow quantity, balance at intermediate nodes, and the cost calculation separately.

8.4. Numerical and Algorithmic Example

In a network with capacities s→a:3, a→t:2, and s→t:1, a total flow of three units is attainable. The cut separating {s,a} from t has capacity three, certifying maximum flow value three.

8.4.1. Illustrative Pseudocode

build_residual_graph(flow, capacities)
while exists_augmenting_path(source, sink):
    delta = minimum_residual_capacity(path)
    augment_forward_and_reverse_arcs(path, delta)
check_flow_conservation()
check_minimum_cut_certificate()

8.5. Residual Networks and Reverse-Arc Semantics

A residual network uses forward capacity for additional flow and reverse capacity for undoing earlier assignments. Searching only forward edges may fail to correct a previous routing choice and thus prevent reaching maximum flow. Flow conservation must hold at all intermediate vertices. An arc with zero residual capacity is excluded from augmentation, although the original edge metadata may still be retained.

cʳ(u,v) = c(u,v) − f(u,v);   cʳ(v,u) = f(u,v)

8.6. Max-Flow and Min-Cut Certificate

An independent maximum-flow certificate consists of the absence of an augmenting path and equality between flow value and the capacity of the reachable-set cut. Edmonds–Karp uses breadth-first augmenting paths; Dinic uses level graphs and blocking flows for stronger complexity bounds. Graph size, capacity distribution and sparsity determine comparative practical performance.

8.7. Distinct Objective of Minimum-Cost Flow

Maximum flow maximizes transported quantity; minimum-cost flow minimizes cost under specified flow values or node balances. Residual graphs with negative edge costs require appropriate potentials or cycle analysis. These two problems should not be conflated without defining demands and target flow. Verification checks delivered flow, edge capacities and total cost separately.

8.8. Computational Example and Calculation

Let capacities of s→a, a→t and s→t be 3, 2 and 1. Sending two units via s→a→t and one via s→t gives flow 3. The cut separating {s,a} from t also has capacity 3, certifying maximality.

max flow = min cut = 3

8.9. Independent Verification and Implementation Constraints

Test whether reverse residual edges allow rerouting earlier decisions. Flow conservation, cut capacity and arc bounds are independent invariants.

Unit 9: Nonlinear and Convex Optimization

9.1. Convexity and Local–Global Optimality

With a convex objective and convex feasible set, every local minimum is global. Nonlinear constraints require analysis of feasibility geometry and derivative information. Gradients, Hessians, and conditioning govern convergence.

9.2. Gradient Methods and KKT Conditions

Gradient-based methods specify step size, stopping tests, and projection operators. KKT conditions are necessary under suitable constraint qualifications and can become sufficient for appropriate convex problems.

∇f(x*) + ∑[i] λᵢ∇gᵢ(x*) = 0;   λᵢgᵢ(x*) = 0

9.3. Stationarity and Numerical Scaling

Sensitivity to initialization can be numerical even in convex models when scaling is poor, while nonconvex models can also exhibit distinct local solutions. Inspect both primal feasibility and stationarity residuals.

9.4. Numerical and Algorithmic Example

For f(x)=(x−3)² with x≥0, the derivative vanishes at x=3. The second derivative is positive and feasibility holds, yielding the global optimum. The same argument cannot be transferred unconditionally to a nonconvex objective.

9.5. Convexity and Global Optimality

A differentiable convex function lies above its tangent hyperplanes, linking first-order optimality conditions to global guarantees. A positive-semidefinite Hessian characterizes twice differentiable convex functions on convex domains; domain assumptions matter. For nonconvex optimization, satisfying KKT conditions may indicate a local minimum, a maximum or a saddle point.

f(y) ≥ f(x) + ∇f(x)ᵀ(y − x)

9.6. KKT Conditions and Constraint Qualifications

Multiplier sign restrictions and complementary slackness are essential for inequality constraints. Necessity of KKT conditions depends on a constraint qualification; sufficient global optimality conditions follow for convex problems under appropriate assumptions. Multiplier interpretation requires the model's scale and active-constraint structure. A solver reporting a stationary point is not thereby certifying a global optimum.

9.7. Gradient Methods and Numerical Differentiation

Gradient descent, Newton and quasi-Newton methods trade iteration cost, Hessian access, memory and convergence rate. Automatic differentiation follows the computational graph; finite differences suffer roundoff for tiny steps and truncation error for overly large steps. Termination should jointly consider gradient norms, step sizes and constraint violations.

9.8. Computational Example and Calculation

For f(x)=(x−3)² under x≥0, the optimum is x=3 with cost zero. Gradient 2(x−3) and Hessian 2 establish strong convexity. The feasible point x=0 fails optimality checks.

f′(x)=2(x−3);  f″(x)=2>0;  x*=3

9.9. Independent Verification and Implementation Constraints

A numerical solver should converge near x=3 from varied starts. Numerical residuals should be assessed with tolerances rather than treated as exact zeros.

Unit 10: Dynamic Programming and Multistage Optimization

10.1. State, Action, and the Bellman Recurrence

Dynamic programming defines a value function over states using optimal substructure. State variables must retain information sufficient to evaluate future cost; irrelevant history needlessly expands the state space. Memory and time depend on state and transition counts.

10.2. Staged Resource Allocation

In staged resource allocation, each action consumes some resource and changes the state. Backward value recursion starts at the terminal horizon. Cyclic and infinite-horizon variants require separate convergence and discount assumptions.

Vₜ(s) = min[a∈A(s)] {cₜ(s,a) + Vₜ₊₁(T(s,a))}

10.3. State Space and Verification

Validate small instances against exhaustive search. State compression preserves optimality only when merged states have equivalent admissible future actions and cost structure.

10.4. Numerical and Algorithmic Example

For four stages of resource allocation, let state equal remaining capacity and action equal the current allocation. Set terminal value to zero and recurse backward. Past cumulative cost need not be stored if remaining capacity sufficiently captures its impact on future feasible actions.

10.5. Assumptions of Bellman Optimality

Dynamic programming relies on the principle that optimal future decisions depend on a sufficient state rather than the full history. Omitting information needed for future costs or transitions invalidates Bellman recursion. Finite-horizon models can be solved backward, whereas infinite-horizon versions require discount or convergence assumptions. Dynamic programming across decision processes, graphs and sequence algorithms uses different state definitions.

Vₜ(s) = minₐ [cₜ(s,a) + Vₜ₊₁(T(s,a))]

10.6. State Explosion and Decomposition

State spaces may grow exponentially when resource counts, time steps and previous decisions are jointly encoded. Keeping only adjacent stages saves memory, while dictionary-based memoization suits sparsely visited states. Compressing states into approximate representations, however, may change correctness. The number of states, transitions and memory used should be measured on the same instances.

10.7. Policy Reconstruction and Optimal Trace

A table of optimal values alone may lose the sequence of decisions that attains them. Retaining argmin actions or predecessor pointers yields a traceable policy. Deterministic tie-breaking resolves multiple equally optimal actions reproducibly. The reconstructed policy should be replayed from its initial state to verify accumulated costs and terminal constraints.

10.8. Computational Example and Calculation

Consider two stages where each decision consumes zero or one resource unit. The state must include both time and remaining budget, since decisions affect future feasibility. Omitting budget makes apparently identical states have different future action sets.

state = (stage, remaining budget)

10.9. Independent Verification and Implementation Constraints

Replay the reconstructed policy to verify budget feasibility. Rolling value tables save memory, but predecessor data must survive if the decision sequence is needed.

Unit 11: Optimization under Uncertainty and Robust Optimization

11.1. Uncertainty Sets and Chance Constraints

A solution may be fragile when uncertain parameters are replaced by single point estimates. Robust optimization enforces constraints for all parameters in a declared uncertainty set, whereas chance constraints impose probabilistic requirements. Their guarantees have different meanings.

11.2. Two-Stage Stochastic Programming

Scenario-based stochastic programming separates first-stage decisions from recourse decisions after uncertainty is observed. Models permitting decisions to use unavailable future information are not implementable. Minimizing expected cost does not automatically control tail risks.

min[x] max[u∈𝒰] f(x,u);   P(g(x,ξ) ≤ 0) ≥ 1 − α

11.3. Out-of-Sample Validation

Calibrate uncertainty sets from relevant data and evaluate out-of-sample scenarios and sensitivity. Robust solutions should not be claimed to minimize cost in every realized scenario.

11.4. Numerical and Algorithmic Example

For capacity requirements with uncertain demand in [8,12], a robust no-shortage model may require at least 12 capacity units; a model based solely on expected demand may choose ten. The difference reflects the declared uncertainty and service guarantees.

11.5. Uncertainty Sets and Robust Decisions

Robust optimization chooses decisions that remain valid for parameters lying in a specified uncertainty set. Box and ellipsoidal sets induce different conservatism and solver structures. An oversized set can produce overly costly cautious decisions, while an undersized set offers insufficient protection. Uncertainty sets should be justified by measurement uncertainty and data provenance.

minₓ maxᵤ∈𝒰 f(x,u)

11.6. Chance Constraints and Scenario Approaches

Chance constraints require an inequality to hold at a prescribed probability. A misspecified probability distribution can make an apparently reliable design fail in deployment. Scenario feasibility on training samples alone does not certify a low out-of-sample violation probability. Independent test scenarios, confidence intervals and observed violation rates are necessary.

11.7. Multiobjective Solutions and Pareto Dominance

Optimizing latency, energy and cost together may not yield one universally best solution. Pareto dominance identifies decisions better in at least one objective without being worse in the others. Weighted sums depend on scaling and normalization, and can miss portions of a nonconvex Pareto frontier. Candidate trade-offs must still be validated against the original decision constraints.

11.8. Computational Example and Calculation

Suppose demand lies in [8,12] and capacity is chosen once. If every demand must be served without shortfall, capacity 12 is the smallest feasible robust choice. Capacity 10 based on the midpoint fails the robust requirement.

capacity ≥ max(demand) = 12

11.9. Independent Verification and Implementation Constraints

The claim of robustness is limited to the justified interval [8,12]. A chance constraint additionally requires a probability distribution.

Unit 12: Optimization Solvers and Solution Verification

12.1. Model–Solver Interfaces and Presolve

The modeling layer should represent variables, constraints, and objectives independently of a particular solver. Presolve may eliminate fixed variables, remove redundant constraints, and rescale coefficients. Solver statuses include optimal, feasible, infeasible, unbounded, and interrupted by limits.

12.2. Solver Statuses and Independent Checks

Application software must preserve the raw solver status, independently check feasible solutions, and report numerical tolerances. Without an optimality certificate, a result is merely a feasible candidate. The model version and input data should remain traceable.

rₚ = ‖Ax − b‖;   r[d] = ‖Aᵀy + s − c‖;   ε[gap] = |cᵀx − bᵀy|

12.3. Reproducible Solver Benchmarks

Benchmarks should align hardware, thread counts, random seeds, and time budgets. If geometric mean speedup is reported, treatment of unsolved instances must be specified before analysis.

12.4. Numerical and Algorithmic Example

If a solver reports x=(2,4) as optimal, the application independently checks Ax≤b against original data. It then reports objective, dual bound, and tolerances. A time-limit status may provide an incumbent without proving optimality.

12.4.1. Illustrative Pseudocode

assert validate_dimensions(model)
result = solver.solve(model, limits, tolerances)
assert result.status in declared_statuses
if result.has_candidate:
    assert validate_original_constraints(result.x, model)
    report(result.objective, result.bound, result.gap)

12.5. Semantic Distinctions Among Solver Statuses

OPTIMAL, FEASIBLE, INFEASIBLE, UNBOUNDED, TIME_LIMIT and NUMERICAL_ISSUE are different result categories. A timeout is not proof of mathematical infeasibility. When both a bound and a candidate are returned, both are needed for audit. Application adapters should map version-specific status codes to explicit semantics and must never treat an unknown status as optimal.

feasibility residual ≤ εₚ;   relative gap ≤ εₒ

12.6. Independent Auditing of Solution Certificates

Candidates must be validated in original variable domains because presolve and scaling transform the internal representation. Primal feasibility and dual bounds provide different kinds of evidence. Integer feasibility can be checked independently, whereas global optimality requires a valid bound and a closed gap. Regression suites should include exhaustively enumerable cases, degeneracy and poorly conditioned matrices.

12.7. Experimental Performance and Reproducibility

Algorithm comparisons need fixed hardware, instance versions, presolve policies and tolerances. Runtime distributions, timeouts and solution quality complement average timing. Speedups on a single instance cannot support broad performance claims. Recording random seeds, model files, solver versions and resource limits enables replication.

12.8. Computational Example and Calculation

Even when a solver returns an optimal status, original constraints need independent checks. At x=2, y=4 both x+y≤6 and 2x+y≤8 hold at equality; residual tolerances should be applied consistently across scales.

r₁ = 6−(2+4)=0;  r₂ = 8−(2·2+4)=0

12.9. Independent Verification and Implementation Constraints

Regression tests should also include infeasible, unbounded, multiply optimal and numerically ill-conditioned instances.

References

• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. 2024 Release. McGraw Hill, 2024. ISBN 9781266933226.