Introduction
In the world of enterprise optimization, practitioners often face a fundamental challenge: how do we make optimal decisions today when critical parameters are uncertain and their true values will only be revealed in the future? Traditional deterministic optimization assumes perfect knowledge of all parameters, yet reality rarely affords us such luxury. From supply chain demand to resource availability, uncertainty is the norm rather than the exception.
Cost Function Approximation (CFA) policies, formalized by Prof. Warren Powell, offer a practical and elegant approach to bridging this gap when optimizing under uncertainty. Rather than attempting to solve complex two-stage or multi-stage stochastic programs directly, CFA leverages a parameterized deterministic optimization model combined with simulation-based learning to adapt decision-making over time.
In this blog post, we'll walk through an implementation of a CFA policy for an artificial Soccer Camp Location problem, demonstrating how to build a system that learns from simulated experience to improve its decision-making under uncertainty. The implementation is available in this repository and is built using the FICO Xpress Optimization Tech Stack which includes a state-of-the-art optimization solver capable of solving LP, MIP, (MI)QP, (MI)QCQP, (MI)SOCP, CP, NLP, and Global (MI)NLP problems and a deployment platform that streamlines building user-friendly web applications.
The Problem: Soccer Camp Location Under Uncertain Demand
Consider a city that operates seasonal soccer camps at local parks for students. Each day interested students sign up to attend, but the number of participants varies significantly based on factors like weather, competing activities, and school schedules. The city must decide:
The traditional stochastic programming approach endogenously captures the uncertainty in the model, using distribution estimates to create scenarios. On the other hand, CFA does not explicitly include uncertainty in the model but instead leverages simulation and a tunable parameter as mechanisms to deal with uncertainty.
An important phenomenon we capture in this exercise is the distinction between estimated distributions and the actual distributions of the uncertain parameters. One of the advantages of CFA is its ability to learn both from estimated distributions in a simulation or from the actual distributions in production, making it particularly robust to inaccurate distribution estimates.
Understanding Cost Function Approximation
A CFA policy is comprised of three core components working in concert:
Implementation Architecture
Our implementation is organized into modular components that separate concerns cleanly and can be found in the subfolderSoccerCampLocationApp/python_source/:
The Parametric Optimization Model
The heart of our CFA is a Mixed Integer Programming (MIP) model based on the classic facility location problem formulation, that determines where to locate camps and how to allocate demand. Let's examine its formulation:
Sets
Decision Variables
Objective Function
The model minimizes total cost, comprised of setup costs and transportation costs:
Mathematically:
Demand Coverage Constraint
Every school's demand must be fully allocated:
Parametric Capacity Constraint
Here lies the key to CFA—the capacity constraint includes the learnable parameter Θj for each potential site j:
The parameter Θj (stored in thepenaltiesdictionary) allows the model to learn that certain locations consistently face capacity issues due to the realizations of uncertain demand. A negative Θj effectively reduces the usable capacity, causing the optimizer to allocate less demand to that site or avoid selecting it altogether.
Simulating Uncertain Demand
The simulator serves two critical purposes: it provides feedback for learning and validates the policy's performance under realistic conditions.
Handling the Estimation vs. Reality Gap
A crucial design decision in our framework is maintaining separate demand distributions—one used by the optimizer (estimates) and one used by the simulator (actuals):
This separation mirrors real-world conditions where demand forecasts are imperfect. The estimated distributions inform planning, but actual demand—drawn from potentially different distributions—determines outcomes.
Tracking Capacity Utilization
After sampling demand, the simulator applies the optimization solution to determine capacity utilization:
Negative residual capacity indicates unmet demand—students who wanted to attend but couldn't due to capacity constraints.
The Learning Mechanism
After each simulation iteration, the parameter update rule adjusts Θ values based on observed capacity violations:
This update rule embodies a simple but effective principle:
Where is the residual capacity (negative when demand exceeds capacity) and α is the step size. Themin(0, ...)ensures we only penalize capacity when violations occur—we're learning to be more conservative where needed, not more aggressive. This learning mechanism can always be modified and should be revisited based on the Key Performance Indicators tracked from production runs.
The CFA Training Loop
The complete training process orchestrates these components across multiple simulation days:
Each iteration represents one day of operation where we:
Evaluation: Comparing CFA Against Baseline
The power of CFA becomes evident when comparing against a naive baseline that uses no learned parameters:
Key metrics to compare include:
Design Decisions and Extensions
Several aspects of this implementation warrant consideration for practical deployment:
Choosing the Step Size
The step size α controls learning speed versus stability. Larger values accelerate learning but may cause oscillation; smaller values provide smoother convergence but require more iterations. The implementation allows experimentation:
Parameter Usage After Training
Post-training, practitioners can choose how to use learned parameters:
Continued Learning in Production
The framework supports continued parameter updates during deployment by setting a non-zero step size during testing, allowing the policy to adapt to changing conditions.
Conclusion
Cost Function Approximation provides a practical methodology for optimization under uncertainty that acknowledges the inherent limitations of deterministic models. By combining mathematical optimization with simulation-based learning, CFA policies can adapt to real-world conditions that violate modeling assumptions.
Two key insights from this implementation are:
The complete implementation demonstrates shows a basic implementation of a CFA policy built with straightforward Python code and the FICO Xpress optimization engine, allowing practitioners at all levels to explore this approach to Sequential Decision Problems.
This implementation uses FICO Xpress software under the Community License terms. For production deployments, consult FICO's licensing options.
Claude Code Opus 4.5 was used to create an initial draft of this article
In the world of enterprise optimization, practitioners often face a fundamental challenge: how do we make optimal decisions today when critical parameters are uncertain and their true values will only be revealed in the future? Traditional deterministic optimization assumes perfect knowledge of all parameters, yet reality rarely affords us such luxury. From supply chain demand to resource availability, uncertainty is the norm rather than the exception.
Cost Function Approximation (CFA) policies, formalized by Prof. Warren Powell, offer a practical and elegant approach to bridging this gap when optimizing under uncertainty. Rather than attempting to solve complex two-stage or multi-stage stochastic programs directly, CFA leverages a parameterized deterministic optimization model combined with simulation-based learning to adapt decision-making over time.
In this blog post, we'll walk through an implementation of a CFA policy for an artificial Soccer Camp Location problem, demonstrating how to build a system that learns from simulated experience to improve its decision-making under uncertainty. The implementation is available in this repository and is built using the FICO Xpress Optimization Tech Stack which includes a state-of-the-art optimization solver capable of solving LP, MIP, (MI)QP, (MI)QCQP, (MI)SOCP, CP, NLP, and Global (MI)NLP problems and a deployment platform that streamlines building user-friendly web applications.
The Problem: Soccer Camp Location Under Uncertain Demand
Consider a city that operates seasonal soccer camps at local parks for students. Each day interested students sign up to attend, but the number of participants varies significantly based on factors like weather, competing activities, and school schedules. The city must decide:
- Where to locate camps (facility location decisions)
- How to allocate students from schools to camps (assignment decisions)
The traditional stochastic programming approach endogenously captures the uncertainty in the model, using distribution estimates to create scenarios. On the other hand, CFA does not explicitly include uncertainty in the model but instead leverages simulation and a tunable parameter as mechanisms to deal with uncertainty.
An important phenomenon we capture in this exercise is the distinction between estimated distributions and the actual distributions of the uncertain parameters. One of the advantages of CFA is its ability to learn both from estimated distributions in a simulation or from the actual distributions in production, making it particularly robust to inaccurate distribution estimates.
Understanding Cost Function Approximation
A CFA policy is comprised of three core components working in concert:
- A Parametric Optimization Model: A deterministic optimization problem augmented with learnable parameters that influence its behavior
- A Simulator: A process that generates realistic demand scenarios to test and train the model
- A Parameter Update Rule: A mechanism to adjust parameters based on observed simulation outcomes
Implementation Architecture
Our implementation is organized into modular components that separate concerns cleanly and can be found in the subfolderSoccerCampLocationApp/python_source/:
- Instance Container (instance.py): Encapsulates all input data including schools, sites, distances, and both estimated and actual demand distributions
- Optimization Engine (simulator.py: optimize()): Formulates and solves the parametric optimization model
- Demand Simulator (simulator.py: simulate_demand()): Samples from actual demand distributions and tracks capacity utilization
- Parameter Updater (simulator.py: adjust_opti_penalties()): Implements the learning rule to adjust capacity parameters
The Parametric Optimization Model
The heart of our CFA is a Mixed Integer Programming (MIP) model based on the classic facility location problem formulation, that determines where to locate camps and how to allocate demand. Let's examine its formulation:
Sets
- Schools: set of schools whose students can participate in the soccer camps
- Sites: potential locations where a soccer camp can be setup
Decision Variables
serves = prob.addVariables(instance.schools, instance.sites, vartype=xp.continuous)
build = prob.addVariables(instance.sites, vartype=xp.binary)
build = prob.addVariables(instance.sites, vartype=xp.binary)
- build
: Binary variable indicating whether site j is selected (1) or not (0) - serves[i,j]: Continuous variable representing the fraction of school i's demand served by site j
Objective Function
The model minimizes total cost, comprised of setup costs and transportation costs:
prob.setObjective(
xp.Sum(instance.school_stats.get(i)[0] * instance.dist[i,j] * serves[i,j]
for i in instance.schools for j in instance.sites)
+ xp.Sum(instance.truck_cost.get(j)*build for j in instance.sites))
xp.Sum(instance.school_stats.get(i)[0] * instance.dist[i,j] * serves[i,j]
for i in instance.schools for j in instance.sites)
+ xp.Sum(instance.truck_cost.get(j)*build
Mathematically:
Demand Coverage Constraint
Every school's demand must be fully allocated:
prob.addConstraint(xp.Sum(serves[i,j] for j in instance.sites) == 1for i in instance.schools)
Parametric Capacity Constraint
Here lies the key to CFA—the capacity constraint includes the learnable parameter Θj for each potential site j:
prob.addConstraint(
xp.Sum(instance.school_stats.get(i)[0] * serves[i,j] for i in instance.schools) <=
(instance.truck_capacities.get(j) + penalties.get(j, 0)) * build
for j in instance.sites)
xp.Sum(instance.school_stats.get(i)[0] * serves[i,j] for i in instance.schools) <=
(instance.truck_capacities.get(j) + penalties.get(j, 0)) * build
for j in instance.sites)
The parameter Θj (stored in thepenaltiesdictionary) allows the model to learn that certain locations consistently face capacity issues due to the realizations of uncertain demand. A negative Θj effectively reduces the usable capacity, causing the optimizer to allocate less demand to that site or avoid selecting it altogether.
Simulating Uncertain Demand
The simulator serves two critical purposes: it provides feedback for learning and validates the policy's performance under realistic conditions.
Handling the Estimation vs. Reality Gap
A crucial design decision in our framework is maintaining separate demand distributions—one used by the optimizer (estimates) and one used by the simulator (actuals):
if train_flag:
params = instance.school_stats # Estimated parameters
else:
params = instance.real_school_stats # Actual parameters
demand = {
school: max(0, random.normalvariate(*params.get(school)))
for school in instance.schools
}
params = instance.school_stats # Estimated parameters
else:
params = instance.real_school_stats # Actual parameters
demand = {
school: max(0, random.normalvariate(*params.get(school)))
for school in instance.schools
}
This separation mirrors real-world conditions where demand forecasts are imperfect. The estimated distributions inform planning, but actual demand—drawn from potentially different distributions—determines outcomes.
Tracking Capacity Utilization
After sampling demand, the simulator applies the optimization solution to determine capacity utilization:
capacities = {
site: instance.truck_capacities.get(site)
for site, value in built.items() if value > 0.5
}
for (school, site), ratio in solution.items():
capacities.update({
site: capacities.get(site, 0) - int(ratio * demand.get(school))
})
site: instance.truck_capacities.get(site)
for site, value in built.items() if value > 0.5
}
for (school, site), ratio in solution.items():
capacities.update({
site: capacities.get(site, 0) - int(ratio * demand.get(school))
})
Negative residual capacity indicates unmet demand—students who wanted to attend but couldn't due to capacity constraints.
The Learning Mechanism
After each simulation iteration, the parameter update rule adjusts Θ values based on observed capacity violations:
defadjust_opti_penalties(capacities: dict, penalties: dict, step_size: float):
for site, penalty in capacities.items():
penalties.update({
site: penalties.get(site, 0) + min(0, step_size * penalty)
})
for site, penalty in capacities.items():
penalties.update({
site: penalties.get(site, 0) + min(0, step_size * penalty)
})
This update rule embodies a simple but effective principle:
Where is the residual capacity (negative when demand exceeds capacity) and α is the step size. Themin(0, ...)ensures we only penalize capacity when violations occur—we're learning to be more conservative where needed, not more aggressive. This learning mechanism can always be modified and should be revisited based on the Key Performance Indicators tracked from production runs.
The CFA Training Loop
The complete training process orchestrates these components across multiple simulation days:
defcfa(number_of_simulation_days: int, step_size: float, penalties: dict, train_flag: bool):
results = []
all_penalties = []
all_penalties.append(penalties.copy())
for i inrange(number_of_simulation_days):
# Solve parametric optimization
served, built, E = optimize(instance, penalties)
# Simulate demand and observe outcomes
capacities = simulate_demand(instance, built, E, train_flag)
# Update parameters based on feedback
adjust_opti_penalties(capacities, penalties, step_size)
all_penalties.append(penalties.copy())
# Record metrics
# ...
return pd.DataFrame(results), all_penalties
results = []
all_penalties = []
all_penalties.append(penalties.copy())
for i inrange(number_of_simulation_days):
# Solve parametric optimization
served, built, E = optimize(instance, penalties)
# Simulate demand and observe outcomes
capacities = simulate_demand(instance, built, E, train_flag)
# Update parameters based on feedback
adjust_opti_penalties(capacities, penalties, step_size)
all_penalties.append(penalties.copy())
# Record metrics
# ...
return pd.DataFrame(results), all_penalties
Each iteration represents one day of operation where we:
- Solve the location problem given current parameters
- Simulate what actually happens with realized demand
- Learn from any capacity violations
- Record performance metrics for analysis
Evaluation: Comparing CFA Against Baseline
The power of CFA becomes evident when comparing against a naive baseline that uses no learned parameters:
# Baseline: Static optimization with no learned parameters
penalties = {site: 0for site in instance.sites}
results_baseline, _ = cfa(test_days, stepsize=0, penalties, train_flag=False)
# CFA: Using trained parameters
penalties = all_penalties.pop() # Use final trained parameters
results_cfa, _ = cfa(test_days, stepsize=0, penalties, train_flag=False)
penalties = {site: 0for site in instance.sites}
results_baseline, _ = cfa(test_days, stepsize=0, penalties, train_flag=False)
# CFA: Using trained parameters
penalties = all_penalties.pop() # Use final trained parameters
results_cfa, _ = cfa(test_days, stepsize=0, penalties, train_flag=False)
Key metrics to compare include:
- Objective Value: Total operational cost (setup + transportation)
- Truck Installation Cost: Fixed costs from opened locations
- Total Serving Cost: Variable transportation costs
- Total Missed Demand: Students excluded due to capacity constraints
Design Decisions and Extensions
Several aspects of this implementation warrant consideration for practical deployment:
Choosing the Step Size
The step size α controls learning speed versus stability. Larger values accelerate learning but may cause oscillation; smaller values provide smoother convergence but require more iterations. The implementation allows experimentation:
simulation_days = 20
stepsize = 1# Aggressive learning during training
stepsize = 1# Aggressive learning during training
Parameter Usage After Training
Post-training, practitioners can choose how to use learned parameters:
- Final values: Use the last Θ values from training
- Averaged values: Average across training iterations for stability
- Exponentially smoothed: Weight recent iterations more heavily
Continued Learning in Production
The framework supports continued parameter updates during deployment by setting a non-zero step size during testing, allowing the policy to adapt to changing conditions.
Conclusion
Cost Function Approximation provides a practical methodology for optimization under uncertainty that acknowledges the inherent limitations of deterministic models. By combining mathematical optimization with simulation-based learning, CFA policies can adapt to real-world conditions that violate modeling assumptions.
Two key insights from this implementation are:
- Parameterization matters: The choice of where and how to inject learnable parameters determines what the model can learn to adapt to.
- Simple update rules can be effective: Despite its simplicity, the penalty update rule successfully teaches the model to be conservative where needed.
The complete implementation demonstrates shows a basic implementation of a CFA policy built with straightforward Python code and the FICO Xpress optimization engine, allowing practitioners at all levels to explore this approach to Sequential Decision Problems.
This implementation uses FICO Xpress software under the Community License terms. For production deployments, consult FICO's licensing options.
Claude Code Opus 4.5 was used to create an initial draft of this article
Updated 6 months ago
Version 3.0