11. Optimization and Mathematical Decision Models

Introduction and Context

Computer science systems are designed and operated under constraints. A cloud provider allocates virtual machines to applications, a delivery platform assigns vehicles to routes, a compiler chooses an efficient execution plan, and a data centre distributes workloads while limiting energy consumption. In each case, several feasible alternatives exist, but they differ in cost, speed, reliability, risk, or resource use. Optimization provides a systematic way to select the most desirable alternative.

An optimization problem consists of decision variables, an objective function, and constraints that describe what is permissible. The objective may be maximized, such as throughput or profit, or minimized, such as delay, energy use, or operating cost. Mathematical decision models translate practical situations into a form that can be analysed by algorithms and interpreted by managers, engineers, and policy makers.

At postgraduate level, optimization is not merely the study of algorithms. It also concerns model formulation, assumptions, computational complexity, sensitivity to data, trade-offs among objectives, and the responsible use of automated recommendations. A mathematically elegant solution is of limited value if the model omits an important operational constraint or relies on unreliable data.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Formulate linear, integer, nonlinear, convex, and multi-objective optimization models.

2. Distinguish feasible, optimal, locally optimal, and globally optimal solutions.

3. Explain the role of duality, shadow prices, complementary slackness, and sensitivity analysis.

4. Apply gradient-based methods and constraint-handling techniques to suitable problems.

5. Interpret optimization results in operational and managerial contexts.

6. Identify modelling errors, computational limitations, ethical risks, and governance requirements.

7. Evaluate contemporary applications involving analytics, automation, and artificial intelligence.

From a Practical Decision to a Mathematical Model

The first task in optimization is not selecting an algorithm; it is defining the decision. Let the vector of decisions be

\[

x=(x_1,x_2,\ldots,x_n).

\]

An objective function \(f(x)\) measures the performance of a decision. A general constrained optimization problem can be written as

\[

\begin{aligned}

\text{minimize or maximize } & f(x)\\

\text{subject to } & g_i(x)\leq 0,\quad i=1,\ldots,m,\\

& h_j(x)=0,\quad j=1,\ldots,p,\\

& x\in X.

\end{aligned}

\]

The set of all points satisfying the constraints is the feasible region. A feasible solution is optimal if no other feasible solution gives a better objective value. A model may contain continuous variables, such as CPU capacity, or discrete variables, such as whether a server is switched on. It may also contain parameters representing demand, costs, capacities, probabilities, or technological coefficients.

A useful modelling discipline is to separate decisions from data. For example, in a server allocation problem, the number of virtual machines assigned to application \(i\) is a decision variable, whereas the application’s predicted demand and the capacity of each server are parameters. Confusing these categories can produce a model that appears mathematically valid but cannot be implemented.

Linear Programming

A linear program (LP) has a linear objective and linear constraints:

\[

\begin{aligned}

\text{maximize } & c^Tx\\

\text{subject to } & Ax\leq b,\\

& x\geq 0.

\end{aligned}

\]

Here, \(x\) is the decision vector, \(c\) contains objective coefficients, \(A\) is the constraint matrix, and \(b\) contains resource limits. Linearity means that marginal effects are constant and additive. If one unit of a product uses two units of labour, ten units use twenty units, regardless of production scale.

The feasible region of an LP is a convex polyhedron. When an optimum exists, at least one optimum occurs at an extreme point, or vertex, of that region. This geometric fact supports the simplex method. Interior-point methods instead move through the interior of the feasible region and have strong theoretical and practical performance for many large-scale LPs.

Consider a simplified cloud-resource problem. Suppose a provider allocates standard and high-memory instances. Let \(x_1\) and \(x_2\) denote their numbers. If their profits are 4 and 7 units, memory consumption is 2 and 5 units, and processing consumption is 3 and 2 units, the model may be

\[

\begin{aligned}

\text{maximize } &4x_1+7x_2\\

\text{subject to }&2x_1+5x_2\leq 40,\\

&3x_1+2x_2\leq 30,\\

&x_1,x_2\geq0.

\end{aligned}

\]

