Optimization Problems in Systems Engineering Study Guide

Optimization Problems in Systems Engineering Overview

• Key Problem Areas in Systems Engineering:     * Equipment Replacement: Determining the optimal timing for replacing aging machinery to balance purchase costs and maintenance expenses.     * Decision Making for Batch Processing: Identifying optimal production quantities and schedules for batch plants.     * Minimizing Manufacturing Costs: Formulating problems that involve both variable production costs and fixed capital/equipment costs.     * 'Big M' Constraints: A specific mathematical technique used to handle logical constraints and discontinuities in optimization models.

Scheduling, Planning, and Enterprise-Wide Optimization

• Internal Categories of Process System Engineering:     * Batch Planning: Solving the fundamental questions of what products to manufacture, in what quantities, and at what specific times.     * Logistics: Determining the quantities of materials to ship and their specific destinations within a supply chain.     * Business Planning: High-level strategic decisions concerning plant locations and the total number of facilities to construct.

• Operations Research (OR): This is the standard business terminology for the optimization of supply chains.

• Enterprise-Wide Optimization (EWO): A broader approach occurring when multiple objectives are integrated into the optimization process. Key considerations include:     * Minimizing the overall carbon footprint of the enterprise.     * Capitalizing on business opportunities to expand the existing product portfolio.     * Achieving and leveraging economies of scale.

Case Study: Equipment Replacement for Vaccine Production

• Scenario Context:     * The problem involves operating a vaccine production facility where equipment quality deteriorates as it ages.     * Initial Condition: The facility starts with entirely new equipment in Year 1.     * Planning Horizon: The analysis covers a 5-year period.     * Goal: Determine how frequently each unit should be replaced to minimize costs.

• Data Characteristics:     * Purchase prices for new equipment are not static; they increase over time.     * Maintenance costs increase significantly as the equipment gets older.

Network and Mathematical Formulation of Equipment Replacement

• Network (Graph) Representation:     * Vertices: Each vertex (node) represents the beginning of a specific year. The nodes are labeled $1, 2, 3, 4, 5, 6$.     * Edges: Directed edges connect a starting year node to a future year node.     * Edge Significance: Each edge represents a specific strategy of purchasing a new unit at the beginning of year $i$ and replacing it at the end of year $j-1$ (beginning of year $j$).     * Edge Weights: The weight assigned to an edge is the total cost of that strategy, which is the sum of the purchase cost and all maintenance costs incurred between year $i$ and year $j$.

• The Optimization Goal: Finding the shortest path from node $1$ to node $6$ represents the minimum cost replacement strategy.

• Algebraic Representation (Cost Matrix):     * All cost values are stored in a cost matrix, denoted as $C_{ij}$.     * Specific Matrix Values Provided:         * $84.1, 53.7, 35.5, 25.8, 20.8$         * $22.8, 24.8, 28.8, 33.8$         * $33.8, 55.7, 37.5$         * $27.8, 39.5$         * $29.8$

• Optimization Variables:     * Let $x_{ij}$ be a binary decision variable.     * $x_{ij} = 1$ if the edge between year $i$ and year $j$ is selected (the strategy is followed).     * $x_{ij} = 0$ otherwise.

• Problem Type: This is classified as a Mixed-Integer Linear Program (MILP).     * Small-scale cases can be solved using the Excel solver to find a global optimum.     * Large-scale industrial cases require specialized optimization software.

Production Sizing and Batch Processes

• Benefits of Batch Processing Facilities:     * The ability to produce multiple products derived from similar feedstocks.     * Rapid responsiveness to changing market demands.     * Operational flexibility to maintain production if a specific supply line or production line is interrupted.     * Increased overall profit margins compared to single-product plants.

