Optimization and Operations Research

Introduction

Optimization selects the best feasible decision from competing alternatives. In computer science engineering, it supports processor scheduling, cloud-resource allocation, network routing, machine-learning training, software release planning and supply-chain management. Operations research complements mathematical optimization with modeling, algorithms, simulation and decision analysis.

A useful model must distinguish three elements:

1. Decision variables—quantities controlled by the decision-maker.
2. Objective function—the performance measure to minimize or maximize.
3. Constraints—technical, logical, financial or regulatory restrictions.

A general minimization problem is

Here, x ∈ ℝⁿ is the decision vector, f is the objective, g_i are inequality constraints, h_j are equality constraints, and X may impose bounds, integrality or other structural restrictions. Variables and objective coefficients must use consistent units; for example, multiplying hours by cost per hour produces cost.

Learning Objectives

After studying this chapter, students should be able to:

• formulate unconstrained, constrained, linear, integer and convex optimization models;
• apply gradient descent and Newton’s method;
• derive and interpret Lagrange and Karush–Kuhn–Tucker conditions;
• solve a small linear program using simplex iterations;
• formulate and interpret primal–dual linear programs;
• solve a small integer program using branch-and-bound;
• formulate scheduling, allocation and routing problems;
• distinguish exact algorithms from heuristics and metaheuristics; and
• evaluate computational, managerial and ethical implications of optimized decisions.

1. Modeling Decisions

A model is an abstraction rather than a complete reproduction of reality. Its solution is useful only when assumptions, data and operational consequences are credible.

1.1 Classification of optimization problems

A model may have no feasible solution, one or many optimal solutions, or an unbounded objective. These outcomes have different managerial meanings and must not be confused with software failure.

2. Unconstrained Optimization

Consider differentiable f:ℝⁿ→ℝ. A necessary condition for an interior local minimizer x^* is

The gradient ∇f contains first partial derivatives. A point satisfying this equation is stationary, but it may be a minimum, maximum or saddle point.

If f is twice continuously differentiable, its Hessian matrix is

At a stationary point, a positive-definite Hessian implies a strict local minimum; a negative-definite Hessian implies a strict local maximum; an indefinite Hessian implies a saddle point. A positive-semidefinite Hessian alone may require further analysis.

2.1 Gradient descent

Gradient descent updates the decision vector by moving opposite the gradient:

Here, k is the iteration index and α_k>0 is the step size. The method is appropriate for differentiable objectives. A fixed step may converge slowly or diverge; line search or adaptive methods can improve reliability.

Worked example. Minimize f(x)=(x−3)²+1. Since f'(x)=2(x−3), gradient descent with α=0.25 gives

Starting with x₀=0, the iterates are x₁=1.5, x₂=2.25 and x₃=2.625, approaching the unique minimizer x^*=3, where f(x^*)=1.

2.2 Newton’s method

Newton’s method uses local curvature:

The Hessian must be nonsingular at the iterate. Near a strict minimizer with a positive-definite Hessian and adequate smoothness, convergence is typically quadratic. Far from a minimizer, damping or line search may be necessary.

For f(x)=x²−4, f'(x)=2x and f''(x)=2. From x₀=3,

Because the second derivative is positive everywhere, x=0 is the unique global minimizer, with objective value f(0)=−4. A negative objective value does not imply that a point is not a minimizer; optimization compares feasible objective values.

3. Equality and Inequality Constraints

3.1 Lagrange multipliers

For minimizing f(x) subject to h_j(x)=0, define

The multipliers ν_j measure local objective sensitivity to equality restrictions under suitable regularity conditions. First-order necessary conditions are

3.2 Karush–Kuhn–Tucker conditions

Use the minimization sign convention

and define

At a regular local optimum, the KKT conditions are:

Stationarity

Primal feasibility

Dual feasibility

Complementary slackness

Equality multipliers ν_j are unrestricted in sign. If inequalities are instead written as g_i(x)≥0, the multiplier convention must be changed consistently.

For a convex differentiable problem—convex f and g_i, affine equalities—the KKT conditions are sufficient for global optimality. Under a constraint qualification such as Slater’s condition, they are also necessary and strong duality holds.

3.3 Worked inequality-constrained problem

Minimize

subject to x+y≤2, x≥0 and y≥0. Write

The unconstrained minimizer (2,1) is infeasible. The closest feasible point lies on x+y=2. The Lagrangian is

Because the solution has positive coordinates, g₂<0 and g₃<0, so complementary slackness gives λ₂=λ₃=0. Stationarity gives

Together with x+y=2, these equations yield

All multipliers satisfy dual feasibility, and the objective value is

The objective and feasible region are convex, and the point (0.5,0.5) satisfies all inequalities strictly. Thus Slater’s condition holds and the KKT solution is globally optimal.