The solution identifies the best allocation under the assumptions. The model does not, by itself, establish whether demand is sufficient, whether workload performance is stable, or whether customers have service-level commitments. Those issues must be represented or assessed separately.

Integer and Mixed-Integer Optimization

Many decisions are inherently discrete. A server cannot be activated 0.37 times, and a project is usually either selected or not selected. Integer programming requires some or all variables to take integer values. A mixed-integer linear program (MILP) combines continuous and integer variables.

Binary variables are particularly useful. Let \(y_j\in\{0,1\}\) indicate whether facility \(j\) is opened. A fixed-cost facility model can include

\[

\text{minimize } \sum_j F_jy_j+\sum_{i,j}c_{ij}x_{ij},

\]

where \(x_{ij}\) is the amount of demand from location \(i\) served by facility \(j\). A linking constraint such as \(x_{ij}\leq M y_j\) prevents assignments to a facility that has not been opened. The constant \(M\) must be a valid and preferably tight upper bound. An unnecessarily large value can weaken the formulation and slow computation.

The LP relaxation of an integer model is obtained by replacing integrality restrictions with continuous bounds. Its solution provides a bound and may guide search, but it may not be implementable. Branch-and-bound partitions the search space into subproblems, uses bounds to discard inferior branches, and can employ cutting planes to tighten the relaxation. Integer optimization is often computationally difficult in the worst case, so time limits, heuristics, decomposition, and approximation may be necessary.

Nonlinear and Convex Optimization

A nonlinear model contains a nonlinear objective or constraint. Examples include congestion costs, quadratic risk measures, economies of scale, and physical performance relationships. A general nonlinear program is

\[

\min_x f(x)\quad\text{subject to }g_i(x)\leq0,\,h_j(x)=0.

\]

Convexity is central because it determines whether local information is globally reliable. A function \(f\) is convex on a convex set if

\[

f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y)

\]

for all feasible \(x,y\) and \(0\leq\lambda\leq1\). In a convex minimization problem, every local minimum is a global minimum. This property does not mean that computation is effortless, but it substantially improves assurance about solution quality.

The gradient \(\nabla f(x)\) gives the direction of greatest local increase. Gradient descent updates a point according to

\[

x^{(k+1)}=x^{(k)}-\alpha_k\nabla f(x^{(k)}),

\]

where \(\alpha_k\) is a step size. If constraints are present, the new point must remain feasible or be corrected using projection, a penalty function, a barrier method, or a constrained optimization procedure.

For a differentiable unconstrained function, a necessary condition for an interior optimum is \(\nabla f(x^*)=0\). This condition is not sufficient in general: the point may be a maximum or saddle point. The Hessian matrix, containing second derivatives, helps classify local behaviour. A positive semidefinite Hessian throughout a domain indicates convexity for a twice-differentiable function.

Constrained Optimization and the Language of Duality

Constraints are not merely technical restrictions. They express scarcity, policy, safety, quality, legal requirements, and physical feasibility. The Lagrangian combines an objective with constraints. For a minimization problem with inequality constraints \(g_i(x)\leq0\) and equality constraints \(h_j(x)=0\), it is commonly written as

\[

L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\sum_j\nu_jh_j(x),

\]

where \(\lambda_i\geq0\) are inequality multipliers and \(\nu_j\) are unrestricted equality multipliers.

The Karush–Kuhn–Tucker (KKT) conditions provide necessary conditions for many constrained nonlinear problems and, under suitable convexity and regularity assumptions, are also sufficient. They include:

• primal feasibility: the original constraints hold;
• dual feasibility: inequality multipliers are nonnegative;
• stationarity: the gradient of the Lagrangian with respect to the decisions is zero;
• complementary slackness: \(\lambda_i g_i(x)=0\) for every inequality constraint.

Complementary slackness has an important interpretation. If a resource constraint is not binding, its multiplier is zero under the usual conditions. If its multiplier is positive, the resource is scarce at the margin and relaxing it can improve the objective.