• Production Planning Case Study Details:     * Product 1 (P1): Production limit of $8000\,lb/day$; Profit of $\$0.16/lb$.     * Product 2 (P2): Production limit of $10,000\,lb/day$; Profit of $\$0.20/lb$.     * Supply Limits:         * Raw Material B: Limited to $6000\,lb/day$.         * Raw Materials A and C: No supply limits provided.     * Batch Size Constraints: Due to the high costs associated with shutting down and starting up, batch sizes are constrained to exactly $2000\,lb$ increments for both $P1$ and $P2$.

Mathematical Formulation for Batch Sizing (MILP)

• Problem Scaling:     * Let $x_1$ be the number of $1000\,lb/day$ runs of $P1$.     * Let $x_2$ be the number of $1000\,lb/day$ runs of $P2$.     * Profit is scaled to units of $\$1000/day$.

• Objective Function and Basic Constraints:     * The primary objective is to maximize profit.     * Constraints include the resource limit on Material $B$.

• Batch Size Logic:     * To ensure production runs meet the $2000\,lb$ batch requirement, the number of runs ($x_i$) must be an even integer.     * Introduction of Integer Variables: New variables $y_i$ are used such that:         * $x_i = 2y_i$     * This forces the production runs to occur in multiples of $2$, satisfying the mandatory batch sizing.

• Solution Methods:     * Complete Enumeration: In this specific small case, there are only $30$ possibilities, which can be checked individually.     * Excel LP Solver: Uses the Branch and Bound algorithm.     * Specialty Software: High-tech tools like GAMS/CPLEX are used for complex versions of these problems.

Minimizing Manufacturing Costs with Fixed Charges

• Problem Variables:     * $j = 1, \dots, n$ represents the indices for different products.     * $C_j$ is the variable cost to produce one unit of product $j$.     * $K_j$ is a fixed equipment/setup cost incurred if any amount of product $j$ is produced.     * $d_j$ represents the consumer demand for product $j$ that must be satisfied.

• Discontinuous Formulation:     * Continuous variables $x_j$ represent the actual production amount.     * Binary variables $y_j$ track whether a product line is active.     * This results in a discontinuous cost function that is mathematically difficult to solve directly.

The Big-M Constraint Method

• Definition and Purpose: To create a linear and continuous relationship between a continuous variable ($x_j$) and its associated binary decision variable ($y_j$).

• The Formulation:     * The constraint is written as:         * $x_j \leq M_j \times y_j$     * Functionality:         * If $x_j \neq 0$, the inequality forces $y_j$ to equal $1$, thereby triggering the fixed cost ($K_j$) in the objective function.         * If $x_j = 0$, the optimization algorithm will naturally force $y_j$ to $0$ to minimize the objective function (since $y_j = 0$ avoids the fixed cost $K_j$).

• Optimization Efficiency:     * To improve the speed of the solver, variables for $M$ should be kept as small as possible.     * Small $M$ values decrease the size of the "feasible region" for the simplifications and relaxations that algorithms use as intermediate steps.     * These constraints are desirable because they are linear, making them compatible with standard MILP solvers.

Optimization in systems engineering

This lecture covers three classic MILP (mixed-integer linear program) problem types that appear throughout process systems engineering, business planning, and operations research.

Example 1

Equipment replacement

Vaccine facility. 5-year horizon. Shortest-path network → cost matrix → MILP. Binary xij variables.

Example 2

Batch production sizing

Two products, constrained supply of B, 2000 lb batch sizes. Integer yi variables enforce batch constraints.

Example 3

Minimizing manufacturing costs

Fixed equipment costs when any product is made. Big-M constraint links binary yj to continuous xj linearly.

Key concept

Solution strategies

Complete enumeration vs. Excel branch & bound vs. GAMS/CPLEX. Know when each applies.

Why MILPs?

Pure LP can't handle "on/off" decisions (is equipment purchased? is a product made at all?). Integer or binary variables capture these discrete choices while the rest of the model stays linear — giving solvers a tractable structure.

Operations research connection

In business, this family of problems is called Operations Research. When multiple objectives are combined (carbon footprint, profit, portfolio), it becomes Enterprise-Wide Optimization — an active research area.

Equipment replacement — problem setup

