[![INFORMS Journal on Computing Logo](https://INFORMSJoC.github.io/logos/INFORMS_Journal_on_Computing_Header.jpg)](https://pubsonline.informs.org/journal/ijoc)

# Theoretical and Numerical Comparison of Nine Single-level Reformulations for Bilevel Programs

This archive is distributed in association with the [INFORMS Journal on
Computing](https://pubsonline.informs.org/journal/ijoc) under the [GNU General Public License v3.0](LICENSE).

This repository contains supporting materials for the paper
[Theoretical and Numerical Comparison of Nine Single-level Reformulations for Bilevel Programs](https://doi.org/10.1287/ijoc.2025.1159) by Y. W. Li, G. H. Lin and X. Zhu. 

The software and data in this repository are a snapshot of the software and data that were used in the research reported in the paper.

## 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.2025.1159

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

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

```
@article{Li2025.1159,
  author =        {Yu-Wei Li and Gui-Hua Lin and Xide Zhu},
  publisher =     {INFORMS Journal on Computing},
  title =         {Theoretical and Numerical Comparison of Nine Single-level Reformulations for Bilevel Programs},
  year =          {2025},
  doi =           {10.1287/ijoc.2025.1159.cd},
  url =           {https://github.com/INFORMSJoC/2025.1159},
  note =          {Available for download at https://github.com/INFORMSJoC/2025.1159},
}  
```

## Description

This repository aims to provide the source code and numerical examples used to illustrate the effectiveness of the approaches developed in the paper ``Theoretical and Numerical Comparison of Nine Single-Level Reformulations for Bilevel Programs''.

## Repository Structure

### Code

This code package provides implementations of direct and relaxation methods with projection for solving bilevel programs. The framework include nine reformulations: MPCC, WDP, MDP, eMDP, TWDP, TMDP, eTMDP, ETMDP, and eETMDP. Due to MATLAB’s case-insensitive file naming rules, all files corresponding to ETMDP and eETMDP are denoted by STMDP and eSTMDP, respectively.

The folder [code](code) contains three subfolders:

- [code_linear_linear](code/code_linear_linear)
  
- [code_linear_quadratic](code/code_linear_quadratic)

- [code_quadratic_quadratic](code/code_quadratic_quadratic)

These folders correspond to three classes of bilevel programs defined by the type of lower-level problem: linear programs (**GroupI**); quadratic programs (**GroupII**); quadratically constrained quadratic programs (**GroupIII**).

Each subfolder includes the following categories of files:

- [problem](code/problem.m): Scripts for randomly generating bilevel test problems of the corresponding type.
  
- [fun](code/fun.m) : Objective functions for the upper-level problem.
  
- [fun_proj](code/fun_proj.m) : Objective function of the projection problem
  
- [main_MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/STMDP/eSTMDP](code/main_MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/STMDP/eSTMDP.m): the main program that solves bilevel programs by the MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/ETMDP/eETMDP direct method.
  
- [constraints_MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/STMDP/eSTMDP](code/constraints_MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/STMDP/eSTMDP.m): constraints for solving bilevel programs by the MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/ETMDP/eETMDP direct method.

- [main_RMPCC/RWDP/RMDP/ReMDP/RTWDP/RTMDP/ReTMDP/RSTMDP/ReSTMDP](code/main_RMPCC/RWDP/RMDP/ReMDP/RTWDP/RTMDP/ReTMDP/RSTMDP/ReSTMDP.m): the main program that solves bilevel programs by the MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/ETMDP/eETMDP relaxation method.
  
- [constraints_RMPCC/RWDP/RMDP/ReMDP/RTWDP/RTMDP/ReTMDP/RSTMDP/ReSTMDP](code/constraints_RMPCC/RWDP/RMDP/ReMDP/RTWDP/RTMDP/ReTMDP/RSTMDP/ReSTMDP.m): constraints for solving bilevel programs by the MPCC/WDP/MDP/eMDP/TWDP/TMDP/eTMDP/ETMDP/eETMDP relaxation method.

Additional Files for [code_quadratic_quadratic](code/code_quadratic_quadratic)

- [fun_lower](code/code_quadratic_quadratic/fun_lower.m): the objective function of the lower-level problem

- [constraints_lower](code/code_quadratic_quadratic/constraints_lower.m): quadratic constraints of the lower-level problem


### Data

No separate data folder is provided. All test instances used in the numerical experiments are generated automatically by the **problem** scripts located in the following three subfolders:

- [code_linear_linear](code/code_linear_linear)
  
- [code_linear_quadratic](code/code_linear_quadratic)

- [code_quadratic_quadratic](code/code_quadratic_quadratic)

Each folder includes a **problem** file that defines the problem dimensions and generates one class of bilevel programming instances. All datasets in our study can be fully reproduced by adjusting the parameter values in the corresponding **problem** script. A fixed random seed is set in the main program, ensuring complete reproducibility of all results.

**Group I** 

| Instances| Dimensions {n, l, m, p, q} |
| ---------| -------------------------- |
| 1-50     |   20, 25, 100, 110, 20     |
| 51-100   |   20, 25, 120, 130, 40     |
| 101-150  |   20, 25, 140, 150, 60     |

**Group II and Group III**

| Instances| Dimensions {n, l, m, p, q} |
| ---------| -------------------------- |
| 1-50     |   20, 25, 30, 20, 10       |
| 51-100   |   20, 25, 50, 40, 20       |
| 101-150  |   20, 25, 70, 60, 30       |

**Parameter Definitions**

- n: dimension of upper-level variable

- l: number of upper-level constraints

- m: dimension of lower-level variable

- p: number of lower-level inequality constraints

- q: number of lower-level equality constraints

### Results

The [results](results) are divided into two components. The first part reports the detailed numerical outcomes obtained from solving the bilevel programs using all nine methods. These results are organized into three groups:

- [Result_GroupI](results/Result_GroupI.xlsx) —— detailed numerical results for Group I bilevel programs.
  
- [Result_GroupII](results/Result_GroupII.xlsx) —— detailed numerical results for Group II bilevel programs.
  
- [Result_GroupIII](results/Result_GroupIII.xlsx) —— detailed numerical results for Group III bilevel programs.
  
The second part presents the analytical summaries based on these numerical outcomes. **Tables 1-11** in the paper correspond to the analysis derived from the results in the three groups.

- [Table 1](results/Table_1_Comparison_of_direct_and_relaxation_algorithms_with_projection.pdf) shows the comparison results of the projection based direct and relaxation algorithms across all reformulations.
  
- [Table 2-4](results/Table_2-4_Overall_comparison_of_nine_reformulations_for_direct_or_relaxation_algorithms_in_Group_I-III.pdf) show the overall comparison results of nine reformulations for direct or relaxation algorithms in Group I-III.
  
- [Table 5](results/Table_5_Overall_comparison_of_nine_reformulations_for_direct_or_relaxation_algorithms_in_all_groups.pdf) shows the overall comparison results of nine reformulations for direct or relaxation algorithms in all groups.
  
- [Table 6-7](results/Table_6-7_Pairwise_comparison_of_dominant_cases_for_direct&relaxation_algorithms_in_three_groups.pdf) show the pairwise comparison results of dominant cases for direct/ relaxation algorithms in three groups.
  
- [Table 8-9](results/Table_8-9_Pairwise_comparison_of_gapvalues_for_direct&relaxation_algorithms_in_three_groups.pdf) show the pairwise comparison results of gap values for direct/ relaxation algorithms in three groups.

- [Table 10-11](results/Table_10-11_Pairwise_comparison_of_ratios_(dominant_casesgaps)_for_direct&relaxation_algorithms_with_450_examples.pdf) show the pairwise comparison results of ratios (dominant cases/gaps) for direct/ relaxation algorithms with 450 examples.

## Requirements

All optimization problems are solved using **MATLAB 9.13.0**.

## Support

For support in using the code, don't hesitate to get in touch with the corresponding author.
