SAA for stochastic programs with endogenous uncertainty

This archive is distributed in association with the INFORMS Journal on Computing under the MIT License.

The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper Solving Two-Stage Programs with Endogenous Uncertainty via Random Variable Transformation by Maria Bazotte, Margarida Carvalho and Thibaut Vidal. The snapshot is based on this SHA in the development repository.

Important: This code is developed at https://github.com/mariabazotte/saa_endog. Please go there if you would like to get a more recent version or would like support

Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2024.0847

https://doi.org/10.1287/ijoc.2024.0847.cd

Below is the BibTex for citing this snapshot of the repository.

@misc{saaendog,
  author =        {Maria Bazotte, Margarida Carvalho and Thibaut Vidal},
  publisher =     {INFORMS Journal on Computing},
  title =         {{SAA for stochastic programs with endogenous uncertainty}},
  year =          {2024},
  doi =           {10.1287/ijoc.2024.0847.cd},
  url =           {https://github.com/INFORMSJoC/2024.0847},
  note =          {Available for download at https://github.com/INFORMSJoC/2024.0847},
}  

Description

This project contains the code for the paper "Solving Two-Stage Programs with Endogenous Uncertainty via Random Variable Transformation". It contains the implementation of the two-stage Network Design and Facility Protection Problem (NDFPP) with endogenous uncertainty introduced in this paper.

Building

Instances

The folder data/ contains the data files needed for experiments in the paper. The folder data/generator includes the file usa_network_generator.py to create new network instances as explained in the paper. The instances are generated based on the Basic US Cities dataset available at https://simplemaps.com/data/us-cities (folder data/generator/data_usa/). To generate a network file, execute:

python usa_network_generator.py -minpop X -nbfacilities X

where:

• -minpop 3000 # Threshold population to select cities from the southeastern region of the United States.
• -nbfacilities 4 # Number of facilities of the instance.

The network file is created at the directory data/usa/. The directory data/ also contains the parameters file, which contains:

• nbProtectionLevelsFacilities=4 # Number of protection levels for the facilities
• facilitiesImpact=0.3 # Impact of other facilities (for binomial, normal and std. normalization)
• penaltyUnmetDemand=10 # Unit penalty for unmet demand
• objectiveOrConstriantWithInstallCost=0 # 0: Cost in budget constraint, 1: Cost is in the objective
• noDisrUncertain=0 # 0: no-disruption event is not uncertain, 1: no-disruption event is uncertain

Main Code

Folder scr/ contains the source code. To run the source code, execute:

make 
./exe -parameters

Where we have the following parameters:

Mandatory parameters:

• -paramfile ../data/params.txt # Path to parameters file
• -networkfile ../data/usa/15nodes4facilities.txt # Path to network file
• -solver 0 # 0: SAA Applied to Transformed (Exogenous) Program (SAA-TP in the paper), 1: Det. Equiv. Original (Endogenous) Program (DE-OP in the paper) (Referred here as Linearization), 2: Det. Equiv. Original (Endogenous) Program (DE-OP in the paper) solved with L-Shaped (Referred here as Linearization-LShaped), 3: EV problem and computation of the EEV
• -distribution # 0: Discrete Selection (NDFPP-Selection), 1: Binomial (NDFPP-Binomial), 2: Normal (NDFPP-Normal), 3: Std. Normalization (NDFPP-Discrete)

Instance parameters:

• -nb_capa_levels 2 # Number of capacity levels of facilities for discrete distributions (for Normal is 0)
• -percentage_budget 0.5 # Percentage of maximal budget for the budget constraint
• -edge_cost_mult 10 # Unit cost for opening one unit of edge

Running parameters:

• -timelimit 3600 # Time limit for optimization
• -nbthreads 1 # Number of threads for gurobi
• -seed 0 # Seed (data generation - cost of facility protection)
• -verbose 0 # 0 -> nothing, 1-> moderated, 2-> intensive (log files)

L-shaped parameters (for DE-OP with L-Shaped):

• -precision 0.0001 # Precision to stop optimization
• -ithotstart 100 # Max nb of iterations for hot start
• -papadakos 1 # 0-> no papadakos cuts, 1-> include papadakos cuts
• -callback 0 # 0-> normal LShaped (multiple trees), 1-> "Benders and cut"
• -typecut 0 # 0-> cuts only when a integer solution is found, 1-> cuts for fractional solutions also included
• -validinequalityEV # 0-> do not use EV valid inequality, 1-> use EV valid inequality

SAA parameters (for SAA-TP):

• -nbproblemsSAA 50 # Number of problems for SAA
• -nbscenariosSAA 750 # Number of scenarios for each SAA problem
• -nbvalidatescenariosSAA 150000 # Number of scenarios for the validation problem of the SAA
• -validinequalitySAA # 0-> do not use valid inequality for SAA problem, 1-> use valid inequality (only for Binomial and Std. Nomalization)

Folders main code

The main code contains the following folders:

• -src/input # This folder contains the class Input, which stores information on input parameters provided by the user to the solver during code execution.
• -src/data # This folder contains several classes related to instances: Instance holds general information about an instance, such as network configuration. AllSceInstance enumerates scenarios for the original endogenous program, representing realizations of endogenous variables. SAAInstance generates scenarios for the transformed exogenous program, providing sample realizations of exogenous random variables based on a specific transformation (distribution option).
• -src/solver # This folder contains implementations of various approaches. Within src/solver/saa, you'll find the SAAProblem class, which implements the SAA-TP approach. In src/solver/baseline, there are baseline implementations: the ExpectedValueProblem class handles the EV problem of the original endogenous program, computing the EEV. The LinearizationProblem class implements the DE-OP without L-Shaped.
• src/lshaped # This folder contains classes for L-Shaped implementation: Lshaped, LinearizionMainProblem, and LinearizationSubproblem, which implement the DE-OP with L-Shaped.

Results

The results are saved in a repository such as:

• results
  • compiled
  • saa
    • discreteselection
    • binomial
    • stdnormalization
    • normal
  • expected
    • discreteselection
    • binomial
    • stdnormalization
    • normal
  • linearization:
    • discreteselection

Each test generates a separate .csv file in the folder corresponding to the method—saa (SAA-TP), expected (EV problem), or linearization (DE-OP)—and the endogenous distribution, which can be discrete selection, binomial, stdnormalization, discrete, or normal. The folder results/compiled contains an Excel file that compiles the experimental results for the paper. This file includes sheets for each specific instance configuration, providing detailed information about all tests. The data for Table 1 is stored in the tables_mean sheet, while Tables 2 and 3 are in ev_tables_mean sheet. Figure 1 is based on data from tables_per_seed sheet. The table in Appendix K also uses tables_per_seed sheet, it considers only instances with seed 0. Similarly, the table in Appendix M is found in ev_tables_per_seed sheet and considers instances with seed 0. Finally, the table in Appendix N is contained in ev_tables_mean sheet.

Replicating

The folder scripts/ contains the sbatch files for replicating the results of the paper. Specifically, the files job_linearization.sh, job_saa.sh, and job_expected.sh contain the commands for the paper's results. After executing these sbatch files, the result .csv files are written in the folder results, according to the configuration explained before.

Unifying paper results

The file unify_results.py unifies the results contained in the .csv files, creating the Excel file with the compiled experimental results of the paper. After running the sbatch files, execute:

python unify_results.py

You can modify this file to see the results of other parameters. The unified results are in the folder results/compiled.

Development

This code is developed at the author's Github site.

Support

For support in using this software, submit an issue.