1. Modeling Methodology: From Problem to Solution
Learning Objectives
- Understand the systematic process of problem formulation
- Learn to translate real-world problems into mathematical models
- Master the key components of optimization models
- Apply best practices in model development and validation
The Optimization Modeling Process
Mathematical optimization modeling is a systematic approach to solving real-world problems. The process involves transforming a practical business or engineering challenge into a mathematical formulation that can be solved using optimization algorithms. This section outlines the fundamental steps in this process, which form the foundation for successfully solving complex problems.
Phase 1: Problem Definition and Analysis
The first phase is critical as it establishes the foundation for the entire modeling effort. During this phase, we must clearly identify the business or operational problem, understand the organizational context, and define the scope of the solution. This involves conducting interviews with stakeholders, reviewing existing processes, and documenting current challenges.
Key Activities in Problem Definition:
- Stakeholder Interviews: Meet with decision-makers, operations managers, and end-users to understand their perspective on the problem
- Context Analysis: Examine the organizational, market, and regulatory context that influences the problem
- Scope Definition: Clearly delineate what is included and excluded from the solution
- Objective Identification: Determine what the organization wants to achieve (minimize cost, maximize profit, improve service, etc.)
- Constraint Recognition: Identify physical, operational, and business constraints
Phase 2: Data Collection and Preparation
Once the problem is well-understood, the next step is to gather relevant data. This includes collecting historical data, obtaining parameter estimates, and preparing the information for use in the mathematical model. Data quality is paramount as it directly affects the reliability of the solution.
Data Requirements:
- Historical Data: Past performance metrics, costs, demand patterns, and resource utilization
- Parameter Estimation: Coefficients for objective functions and constraints (e.g., unit costs, processing times)
- System Specifications: Capacity limits, availability windows, resource quantities
- External Factors: Market prices, customer demand forecasts, regulatory requirements
- Data Validation: Verification and quality checks to ensure data accuracy
Phase 3: Mathematical Model Formulation
The model formulation phase translates the problem into a mathematical framework. This involves identifying decision variables, defining the objective function, and specifying constraints. The mathematical model should be a simplified representation of reality that captures the essential features of the problem.
Key Components of an Optimization Model:
1. Decision Variables
Decision variables represent the choices available to the decision-maker. They are the unknowns that the optimization algorithm will determine values for. Examples include:
- Production quantities of different products
- Shipment quantities between locations
- Resource allocation percentages
- Binary decisions (yes/no, implement/don't implement)
yk = 1 if facility k is opened, 0 otherwise
pi = production quantity for product i
2. Objective Function
The objective function defines what we are trying to optimize. It is a mathematical expression that combines decision variables with their respective coefficients (costs, revenues, profits, etc.). The objective can be to minimize (costs, time, waste) or maximize (profit, revenue, efficiency).
OR
Maximize: Z = Σi pi × qi - Σk fk × yk
3. Constraints
Constraints represent the limitations and requirements that the solution must satisfy. They ensure that the solution is feasible and realistic. Types of constraints include capacity constraints, demand constraints, resource constraints, and logical constraints.
Demand Constraint: Σi xij = Dj ∀j
Non-negativity: xij ≥ 0
Phase 4: Model Validation and Refinement
Before solving the model, it is crucial to validate its structure and ensure it accurately represents the problem. This involves checking for logical consistency, testing with known solutions, and refining the model based on stakeholder feedback.
Validation Techniques:
- Dimensional Analysis: Verify that all terms in equations have consistent units
- Sensitivity Analysis Preview: Test how the model behaves with extreme parameter values
- Scenario Testing: Validate the model using historical scenarios with known outcomes
- Expert Review: Have domain experts review the model structure and parameters
- Feasibility Check: Ensure at least one feasible solution exists (check for infeasibility)
Phase 5: Solution and Optimization
Once the model is formulated and validated, it is ready to be solved using appropriate optimization algorithms. The choice of algorithm depends on the model type (linear, integer, convex, etc.) and the problem size. This phase is covered in detail in subsequent sections of this course.
Phase 6: Results Analysis and Implementation
The final phase involves analyzing the optimization results, conducting sensitivity analysis to understand solution robustness, and implementing the recommended solution in the real-world system. This phase is critical for ensuring that the optimization effort delivers business value.
2. Real-World Case Studies and Applications
Learning Objectives
- Understand how optimization is applied in real industrial and commercial settings
- Learn to formulate problems based on industry-specific requirements
- Analyze the business impact of optimization solutions
- Develop case study analysis skills
Case Study 1: Production Planning and Scheduling
Harris Corporation: Electronics Manufacturing Optimization
Problem Context: Harris Corporation manufactures semiconductor components for various industries. The company faced significant challenges in production planning due to demand variability, limited production capacity, and inventory carrying costs. Multiple production lines produced similar products, each with different efficiency characteristics.
Problem Formulation:
Decision Variables:
- xij = units of product i produced in period j
- sij = inventory of product i at end of period j
- yij = 1 if production line for product i is active in period j, 0 otherwise
Objective Function:
where ci is production cost, hi is holding cost, and fi is setup cost
Key Constraints:
- Demand satisfaction: si,j-1 + xij - sij = Dij
- Capacity: xij ≤ M·yij (big-M constraint)
- Minimum production: xij ≥ L·yij
- Production line availability: Σi yij ≤ Available lines in period j
Results:
| Metric | Before Optimization | After Optimization | Improvement |
|---|---|---|---|
| Total Annual Cost | $2.8M | $2.1M | 25% reduction |
| Average Inventory Level | $450K | $280K | 38% reduction |
| On-Time Delivery Rate | 92% | 98% | +6% |
| Production Line Utilization | 68% | 82% | +14% |
Key Insights:
- The optimal solution balanced production setup costs against inventory holding costs
- Strategic anticipation of demand peaks allowed better resource utilization
- Improved customer service was achieved through better demand matching
- Implementation took 6 months and included staff training on the new planning system
Case Study 2: Transportation and Distribution Network Optimization
Logistics Company: Route Optimization and Network Design
Problem Context: A major logistics company operated a distribution network with 15 warehouses and served over 5,000 customers across multiple regions. The company sought to optimize warehouse locations, transportation routes, and delivery schedules to minimize total logistics costs while meeting service level agreements.
Problem Formulation:
Decision Variables:
- yk = 1 if warehouse k is operated, 0 otherwise
- xijk = units shipped from warehouse k to customer i via route j
- rij = 1 if customer i is served by route j, 0 otherwise
Objective Function:
Results:
| Metric | Baseline | Optimized | Impact |
|---|---|---|---|
| Number of Warehouses | 15 | 10 | 33% reduction |
| Total Transportation Cost | $12.5M/year | $8.2M/year | 34% savings |
| Average Delivery Time | 3.2 days | 2.5 days | 22% faster |
| Vehicle Utilization | 61% | 78% | +17% |
Case Study 3: Blending and Mixture Problems in Refining
Petroleum Refinery: Crude Oil Blending Optimization
Problem Context: A petroleum refinery processes various crude oil types into finished products (gasoline, diesel, jet fuel) with specific quality requirements. The refinery must blend different crude oils to meet product specifications while minimizing raw material costs.
Problem Formulation:
Decision Variables:
- xij = barrels of crude i allocated to product j
- qj = quality parameter for product j
Objective Function:
where pi is crude price and rj is product revenue
Key Constraints:
- Supply: Σj xij ≤ Available crude i
- Demand: Σi xij = Demand for product j
- Quality specs: Qmin,j ≤ Σi (xij·qualityi)/Σi xij ≤ Qmax,j
Results:
- Reduced raw material costs by 8-12% while meeting all quality specifications
- Improved profit margin by optimizing product mix based on market prices
- Enabled faster response to market price changes
- Reduced manual blending adjustments by 95%
Case Study 4: Resource Allocation in Healthcare
Hospital Network: Operating Room Scheduling and Staff Allocation
Problem Context: A hospital network with multiple locations needed to optimize operating room (OR) utilization and surgical staff scheduling to reduce wait times while maintaining work-life balance and minimizing overtime costs.
Key Results:
- Reduced average surgical wait time from 14 days to 5 days
- Decreased OR idle time from 28% to 12%
- Reduced overtime costs by 35%
- Improved staff satisfaction scores by 40%
Key Lessons from Case Studies
- Data Quality is Crucial: Accurate and complete data is essential for obtaining realistic results
- Model Simplification: A simpler model that captures key trade-offs is often more useful than a complex model
- Stakeholder Engagement: Involving stakeholders throughout the process ensures buy-in and successful implementation
- Sensitivity Analysis: Understanding how solutions change with parameter variations provides confidence in recommendations
- Change Management: Technical optimization is only part of the solution; change management is critical for implementation success
3. Optimization Modeling and Solution Software
Learning Objectives
- Understand the capabilities and limitations of major optimization software
- Learn the syntax and structure of modeling languages (AMPL, GAMS)
- Develop practical skills in using optimization tools
- Compare different software platforms for problem selection
Overview of Optimization Software
Modern optimization problems require specialized software that can handle complex mathematical formulations and large-scale problems. The landscape of optimization software includes modeling languages, integrated development environments, and solver engines. This section provides an overview of the most widely-used tools in industry and academia.
1. Algebraic Modeling Languages
AMPL (A Mathematical Programming Language)
Overview: AMPL is a powerful algebraic modeling language designed for mathematical programming problems. It allows users to write optimization problems in an intuitive, mathematical notation that closely resembles standard mathematical formulation.
Key Features:
- Separation of model and data files for flexibility
- Support for linear, nonlinear, and integer programs
- Extensive library of solvers (CPLEX, Gurobi, MINOS, etc.)
- Interactive environment with debugging capabilities
- Large-scale problem support (thousands of variables and constraints)
Example: AMPL Formulation of Transportation Problem
set WAREHOUSES;
set CUSTOMERS;
param supply{WAREHOUSES};
param demand{CUSTOMERS};
param cost{WAREHOUSES, CUSTOMERS};
var Ship{WAREHOUSES, CUSTOMERS} >= 0;
minimize Total_Cost: sum{i in WAREHOUSES, j in CUSTOMERS} cost[i,j] * Ship[i,j];
subject to Supply_Constraint{i in WAREHOUSES}:
sum{j in CUSTOMERS} Ship[i,j] <= supply[i];
subject to Demand_Constraint{j in CUSTOMERS}:
sum{i in WAREHOUSES} Ship[i,j] = demand[j];
Advantages: Clean syntax, powerful solver integration, excellent for large-scale problems, good debugging support
Disadvantages: Commercial license required, steeper learning curve, requires separate solver software
GAMS (General Algebraic Modeling System)
Overview: GAMS is another prominent algebraic modeling language widely used in industry and academia for solving optimization problems.
Key Features:
- Intuitive syntax similar to mathematical notation
- Support for LP, NLP, MIP, MINLP problems
- Access to multiple solvers (CPLEX, BARON, CONOPT, etc.)
- Extensive documentation and user base
- Good for modeling economic and engineering problems
Example: GAMS Formulation of Transportation Problem
I warehouses / W1, W2, W3 /
J customers / C1, C2, C3, C4 /;
PARAMETERS
a(I) supply at warehouse i
/ W1 100, W2 150, W3 120 /
b(J) demand at customer j
/ C1 80, C2 70, C3 50, C4 90 /;
TABLE d(I,J) distance in km
C1 C2 C3 C4
W1 2 3 1 4
W2 6 1 8 3
W3 3 5 2 5;
VARIABLES
x(I,J) shipment quantities
z total cost;
POSITIVE VARIABLE x;
EQUATIONS
cost_definition, supply_constraint(I), demand_constraint(J);
cost_definition.. z =e= SUM((I,J), d(I,J)*x(I,J));
supply_constraint(I).. SUM(J, x(I,J)) =l= a(I);
demand_constraint(J).. SUM(I, x(I,J)) =e= b(J);
MODEL transport /all/;
SOLVE transport USING LP MINIMIZING z;
Advantages: Intuitive syntax, supports various problem types, good solver integration, strong academic community
Disadvantages: Commercial license, steeper initial learning curve, different from standard programming languages
2. General-Purpose Programming Languages with Optimization Libraries
Python with Optimization Libraries
Overview: Python has emerged as a popular platform for optimization due to its ease of use and powerful ecosystem of scientific libraries. Several excellent optimization packages are available for Python.
Popular Python Optimization Libraries:
- PuLP: Lightweight modeling language for LP and integer programming
- Pyomo: Powerful algebraic modeling language similar to AMPL/GAMS
- Gurobi Python API: Direct interface to the Gurobi solver
- CVXPY: Disciplined convex programming framework
- SciPy.optimize: General-purpose optimization routines
Example: Python with PuLP for Transportation Problem
# Create the model
model = LpProblem("Transportation", LpMinimize)
# Define data
warehouses = ['W1', 'W2', 'W3']
customers = ['C1', 'C2', 'C3', 'C4']
supply = {'W1': 100, 'W2': 150, 'W3': 120}
demand = {'C1': 80, 'C2': 70, 'C3': 50, 'C4': 90}
# Cost data
costs = {
('W1', 'C1'): 2, ('W1', 'C2'): 3, ('W1', 'C3'): 1, ('W1', 'C4'): 4,
('W2', 'C1'): 6, ('W2', 'C2'): 1, ('W2', 'C3'): 8, ('W2', 'C4'): 3,
('W3', 'C1'): 3, ('W3', 'C2'): 5, ('W3', 'C3'): 2, ('W3', 'C4'): 5
}
# Decision variables
routes = [(w, c) for w in warehouses for c in customers]
vars_ship = LpVariable.dicts("Route", routes, lowBound=0, cat='Continuous')
# Objective function
model += lpSum([vars_ship[(w,c)]*costs[(w,c)] for (w,c) in routes])
# Supply constraints
for w in warehouses:
model += lpSum([vars_ship[(w,c)] for c in customers]) <= supply[w]
# Demand constraints
for c in customers:
model += lpSum([vars_ship[(w,c)] for w in warehouses]) == demand[c]
# Solve
model.solve()
print("Optimal Cost: ", value(model.objective))
Advantages: Free and open-source, easy to learn, integration with other tools, fast prototyping
Disadvantages: Generally slower than commercial solvers, may require external solver libraries, less mature than AMPL/GAMS
MATLAB for Optimization
Overview: MATLAB provides the Optimization Toolbox with functions for linear programming, integer programming, and nonlinear optimization. MATLAB is particularly strong for problems involving visualization and numerical computation.
Key Features:
- Integrated environment for modeling and solving
- Strong visualization and plotting capabilities
- Built-in solvers for various problem types
- Support for large-scale problems
- Excellent for prototyping and research
Advantages: Integrated environment, strong visualization, good for research, extensive documentation
Disadvantages: Expensive commercial license, slower than specialized solvers, less suited for very large-scale industrial problems
3. Commercial Solvers
While modeling languages allow users to formulate problems, the actual solution requires solver engines. The following are industry-leading solvers:
CPLEX (IBM)
- Industry standard for LP/MIP
- Extremely fast for large-scale problems
- Robust and reliable
- Works with AMPL, GAMS, OPL
- High cost for commercial use
Gurobi Optimizer
- State-of-the-art LP/MIP solver
- Superior performance on many problems
- Excellent Python integration
- Good for academic research
- Growing industry adoption
XPRESS (FICO)
- Professional-grade LP/MIP solver
- Fast convergence
- Good parallelization
- Integrates with Mosel language
- Commercial licensing
Open-Source Solvers
- COIN-OR LP/MIP
- SCIP for integer programming
- Ipopt for nonlinear programming
- Free to use
- Generally slower than commercial
Software Selection Guide
| Selection Criteria | Best Choice | Alternative |
|---|---|---|
| Large-scale LP/MIP problems | CPLEX or Gurobi with AMPL | XPRESS |
| Academic research | Python + Gurobi (academic license) | AMPL with open-source solvers |
| Engineering applications | MATLAB Optimization Toolbox | Python + NumPy/SciPy |
| Quick prototyping | Python with PuLP | Spreadsheet with Solver |
| Nonlinear optimization | Pyomo with IPOPT | GAMS with CONOPT |
| Budget-conscious | Python + COIN-OR | LibreOffice Calc with Solver |
4. Practical Implementation Guide
Learning Objectives
- Understand the complete workflow for solving optimization problems
- Learn best practices for implementation and deployment
- Develop skills in model building and testing
- Master documentation and maintenance procedures
Step 1: Problem Definition and Scoping
Key Activities:
- Meet with business stakeholders to understand objectives
- Identify key decision-makers and influencers
- Clarify success metrics and constraints
- Estimate problem size and complexity
- Establish project timeline and resource requirements
Deliverable: Project charter with problem statement, objectives, scope, timeline, and resource plan
Step 2: Data Collection and Preparation
Key Activities:
- Identify data sources (ERP systems, databases, spreadsheets, etc.)
- Extract and compile historical data
- Perform data quality assessment
- Fill gaps with expert estimates or statistical methods
- Document all data transformations
- Create data dictionary with definitions and units
- All required data fields are present
- Values are within expected ranges
- No significant missing values (< 5% for key fields)
- Data is internally consistent and validated
- Units are clearly documented
- Data sources are documented
- Outliers are investigated and justified
Step 3: Model Development
Iterative Approach:
- Model Skeleton: Create a basic model with core elements (decision variables, objective, main constraints)
- Expand Model: Add secondary constraints and refinements
- Test Feasibility: Verify the model has at least one feasible solution
- Validate Logic: Check that the model correctly represents the problem
- Test with Data: Run with sample/historical data and verify results are reasonable
- Sensitivity Testing: Test how the model responds to parameter changes
Implementation Approach in Python/AMPL:
- Start with a small version of the problem to test logic
- Gradually increase problem size
- Use modular design with separate functions for model components
- Include input validation and error handling
- Create clear output reports
Step 4: Model Validation and Testing
Validation Tests:
| Test Type | Description | Pass Criteria |
|---|---|---|
| Feasibility Test | Does a feasible solution exist? | Model finds optimal solution, no infeasibility message |
| Reasonableness Test | Are results realistic for the domain? | Results align with domain expert expectations |
| Historical Test | How would solution perform on past scenarios? | Results are better than historical baseline |
| Extreme Point Test | Does model behave reasonably at parameter extremes? | No illogical or degenerate solutions |
| Sensitivity Test | How sensitive is solution to parameter changes? | Sensitivity is consistent with domain knowledge |
Step 5: Solution Generation and Analysis
Key Outputs:
- Optimal solution values for all decision variables
- Objective function value
- Solution status (optimal, feasible, infeasible)
- Solver statistics (iterations, time, gap)
- Constraint utilization report
- Sensitivity analysis results
Step 6: Implementation and Deployment
Deployment Strategy:
- Pilot Program: Test solution with limited scope and subset of users
- User Training: Train operations staff on solution interpretation and use
- System Integration: Integrate optimization solution with existing systems (ERP, databases)
- Monitoring and Adjustment: Track actual vs. projected performance; adjust model parameters as needed
- Full Rollout: Gradually expand to all operations
Change Management:
- Communicate benefits and changes to all stakeholders
- Address concerns and resistance with evidence
- Provide adequate training and support
- Document all new procedures and policies
- Establish feedback mechanisms for continuous improvement
Practical Example: Transportation Problem Step-by-Step
Problem Setup:
A manufacturing company operates 3 warehouses and serves 4 regional customers. We need to determine optimal shipment quantities to minimize transportation costs while meeting customer demand and warehouse capacity.
Data:
| Warehouse | Supply (units) |
|---|---|
| W1 | 100 |
| W2 | 150 |
| W3 | 120 |
| Customer | Demand (units) |
|---|---|
| C1 | 80 |
| C2 | 70 |
| C3 | 50 |
| C4 | 90 |
AMPL Solution:
set WAREHOUSES;
set CUSTOMERS;
param supply{WAREHOUSES};
param demand{CUSTOMERS};
param cost{WAREHOUSES, CUSTOMERS};
var Ship{WAREHOUSES, CUSTOMERS} >= 0;
minimize Total_Cost: sum{i in WAREHOUSES, j in CUSTOMERS} cost[i,j] * Ship[i,j];
subject to Supply{i in WAREHOUSES}:
sum{j in CUSTOMERS} Ship[i,j] <= supply[i];
subject to Demand{j in CUSTOMERS}:
sum{i in WAREHOUSES} Ship[i,j] = demand[j];
data;
set WAREHOUSES := W1 W2 W3;
set CUSTOMERS := C1 C2 C3 C4;
param supply := W1 100 W2 150 W3 120;
param demand := C1 80 C2 70 C3 50 C4 90;
param cost: C1 C2 C3 C4 :=
W1 2 3 1 4
W2 6 1 8 3
W3 3 5 2 5;
5. Analysis and Interpretation of Results
Learning Objectives
- Understand how to interpret optimization results
- Learn sensitivity analysis techniques
- Master trade-off analysis and scenario planning
- Develop skills in presenting results to stakeholders
Understanding the Solution Report
Optimization solvers produce detailed reports that contain crucial information for decision-making. Understanding these reports is essential for proper interpretation and implementation of solutions.
Key Components of Solution Reports
1. Problem Statistics
- Number of variables: Total count of decision variables in the model
- Number of constraints: Total count of constraints
- Nonzeros: Number of non-zero coefficients in the constraint matrix
- Density: Percentage of matrix that contains non-zero values (typically 0.1-5%)
2. Solver Performance
| Metric | Description | Interpretation |
|---|---|---|
| Status | Solution status (optimal, feasible, infeasible) | Optimal is best; feasible indicates time limit; infeasible needs model review |
| Objective Value | Value of the objective function | The best solution found by the solver |
| Iterations | Number of algorithm iterations | More iterations suggest a harder problem |
| Time (seconds) | Wall-clock time to solve | Indicates computational complexity |
| Gap | Optimality gap (for incomplete solutions) | Shows how far from proven optimal (if incomplete) |
Sensitivity Analysis
Sensitivity analysis examines how the optimal solution changes when model parameters vary. This is crucial for understanding solution robustness and identifying critical parameters.
Types of Sensitivity Analysis
1. Range of Optimality for Objective Coefficients
This analysis determines the range over which an objective function coefficient can change without affecting the optimal basis (though the objective value will change). The ranges are provided as allowable increases and decreases.
Current range: [c_j - allowable_decrease, c_j + allowable_increase]
Example: If the cost of shipping from W1 to C1 is $2 with allowable decrease of $0.50 and allowable increase of $1.50, the current optimal solution remains optimal as long as the cost is between $1.50 and $3.50.
2. Range of Feasibility for Constraint RHS
This analysis determines the range over which the right-hand side (RHS) of a constraint can change while maintaining the same shadow price (dual value). Shadow prices indicate the rate of change of the objective value with respect to changes in the constraint RHS.
Shadow price: λ_i = change in objective value / change in RHS
Valid range: [b_i - allowable_decrease, b_i + allowable_increase]
3. Shadow Prices (Dual Values)
Shadow prices represent the marginal value of relaxing a constraint by one unit. They indicate:
- How much the objective function would improve if we could loosen a constraint
- The maximum price we should pay to obtain one additional unit of a scarce resource
- The minimum price reduction we need to make an activity worthwhile
Interpretation Guidelines:
- Positive shadow price (for minimization): Resource is scarce; relaxing constraint is beneficial
- Zero shadow price: Constraint is not binding; has slack
- Shadow price valid range: The range shown applies to the shadow price validity
Scenario Analysis
Scenario analysis involves solving the optimization model under different assumptions to explore potential outcomes.
Common Scenarios:
- Best Case Scenario: Most favorable parameter assumptions (lowest costs, highest prices, etc.)
- Worst Case Scenario: Least favorable parameter assumptions
- Most Likely Scenario: Expected parameter values based on forecasts
- What-If Scenarios: Specific policy or market changes (e.g., new capacity, competitor entry)
Implementation Steps:
- Identify 3-5 key scenarios representing different business environments
- For each scenario, adjust model parameters appropriately
- Solve the model under each scenario
- Compare solutions and key metrics across scenarios
- Identify robust strategies that perform well across scenarios
Presenting Results to Stakeholders
Executive Summary (1-2 pages):
- Problem statement and business objectives
- Key findings and recommendations
- Expected benefits (cost savings, efficiency gains, etc.)
- Implementation timeline and requirements
Technical Report (10-20 pages):
- Detailed problem formulation
- Mathematical model with all components
- Data sources and validation
- Solution method and algorithm
- Results and analysis
- Sensitivity analysis findings
- Implementation recommendations
- Appendices with data and detailed calculations
Visual Presentations:
- Charts showing current vs. optimized performance
- Network diagrams for distribution problems
- Gantt charts for scheduling solutions
- Sensitivity tornado charts showing parameter impact
- Scenario comparison dashboards