4. Convex Optimization

A set C is convex if, for every x,y∈C and θ∈[0,1],

A function f is convex on C if

For a twice-differentiable function on a convex open set, ∇²f(x) being positive semidefinite everywhere is sufficient and necessary for convexity. The major computational benefit is that every local minimum of a convex optimization problem is global.

Strict convexity implies at most one minimizer, although existence still requires appropriate continuity and feasible-set conditions. Convexity does not guarantee inexpensive computation for every representation, but many important convex classes have efficient algorithms.

5. Linear Programming and the Simplex Method

An LP in standard inequality form is

Here, x contains decision quantities, c contains objective contribution per unit, A contains resource usage per unit, and b contains available resources. All relationships are linear and coefficients are assumed known.

5.1 Simplex iterations: a complete example

Consider

subject to

Introduce nonnegative slacks s₁,s₂,s₃:

The initial basic feasible solution is (x₁,x₂)=(0,0) with basis (s₁,s₂,s₃)=(4,2,3).

Iteration 1. Variable x₁ enters because its objective coefficient, 3, gives the largest immediate improvement. The ratio test is min(4÷1,2÷1)=2, so s₂ leaves. From x₁+s₂=2,

Substitution produces the dictionary

At nonbasic x₂=s₂=0, the new solution is (x₁,x₂)=(2,0) with z=6.

Iteration 2. Since the coefficient of x₂ in the objective dictionary is positive, x₂ enters. The applicable ratios are 2 from the first row and 3 from the third, so s₁ leaves. Solving the first row gives

Substitution gives

Increasing either nonbasic variable s₁ or s₂ cannot improve z. Therefore,

The third resource has slack s₃=1. Simplex traverses adjacent vertices rather than testing every feasible point. Degeneracy, cycling and numerical conditioning require careful implementation; anti-cycling pivot rules and presolve procedures are commonly used.

6. Duality and Sensitivity

The dual of the preceding general maximization LP is

Each dual variable is associated with a primal resource constraint. Weak duality states that every dual feasible objective is an upper bound on every primal feasible objective for this max–min convention:

If both LPs have optimal solutions, strong duality gives equality of their optimal objective values.

For the simplex example, the dual is

subject to

The solution (y₁,y₂,y₃)=(2,1,0) is feasible and has value 10, proving that the primal solution with value 10 is optimal. The zero value of y₃ is consistent with the unused third resource.

A dual value is often interpreted as a shadow price: the marginal change in optimal objective value caused by a one-unit increase in a resource, while the current optimal basis remains valid. This interpretation is local and should not be extrapolated beyond its allowable sensitivity range.

7. Integer Optimization and Branch-and-Bound

Integer restrictions represent indivisible servers, vehicles, facilities and yes/no decisions. Binary variables satisfy x_i∈{0,1}. Solving the LP relaxation—removing integrality—provides a bound but may produce operationally impossible fractional answers.

7.1 Systematic branch-and-bound example

Consider

subject to

Root node. The LP relaxation has the intersection

which gives x=3, y=1.5 and upper bound 5(3)+4(1.5)=21. Because y is fractional, branch on y≤1 and y≥2.

Node A: y≤1. Its LP optimum is y=1, x=10/3, with upper bound

Branch on x≤3 and x≥4.

• Node A1: y≤1,x≤3. The LP optimum is the integer point (3,1) with value 19. It becomes the incumbent.
• Node A2: y≤1,x≥4. Feasibility forces (x,y)=(4,0), with LP bound and integer value 20. The incumbent becomes 20, and the node is fathomed by integrality.

Node B: y≥2. The LP optimum is (2,2) with bound 18. Because 18 cannot exceed the incumbent value 20, the entire node is pruned by bound.

Figure: Branch-and-bound nodes are fathomed by integrality or pruned when their LP bound cannot improve the incumbent.

Therefore, the optimal integer solution is (x,y)=(4,0) with value 20. Branch-and-bound is systematic: every unexplored node is eliminated only by infeasibility, integrality or a valid bound—not by informal enumeration.

8. Scheduling, Allocation and Routing Models

8.1 Assignment and scheduling

Let x_ij=1 if job i is assigned to machine j, and 0 otherwise. If c_ij is processing cost, a basic assignment model is

subject to

Here, q_j is machine capacity measured in compatible job units. Time-indexed formulations, precedence constraints and setup variables extend the model to detailed scheduling.

8.2 Explicit routing formulation

For a directed traveling salesperson problem, let V={1,…,n} be locations, location 1 be the depot, c_ij be travel distance or cost from i to j, and x_ij=1 when arc (i,j) is used. The model is

subject to

Degree constraints alone can create disconnected subtours. Miller–Tucker–Zemlin constraints eliminate them:

The order variables u_i identify visit positions for nondepot locations. Vehicle-routing models add vehicle capacities, customer demands, time windows and multiple vehicles. If c_ij is in kilometres, the objective is total kilometres; if it includes monetary and environmental components, their units must first be normalized or monetized consistently.

9. Heuristics and Metaheuristics

Exact methods certify optimality but may become impractical for large combinatorial problems. A heuristic seeks a good feasible solution without guaranteeing global optimality.

Common approaches include:

• greedy construction: repeatedly make the best immediate choice;
• local search: replace a solution with a better neighboring solution;
• simulated annealing: sometimes accept worsening moves to escape local minima;
• tabu search: discourage recently visited moves;
• genetic algorithms: evolve populations through selection and variation;
• ant-colony methods: use reinforced probabilistic path construction.

For routing, a nearest-neighbor tour can be improved using 2-opt edge exchanges. For scheduling, earliest-due-date and shortest-processing-time rules offer fast decisions but optimize only under particular assumptions.

Best practice is to report feasibility, runtime, the best known bound and the optimality gap. For a maximization problem with incumbent L>0 and valid upper bound U, one common relative gap is

The denominator convention varies among solvers and must be documented.

10. Illustrative Case: Cloud Workload Allocation

Background and problem

A fictional software company must allocate a nightly analytics workload between standard and accelerator cloud instances. Let x and y denote billed instance-hours of the two types. Standard hours cost 2 currency units and accelerator hours cost 3 units.

Each standard hour provides 4 compute units and 8 memory-service units; each accelerator hour provides 10 compute units and 6 memory-service units. The workload requires at least 100 compute units and 96 memory-service units. At most 20 standard and 12 accelerator hours are available.

Continuous model

subject to

At the intersection of the two service constraints,

Solving gives

The cost is

The point satisfies both availability bounds. Comparison with the other feasible vertices confirms that it is the continuous optimum.

Integer billing decision

If only whole instance-hours may be purchased, x and y must be nonnegative integers. Testing integer candidates implied by the binding requirements—or solving the MIP—gives

This allocation supplies 4(6)+10(8)=104 compute units and 8(6)+6(8)=96 memory-service units. It is feasible, and no lower-cost integer pair meets both requirements. The integrality premium over the continuous optimum is approximately 36−35.143=0.857 currency units.

Outcome and learning points

The continuous solution provides a lower bound and reveals the desired resource mix; the integer model produces an implementable purchase. Before deployment, managers should test uncertain workload forecasts, service-level requirements, outage risks and carbon intensity. A mathematically optimal plan based on inaccurate forecasts may be operationally inferior to a slightly more expensive robust plan.

11. Limitations, Governance and Contemporary Practice

Optimization models inherit weaknesses from their data and assumptions. Linear coefficients may ignore congestion, nonlinear performance degradation or uncertainty. Large MIPs can require substantial computation, while heuristics may return inconsistent solution quality.

Responsible practice includes:

• validating data lineage and coefficient units;
• documenting objective choices and excluded impacts;
• testing sensitivity and adverse scenarios;
• preventing discriminatory allocation or scheduling rules;
• protecting personal and commercially sensitive data;
• maintaining human review for high-impact decisions; and
• monitoring deployed solutions for model drift.

Machine learning increasingly predicts demand, travel time or processing duration, while optimization converts predictions into actions. This “predict-then-optimize” pipeline can propagate prediction bias. Contemporary methods therefore include robust optimization, stochastic programming, distributionally robust optimization, learning-augmented algorithms and differentiable optimization layers. AI can also propose models or heuristics, but feasibility, units, constraint completeness and optimality claims still require independent verification.

Chapter Summary

Optimization formalizes decisions through variables, objectives and constraints. Gradient descent and Newton’s method solve smooth unconstrained problems, while Lagrange multipliers and explicit KKT conditions characterize constrained optima. Convexity is especially valuable because local minima are global and KKT conditions become sufficient under appropriate assumptions.

Linear programs can be solved by simplex iterations, and dual variables provide bounds and local resource valuations. Integer programs represent indivisible decisions; branch-and-bound uses LP bounds to prune nodes systematically. Assignment, scheduling and routing models translate operational requirements into mathematical constraints. Exact algorithms provide certificates, whereas heuristics trade guarantees for speed. Effective professional use additionally requires sensitivity analysis, reliable data, ethical governance and careful interpretation.

Key Terms

Decision variable: A controllable quantity represented in an optimization model.

Objective function: The numerical performance criterion to minimize or maximize.

Feasible solution: A decision satisfying every constraint and domain restriction.

Gradient: The vector of first partial derivatives of a scalar function.

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

Newton’s method: A curvature-based iterative method for smooth optimization.

Lagrangian: A function combining an objective with weighted constraints.