You operate a vaccine production facility. Equipment deteriorates with age. Given a 5-year planning horizon (starting with all-new equipment in year 1), when do you replace each unit?

What makes this tricky

Equipment purchase prices rise with time (inflation).

Maintenance costs also rise with equipment age.

Replacing early costs more upfront; replacing late costs more in maintenance. There's an optimal crossover point — but it's not obvious.

Key data (from lecture)

Purchase price (rises over years)

Year 1: $20k → Year 2: $22k → Year 3: $25k → Year 4: $27k → Year 5: $30k

Maintenance cost (rises with age of equipment)

Age 1yr: $5k → Age 2yr: $8k → Age 3yr: $12k → Age 4yr: $18k

Network insight

Model each year as a node (1–6, where 6 = end of year 5). An edge from node i to node j means "buy new equipment at the start of year i, replace it at the start of year j." The weight on that edge = total cost (purchase + maintenance) for that strategy. Finding the cheapest total plan = shortest path from node 1 to node 6.

Network, cost matrix & binary variables

The 6-node network (one node per year boundary) has edges connecting every pair i → j where i < j. Each edge weight Cij = purchase cost at year i + cumulative maintenance through year j−1.

Weighted network — selected edge costs shown (full matrix below):

1

84.1

2

53.7

3

35.5

4

25.8

5

20.8

6

Top path shown — direct edges (1→2, 2→3, etc.) represent replacing every year. Diagonal edges (e.g. 1→3) represent keeping equipment for 2 years.

Cost matrix Cij

i \ j 2 3 4 5 6

1 20.8 28.8 33.8 39.5 84.1

2 — 22.8 24.8 33.8 53.7

3 — — 25.8 27.8 35.5

4 — — — 22.8 29.8

5 — — — — 20.8

Reading the matrix

C14 = 33.8 means: buy new at year 1, replace at year 4 (use for 3 years), total cost $33.8k. Highlighted cells suggest one possible optimal path: 1→4→6 (buy at yr 1, replace at yr 4, done at yr 6). Verify by summing: 39.5 + 29.8 = 69.3 — or try other paths!

Decision variable

xij = 1 if edge i→j is followed (equipment bought at year i, replaced at year j), 0 otherwise

Equipment replacement — MILP formulation

Objective — minimize total cost

min Σi Σj>i Cij · xij

Flow conservation at each intermediate node k (2–5)

Σi<k xik = Σj>k xkj ∀ k = 2,3,4,5

Must start at node 1 and end at node 6

Σj x1j = 1 Σi xi6 = 1

Binary constraint

xij ∈ {0, 1}

Problem type

This is a mixed-integer linear program (MILP). For this small size (15 possible edges), Excel Solver finds the global optimum. For larger industrial instances, dedicated solvers like CPLEX or GAMS are needed.

Exam tip — the flow conservation constraint

At every intermediate node, the number of edges entering must equal the number leaving. This is the classic network flow constraint — make sure you can write it for a general node k.

Batch production sizing — problem setup

A plant makes two products (P1, P2) from shared feedstocks. You want to maximize profit subject to production, supply, and batch-size constraints.

Given data

Production limits

P1: max 8,000 lb/day P2: max 10,000 lb/day

Supply constraint

Feedstock B: max 6,000 lb/day (A and C: unlimited)

Profits

P1: $0.16/lb P2: $0.20/lb

Batch size constraint

Production must be in multiples of 2,000 lb for both P1 and P2

Scaling (to avoid numerical issues)

x₁ = number of 1,000 lb/day runs of P1 x₂ = number of 1,000 lb/day runs of P2 profit in $1,000/day

Why scale?Mixing very large numbers (lb/day) with small coefficients ($/lb) causes numerical precision problems in solvers. Scaling to similar magnitudes improves reliability.

Objective function (scaled)

max 0.16 x₁ + 0.20 x₂

Constraint on feedstock B

(based on stoichiometry from the reaction scheme)

