Description: This notebook marks the beginning of a six-part series.
We start with a straightforward facility location problem, demonstrating how to utilize AMPL and the amplpy module within a Jupyter Notebook to find a solution.
As the series progresses, the problem complexity will increase, evolving into a two-stage stochastic programming problem.
From the third notebook onwards, our focus will pivot from modeling to algorithm development in AMPL.
We’ll explore four distinct approaches to implementing the Benders decomposition: initially through AMPL scripting, then by shifting control flow to the amplpy module.
This transition allows us to illustrate how subproblems can be solved in parallel.
Lastly, we’ll introduce our AMPLS library, which facilitates exporting AMPL model instances to persistent solver representations.
This approach enables an exceptionally efficient Benders decomposition implementation.
Problem description
Facility location decisions are crucial and often involve significant investment for both public and private sector entities, bearing profound social, economic, and environmental implications.
The strategic positioning of facilities, such as warehouses, factories, and service centers, can determine an organization’s operational efficiency, market reach, and overall sustainability.
Given the high stakes of these decisions, engineers and analysts have developed sophisticated models to aid organizations in identifying optimal locations.
These models take into account a variety of factors, including but not limited to, transportation costs, proximity to customers and suppliers, labor availability, customer demand, and environmental regulations.
The challenge is compounded when considering the uncertainty inherent in future conditions.
Factors such as fluctuating market demands, changes in infrastructure, and unpredictable socio-economic developments require a robust approach to facility location.
Therefore, as we will explore in the second notebook of this series, engineers frequently utilize stochastic models and robust optimization techniques.
These approaches are designed to accommodate uncertainties, ensuring that the selected locations remain effective across various potential future scenarios.
AMPL implementation
Translating the mathematical formulation of our optimization problem into an AMPL model is a direct process.
The AMPL code closely mirrors each inequality in the system (1), preserving the structure of the mathematical model.
AMPL’s expressive syntax allows for meaningful names for entities such as variables, parameters, and constraints, enhancing the model’s clarity.
For instance, we’ll represent the set $I$ as FACILITIES, and $J$ as CUSTOMERS.
Variables previously denoted as $x$ and $y$ will be named facility_open and production, respectively.
Similarly, we will rename our parameters for greater clarity: $f_i$ becomes fixed_cost, $q_ij$ is now variable_cost, $\lambda_j$ is referred to as customer_demand, and $k_i$ is labeled as facility_capacity.
Using descriptive names not only enhances the readability of the model but also its maintainability and the ease with which it can be shared and understood by others.
Creating the model file
Creating an AMPL model file is straightforward: simply open a text editor, type your AMPL model, and then submit it to the ampl interpreter.
You can do this either by passing it as a command-line argument or by using it in interactive mode.
For more details on these processes, refer to the AMPL book.
In the context of a Jupyter Notebook, like the one we are using, you can create an AMPL model file directly within a code cell.
To do this, we’ll employ the %%writefile magic command, which acts as our text editor for generating the model file.
The syntax %%writefile <filename> will create a file named <filename> in the notebook’s current working directory.
As far as ampl is concerened, the file extension is not crucial, but it’s customary to use the .mod suffix for model files.
As we progress and begin to utilize AMPL’s Python API, we’ll demonstrate how to load these model files into AMPL for further use.
Specifying Data
Once you have formulated your optimization problem mathematically, as discussed previously, writing the AMPL model becomes relatively straightforward.
For detailed guidance on AMPL syntax, the AMPL book is an excellent resource.
However, a model without data will result in an error message, not a solution.
AMPL supports a variety of data loading methods.
In production environments, data is typically sourced from databases, CSV or Excel files, or existing data frames, such as those in Pandas.
AMPL is equipped with features and tools that allow for seamless data importation from any of these sources.
It’s important to note that AMPL also supports loading data from a dedicated data file, usually with a .dat suffix.
However, if your data is already in an Excel file, a database, a data frame, or another storage format, there is NO NEED to convert it into a .dat file for AMPL.
Using .dat files can be convenient if you don’t have access to real data yet and wish to test your model.
Below, we will demonstrate how to provide data using .dat files.
In subsequent notebooks, as we increasingly utilize AMPL’s Python API, we will transition to using Pandas data frames for data input.
For a comprehensive overview of loading data from databases, Excel, or CSV files, please refer to our data connectors page.
Various demands
For our specific problem we will specify 3 data files.
Each data file will represent a customer demand scenario: low, medium, or high.
Similar as above we will use the jupyter notebook magic %%writefile <filename> to write our data files in the current working directory.
Outside of a Jupyter notebook you can use any text editor to do this.
Solve for each scenario and check for optimality
Outside of a Jupyter notebook, there are several approaches to solve our model for each scenario.
You might, for example, use a bash script to iterate through all files, invoking ampl on each one.
Alternatively, an AMPL script named det.run could be written as follows:
option solver highs;
option omit_zero_rows 1, omit_zero_cols 1, display_precision 0;
model floc_det.mod;
data floc_low.dat;
solve;
print "LOW DEMAND COST:";
display TotalCost;
print "LOW DEMAND SOLUTION:";
display facility_open;
reset data;
data floc_med.dat;
solve;
print "MEDIUM DEMAND COST:";
display TotalCost;
print "MEDIUM DEMAND SOLUTION:";
display facility_open;
reset data;
data floc_high.dat;
solve;
print "HIGH DEMAND COST:";
display TotalCost;
print "HIGH DEMAND SOLUTION:";
display facility_open;
This script can then be executed from the terminal with the command ampl det.run.
Within a Jupyter Notebook, we’ll leverage amplpy for a similar purpose as outlined in the AMPL script above.
The Python API will allow us to instantiate an AMPL object and utilize its methods to read model and data files, configure options, issue solve commands, and refresh our data as needed.
It’s important to note that customer_demand is the only parameter that varies across the different scenarios in our data files.
This observation suggests that it might not be necessary to create three distinct data files and reset all our data after each solve, as the AMPL script above does.
Instead, we can begin with a single data file for the low demand scenario, floc_low.dat.
For the medium and high scenarios, we can simply use AMPL’s update data command to modify the customer_demand parameter accordingly.
Solve for low demand
Relying on AMPL’s Python API.
Number of variables: 15
Number of constraints: 8
Presolve eliminates 0 constraints and 1 variable.
Adjusted problem:
14 variables:
2 binary variables
12 linear variables
8 constraints, all linear; 28 nonzeros
8 inequality constraints
1 linear objective; 14 nonzeros.
HiGHS 1.6.0:HiGHS 1.6.0: optimal solution; objective 15966984.87
8 simplex iterations
1 branching nodes
Success: Problem solved to optimality!
TotalCost = 15966984.865
facility_open [*] :=
Baton_Rouge_LA 1
Baytown_TX 1
;
Solve for medium demand
HiGHS 1.6.0:HiGHS 1.6.0: optimal solution; objective 15966984.87
8 simplex iterations
1 branching nodes
Success: Problem solved to optimality!
TotalCost = 15966984.865
facility_open [*] :=
Baton_Rouge_LA 1
Baytown_TX 1
Beaumont_TX 0
;
Solve for high demand
Presolve eliminates 1 constraint and 2 variables.
Adjusted problem:
13 variables:
1 binary variable
12 linear variables
7 constraints, all linear; 25 nonzeros
7 inequality constraints
1 linear objective; 13 nonzeros.
HiGHS 1.6.0:HiGHS 1.6.0: optimal solution; objective 22250711.2
6 simplex iterations
1 branching nodes
Success: Problem solved to optimality!
TotalCost = 22250711.200000003
facility_open [*] :=
Baton_Rouge_LA 1
Baytown_TX 1
Beaumont_TX 1
;
Conclusion
In this section, we’ve covered foundational aspects of modeling in AMPL, including how to import data and utilize AMPL’s Python API.
Our exploration revealed that for low to medium demand scenarios, opening just two facilities suffices to meet customer needs.
However, the surge in demand under the high-demand scenario necessitates the operation of all three facilities.
Moving forward, we’ll demonstrate a more efficient approach that avoids solving three distinct problems.
Instead, we’ll consolidate them into a single problem.
This will be accomplished by formulating the extensive form of the stochastic capacitated facility location problem, streamlining the entire process.