The dual of an LP assigns values to constraints and produces a related optimization problem. For a primal maximization problem with \(Ax\leq b\) and \(x\geq0\), the dual commonly takes the form

\[

\min_{y\geq0} b^Ty\quad\text{subject to }A^Ty\geq c.

\]

Weak duality states that every feasible dual solution bounds every feasible primal solution in the appropriate direction. Under standard conditions, strong duality states that optimal objective values are equal. Duality is valuable for verification, resource valuation, decomposition, and sensitivity analysis. The dual variable associated with a capacity constraint is often called a shadow price: approximately, it measures the change in optimal objective value caused by a one-unit increase in that capacity, within a valid range.

Multi-Objective Decision Models

Real decisions rarely have one universally accepted objective. A data-centre manager may seek low cost, low energy consumption, high availability, and equitable service. These objectives can conflict. Multi-objective optimization represents the conflict rather than hiding it in a single arbitrary score.

A decision \(x^*\) is Pareto efficient if no feasible decision improves one objective without worsening at least one other objective. The collection of efficient solutions is the Pareto frontier. A common scalarization is the weighted-sum model:

\[

\min_x\sum_{k=1}^{r}w_k f_k(x),\qquad w_k\geq0,

\]

after objectives have been normalized to comparable scales. The weights express preferences, not objective truth. Poor scaling can cause one objective to dominate numerically. The epsilon-constraint method optimizes one objective while imposing bounds on the others, allowing systematic exploration of trade-offs.

Preference elicitation should involve stakeholders. A manager may specify a maximum acceptable latency, while a compliance officer may require a minimum fairness level. Presenting several Pareto-efficient alternatives is often more defensible than presenting one apparently precise answer.

Sensitivity, Uncertainty, and Robustness

An optimization result is conditional on its data and assumptions. Sensitivity analysis examines how the solution or objective value changes when parameters vary. In LP, allowable ranges for objective coefficients and right-hand-side values identify intervals over which the current basis remains optimal. Shadow prices quantify local value, but they should not be extrapolated beyond those ranges.

Uncertainty can be handled in several ways. Scenario analysis evaluates decisions under alternative demand, cost, or failure conditions. Stochastic programming represents uncertain quantities with probability distributions and may optimize expected performance or risk-adjusted performance. Robust optimization seeks solutions that remain acceptable for all values in a specified uncertainty set. Robust solutions can be less optimal under the nominal scenario but safer when predictions are unreliable.

A distinction must be made between model uncertainty and parameter uncertainty. Parameter uncertainty concerns the value of a known quantity, such as demand. Model uncertainty concerns whether the assumed relationship is correct, such as whether latency increases linearly with load. Better measurement cannot fully solve a wrongly specified model.

A Practical Modelling Workflow

A reliable optimization study usually follows a cycle rather than a single calculation.

First, define the decision context, stakeholders, time horizon, and success criteria. Second, specify decision variables with units and domains. Third, construct the objective and constraints from operational relationships. Fourth, test dimensions, signs, bounds, and extreme cases. Fifth, select an algorithm appropriate to the mathematical structure and scale. Sixth, validate the model against historical or simulated behaviour. Seventh, perform sensitivity and scenario analysis. Finally, communicate assumptions, trade-offs, limitations, and implementation responsibilities.

Model validation should include a feasibility check. A solution that violates a service-level requirement because the requirement was omitted is not an optimization success. It is also useful to compare the optimized solution with a current policy, a simple heuristic, and deliberately perturbed data. Such comparisons reveal whether the result is robust or merely exploiting an artefact of the input.

Applied Case: Capacity Planning for a Regional Cloud Platform

Background

The following is an illustrative case. A regional cloud platform must decide which of three data-centre zones to activate for the next planning period. Activating a zone incurs a fixed cost. Once active, a zone can host workloads and contributes computing and memory capacity. Customer demand is forecast by application class, but the forecast is uncertain.

Situation and Model

Let \(y_j\) be a binary variable indicating activation of zone \(j\), and \(x_{ij}\) the number of workload units of class \(i\) assigned to zone \(j\). The objective is to minimize fixed activation cost, variable operating cost, and a penalty for unmet demand:

\[

\min \sum_jF_jy_j+\sum_{i,j}c_{ij}x_{ij}+P\sum_i u_i,

\]

where \(u_i\) is unmet demand and \(P\) is a large service penalty. Demand balance is represented by

\[

\sum_jx_{ij}+u_i=d_i.

\]

Capacity constraints link resource consumption to activated zones:

\[

\sum_i a_i x_{ij}\leq C_jy_j,

\qquad

\sum_i b_i x_{ij}leq M_jy_j.

\]

Additional constraints may require geographic redundancy, limit concentration of workloads, or reserve capacity for priority customers. If latency depends on load, a linear approximation may be inadequate; a convex congestion term or scenario-based constraint may be more suitable.

Analysis and Approach

The planning team first solves a MILP using forecast demand. It then solves the model under high-demand and failure scenarios. A nominal solution activates two zones at low cost but leaves little reserve capacity. A robust alternative activates a third zone and has a higher fixed cost, yet it maintains service under a major demand increase and the loss of one zone.

The team also examines the dual information from the continuous allocation subproblem. A high shadow price for memory indicates that purchasing additional memory or improving memory efficiency may be more valuable than acquiring more CPU. This prevents management from making investment decisions based only on total capacity.

A multi-objective analysis is then performed with cost, energy, and availability as objectives. Rather than choosing weights without consultation, the team presents several Pareto-efficient plans. The operations manager selects a plan satisfying a minimum availability target and then minimizes cost among those plans.

Outcome

The selected plan is not simply the plan with the lowest nominal cost. It is the least-cost plan satisfying service, redundancy, and robustness requirements. The model is deployed as a decision-support tool, not as an uncontrolled automatic switch. Forecasts are refreshed, assumptions are monitored, and the plan is re-optimized when demand or energy prices change materially.

Learning Points

The case illustrates five principles. Fixed and variable decisions often require mixed-integer models. Forecast uncertainty should be tested rather than hidden. Shadow prices can guide investment. Multi-objective analysis makes trade-offs explicit. Finally, operational adoption requires governance, monitoring, and human accountability in addition to mathematical optimization.

Applications in Computing and Management

Optimization is used in network routing, bandwidth allocation, wireless frequency assignment, software project selection, database query planning, container placement, cybersecurity resource allocation, inventory management, workforce scheduling, and energy-aware computing. In machine learning, training often involves minimizing a loss function, although practical training may involve nonconvex objectives, stochastic gradients, regularization, and constraints.

In management, optimization supports budgeting, portfolio selection, supply-chain design, pricing, staffing, and capital allocation. The managerial value lies in clarifying trade-offs and exposing the consequences of constraints. The model should support deliberation rather than replace judgement where values, rights, or uncertain strategic considerations cannot be fully quantified.

Modern solvers provide modelling languages, presolve routines, parallel branch-and-bound, automatic differentiation, and interfaces to data platforms. AI systems may predict demand or estimate costs, while optimization converts predictions into actions. This combination is powerful but creates a dependency: biased or poorly calibrated predictions can produce systematically poor decisions at scale. Predictive accuracy therefore cannot be treated as a substitute for decision validity.

Challenges, Risks, and Common Modelling Errors

A frequent error is optimizing a proxy that does not represent the real objective. Minimizing average response time may increase the delay experienced by a small but important group. Another error is omission of constraints, particularly legal, safety, fairness, or operational constraints that are difficult to express numerically.

Other common problems include inconsistent units, double counting resources, unrealistic bounds, incorrect inequality directions, overly large big-M constants, and treating a fractional solution as implementable. Correlation may be mistaken for causation when historical data are used to estimate objective coefficients. A model can also become infeasible because requirements conflict; infeasibility analysis and carefully designed relaxation variables are useful diagnostic tools.

Nonconvex models may have many local optima, and gradient methods can depend strongly on initialization and step-size selection. Solver status must be examined: a time-limited integer solution may be feasible but not proven optimal. Numerical tolerances can matter when coefficients differ greatly in magnitude. Scaling, presolve diagnostics, and independent verification reduce these risks.