KKT conditions: Stationarity, feasibility and complementary-slackness conditions for constrained optimization.

Convex set: A set containing every line segment between any two of its points.

Convex function: A function lying below or on every chord connecting points on its graph.

Linear program: An optimization problem with a linear objective and linear constraints.

Simplex method: An LP algorithm that moves between adjacent basic feasible solutions.

Duality: The relationship between a primal optimization problem and an associated dual problem.

Shadow price: A local marginal value associated with relaxing a constraint.

Integer program: An optimization model requiring selected variables to be integers.

LP relaxation: A model obtained by removing integer restrictions.

Branch-and-bound: An exact tree-search method using branching, bounds and pruning.

Incumbent: The best feasible integer solution currently known.

Heuristic: A method seeking good feasible solutions without an optimality guarantee.

Optimality gap: The reported difference between an incumbent objective and a valid bound.

Review Questions

Short Answer Questions

1. What are the three principal components of an optimization model?
2. Why is a stationary point not necessarily a minimum?
3. State complementary slackness using the convention g_i(x)≤0.
4. What information does an LP relaxation provide in branch-and-bound?
5. Why are subtour-elimination constraints required in a TSP formulation?

Long Answer Questions

1. Explain gradient descent and Newton’s method, including convergence advantages and limitations.
2. Derive all KKT conditions for a differentiable minimization problem with equality and inequality constraints.
3. Explain the simplex method using entering variables, leaving variables, ratio tests and optimality conditions.
4. Discuss weak duality, strong duality, complementary slackness and shadow-price interpretation.
5. Compare exact algorithms, heuristics and metaheuristics for large scheduling and routing problems.

Analytical / Application Questions

1. Minimize (x−4)²+(y−2)² subject to x+y≤4 and x,y≥0. Solve using KKT conditions and verify global optimality.
2. Formulate a binary assignment model for four programmers and three projects when every programmer must receive one project and each project has a stated capacity.
3. Extend the cloud-allocation case by adding a carbon budget. Explain how the new constraint could change the optimum and how its dual value would be interpreted.

Multiple Choice Questions with Answers

Question 1

For f(x,y)=x²+3y², what is the gradient at (1,−1)?

A. (2,−6)

B. (1,−3)

C. (2,6)

D. (−2,6)

Correct Answer: A. (2,−6)

Question 2

Applying Newton’s method to f(x)=x²−4 from x₀=3 produces which next iterate?

A. −4

B. 0

C. 1.5

D. 3

Correct Answer: B. 0

Question 3

Under the minimization convention g_i(x)≤0 and L=f+∑λ_ig_i, dual feasibility requires:

A. λ_i≤0

B. λ_i=0 for every constraint

C. λ_i≥0

D. No sign restriction on λ_i

Correct Answer: C. λ_i≥0

Question 4

What is the optimal objective value of the chapter’s LP max\ 3x₁+2x₂ subject to x₁+x₂≤4, x₁≤2 and x₂≤3?

A. 6

B. 8

C. 9

D. 10

Correct Answer: D. 10

Question 5

For a primal maximization LP and its corresponding dual minimization LP, every dual feasible objective value is:

A. An upper bound on every primal feasible objective value

B. A lower bound on every primal feasible objective value

C. Always equal to the primal objective value

D. Necessarily negative

Correct Answer: A. An upper bound on every primal feasible objective value

Question 6

In the branch-and-bound example, why is the node y≥2 pruned after an incumbent of 20 is found?

A. The node is infeasible

B. Its LP upper bound is 18

C. Its variables are continuous

D. Its LP lower bound is 21

Correct Answer: B. Its LP upper bound is 18

Question 7

In the directed TSP formulation, the constraints ∑_j≠ix_ij=1 ensure that:

A. Every route has minimum cost

B. Every location has exactly one incoming arc

C. Exactly one arc leaves each location

D. Subtours cannot occur

Correct Answer: C. Exactly one arc leaves each location

Question 8

What is the optimal whole-hour allocation in the cloud case?

A. x=8,y=6

B. x=7,y=7

C. x=5,y=8

D. x=6,y=8

Correct Answer: D. x=6,y=8

Question 9

Which statement is guaranteed for a convex optimization problem with a convex objective and convex feasible region?

A. Every local minimum is a global minimum

B. Every stationary point is a strict maximum

C. Every feasible point is optimal

D. The optimum must have integer coordinates

Correct Answer: A. Every local minimum is a global minimum

Question 10

Which equation expresses complementary slackness for an inequality g_i(x)≤0?

A. λ_i+g_i(x)=0

B. λ_ig_i(x)=0

C. λ_i=g_i(x)

D. λ_i−g_i(x)=1

Correct Answer: B. λ_ig_i(x)=0