[B consumed by P1] · x₁ + [B consumed by P2] · x₂ ≤ 6

Batch constraint & complete MILP

The tricky part: production must be in multiples of 2,000 lb/day — meaning x_i (in units of 1,000 lb/day) must be an even integer. How do you enforce this?

Introducing integer variables y_i

Define new integer variables

x₁ = 2 y₁ x₂ = 2 y₂ where y_i ∈ ℤ⁺ (positive integers)

By writing x as 2y, you guarantee x is always an even multiple of 1,000 = a multiple of 2,000 lb. The y variables absorb the integrality requirement.

Complete MILP

Objective

max 0.32 y₁ + 0.40 y₂

Supply B constraint

[coeff] y₁ + [coeff] y₂ ≤ 3

Production limits

y₁ ≤ 4 y₂ ≤ 5

Integrality

y₁, y₂ ∈ ℤ⁺

Key insight — substitution trickIntroducing y = x/2 converts a "must be even integer" constraint into a simple "must be positive integer" constraint. This technique — inventing auxiliary integer variables to enforce discreteness — is a general MILP modeling skill.

Exam tipYou may be asked to formulate (not solve) a batch-constrained production problem. Know how to: (1) define scaled variables, (2) write the objective, (3) write resource constraints, and (4) enforce batch size via integer substitution variables.

Big-M constraints — manufacturing cost minimization

Problem: produce n products at minimum cost. If you make any of product j, you must pay a fixed equipment cost K_j (discontinuous — either $0 or K_j). How do you model this?

Variables

x_j = continuous amount of product j produced y_j = binary: 1 if any of product j is made, 0 otherwise

The problem with a naive formulation

Discontinuous constraint (hard for solvers)

If x_j > 0 → y_j = 1 (incur fixed cost K_j)
If x_j = 0 → y_j = 0 (no fixed cost)

This can't be directly fed to an LP/MILP solver because it's a conditional — not a linear constraint. Big-M is the fix.

The Big-M constraint

Replace the conditional with this linear constraint

x_j ≤ M · y_j ∀ j

What is M?M must be at least as large as the maximum possible value of x_j — typically the demand d_j. Using M = d_j is ideal: it's "as small as possible" while still being valid.

Why make M as small as possible?Tighter M values shrink the LP relaxation's feasible region (the region explored during branch-and-bound). A smaller feasible region → fewer nodes to explore → faster solution. Using M = ∞ is technically valid but makes the solver very slow.

Objective (minimize total cost)

min Σ_j C_j x_j + Σ_j K_j y_j

Demand satisfaction

x_j ≥ d_j · y_j ∀ j

Solving MILPs — three approaches

Complete enumeration

Try every combination. For the equipment replacement example: 30 possible paths. Feasible for tiny problems. Impractical as n grows (exponential scaling).

Excel Solver (branch & bound)

Medium tech. Solves LP relaxation, branches on fractional integer variables, prunes infeasible branches. Good for classroom-scale MILPs.

GAMS / CPLEX

Industrial-grade. Handles thousands of variables and constraints. Used for real supply chain, scheduling, and plant-wide optimization.

Branch and bound — how it works

1

Solve LP relaxation

Ignore integrality — solve as a continuous LP. Get an upper bound on the objective (for maximization).

2

Branch on a fractional variable

Pick an integer variable with a fractional solution value (e.g., y₁ = 2.7). Create two subproblems: one with y₁ ≤ 2, one with y₁ ≥ 3.

3

Prune infeasible or dominated branches

If a branch's LP relaxation is worse than the best integer solution found so far, discard it. This is where tight Big-M bounds help — they cut off more branches early.

4

Repeat until all branches resolved

The best integer-feasible solution found is the global optimum (for MILP, branch-and-bound guarantees optimality).

Enterprise-Wide OptimizationWhen these MILP tools are applied to multi-plant supply chains with multiple objectives (cost, carbon footprint, resilience), the field is called Enterprise-Wide Optimization — an active research and industrial area built on exactly these foundations.