Ethical and Governance Considerations

Optimization affects people when it allocates jobs, credit, medical resources, educational opportunities, or public services. A mathematically optimal solution can still be ethically unacceptable if it discriminates, lacks transparency, or imposes disproportionate burdens. Fairness constraints, auditing, explainable trade-offs, and appeal mechanisms may be necessary.

Governance should specify who owns the model, who approves objective functions and constraints, how data quality is checked, and when human review is mandatory. Sensitive data require privacy protection and access control. Decisions with legal or human-rights implications should not be justified solely by the statement that “the algorithm selected it.” Documentation should record assumptions, versions, parameter changes, validation results, and known limitations.

Emerging Directions and Best Practices

Current developments include distributed optimization for edge and federated systems, differentiable optimization embedded in learning pipelines, online optimization for rapidly changing environments, and hybrid methods combining machine learning with mathematical programming. Digital twins can connect optimization models to near-real-time operational data. Quantum and specialized hardware remain research directions for selected combinatorial problems, but their practical suitability must be evaluated rather than assumed.

Effective practice follows several principles:

• formulate the decision and constraints before choosing the solver;
• use clear units, realistic bounds, and documented assumptions;
• exploit convexity and problem structure whenever possible;
• compare exact methods with transparent heuristics when scale requires it;
• test feasibility, sensitivity, scenarios, and out-of-sample performance;
• report gaps, uncertainty, and solver status honestly;
• involve domain experts and affected stakeholders;
• monitor the deployed decision process and revisit the model as conditions change.

Chapter Summary

Optimization formulates decisions as the selection of feasible values for decision variables that maximize or minimize an objective. Linear programming is effective when relationships are additive; integer and mixed-integer programming represent discrete choices; nonlinear programming captures curved relationships; and convexity provides strong guarantees about global optimality. Gradients, Hessians, KKT conditions, Lagrangians, and duality support analysis of constrained problems. Shadow prices and sensitivity analysis explain the value of scarce resources and the effect of parameter changes.

Multi-objective optimization represents competing goals through Pareto efficiency, weighted scalarization, or epsilon-constraint methods. Uncertainty requires scenario analysis, stochastic models, or robust optimization. Practical success depends on sound formulation, validation, computational awareness, stakeholder participation, and governance. In computing and management, optimization is most valuable as a transparent decision-support discipline that connects data, mathematical structure, operational constraints, and responsible action.

Key Terms

Decision variable: A controllable quantity whose value is selected by the optimization model.

Objective function: A mathematical measure to be maximized or minimized.

Constraint: A condition restricting permissible decisions.

Feasible solution: A decision satisfying every model constraint.

Feasible region: The set of all feasible decisions.

Linear programming: Optimization with linear objective and constraint functions.

Integer programming: Optimization in which specified variables must take integer values.

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

Binary variable: An integer variable restricted to zero or one.

LP relaxation: An integer model with integrality restrictions temporarily removed.

Convex function: A function whose value at a weighted average does not exceed the corresponding weighted average of its values.

Gradient: A vector of first derivatives indicating local direction of greatest increase.

Hessian: A matrix of second derivatives used to study curvature.

Lagrangian: A function combining an objective with weighted constraint functions.

KKT conditions: Necessary, and under suitable assumptions sufficient, conditions for constrained optimality.

Duality: The relationship between a primal optimization problem and a related problem based on its constraints.

Shadow price: The marginal value of relaxing a constraint within a valid sensitivity range.

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

Robust optimization: Optimization seeking acceptable performance across an uncertainty set.

Sensitivity analysis: Study of how solutions or objective values respond to parameter changes.

Review Questions

Short Answer Questions

1. What are the three essential components of a basic optimization model?

2. Why are binary variables useful in facility-location or project-selection problems?

3. State the practical meaning of a shadow price.

4. What distinguishes a convex minimization problem from a general nonlinear problem?

5. Define Pareto efficiency.

Long Answer Questions

1. Explain the formulation, geometry, and computational approaches of linear programming.

2. Discuss mixed-integer programming, LP relaxation, branch-and-bound, and the role of big-M constraints.

3. Explain the Lagrangian and KKT conditions, including complementary slackness.

4. Compare scenario analysis, stochastic programming, and robust optimization.

5. Describe a complete optimization modelling workflow for a large computing infrastructure decision.

Analytical / Application Questions

1. Formulate a mixed-integer model for selecting cloud zones and assigning workloads when fixed activation costs, capacity limits, and unmet-demand penalties are present.

2. A manager must balance cost, energy consumption, and availability. Explain how Pareto analysis and the epsilon-constraint method could support the decision.

3. An optimization model recommends a low-cost staffing plan, but the result changes greatly when demand forecasts are slightly altered. Diagnose possible causes and propose sensitivity, validation, and governance actions.

22. Multiple Choice Questions with Answers

Question 1

Which feature most directly distinguishes a mixed-integer linear program from a standard linear program?

A. It has no constraints.

B. At least one decision variable is required to take an integer value.

C. Its objective must be nonlinear.

D. It can only contain binary variables.

Correct Answer: B. At least one decision variable is required to take an integer value.

Question 2

In a minimization problem with a constraint g(x) ≤ 0, what is the usual sign restriction on its KKT multiplier?

A. It must be nonnegative.

B. It must be nonpositive.

C. It must equal zero always.

D. It can take only integer values.

Correct Answer: A. It must be nonnegative.

Question 3

What does a positive shadow price for a binding capacity constraint generally indicate?

A. Increasing the capacity may improve the objective value.

B. The constraint can be deleted without effect.

C. The current solution is necessarily infeasible.

D. The capacity has no economic value.

Correct Answer: A. Increasing the capacity may improve the objective value.

Question 4

Why is convexity especially valuable in minimization?

A. It guarantees that every feasible point is optimal.

B. It guarantees that every local minimum is global under the usual convex assumptions.

C. It eliminates the need for constraints.

D. It makes all variables integer automatically.

Correct Answer: B. It guarantees that every local minimum is global under the usual convex assumptions.

Question 5

A company wants to minimize cost while ensuring that energy use does not exceed a specified limit. Which modelling approach directly represents this preference?

A. Optimize cost subject to an energy constraint.

B. Remove energy from the model.

C. Use only an unconstrained gradient method.

D. Replace all variables with binary variables.

Correct Answer: A. Optimize cost subject to an energy constraint.

Question 6

Which statement about an LP relaxation of an integer program is correct?

A. It always produces an implementable integer decision.

B. It removes integrality restrictions and can provide a bound for the integer problem.

C. It necessarily has a worse objective value than every integer solution in both optimization directions.

D. It eliminates all computational difficulty.

Correct Answer: B. It removes integrality restrictions and can provide a bound for the integer problem.

Question 7

A solution is Pareto efficient when:

A. It optimizes every objective independently at the same time.

B. No objective can be improved without worsening at least one other objective.

C. All objective weights are equal.

D. All constraints are inactive.

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

Question 8

Which situation most strongly supports using robust optimization?

A. All parameters are known exactly and permanently.

B. The decision must remain acceptable across a specified range of uncertain parameters.

C. There is no objective function.

D. Only unconstrained quadratic functions are permitted.

Correct Answer: B. The decision must remain acceptable across a specified range of uncertain parameters.

Question 9

In the cloud-capacity case, why might a nominally cheapest plan be rejected?

A. It may lack reserve capacity and fail under high demand or zone failure.

B. Fixed costs are never relevant.

C. MILP models cannot represent capacity.

D. A higher-cost plan is always mathematically optimal.

Correct Answer: A. It may lack reserve capacity and fail under high demand or zone failure.

Question 10

Which is a modelling error rather than an optimization method?

A. Using branch-and-bound for discrete decisions.

B. Applying projected gradient descent to a constrained smooth problem.

C. Omitting a legally required service constraint from the model.

D. Examining sensitivity to demand changes.

Correct Answer: C. Omitting a legally required service constraint from the model.