The purpose of this project is to solve the Minimum Cardinality Subset of Bases to Arm problem. Given an undirected graph representing military bases and their mutual protections, and some critical points that need to be protected, the objective is to find the minimum subset of bases that need to be armed to protect all critical points.
The Minimum Cardinality Subset of Bases to Arm problem is a variant of the Minimum Dominating Set problem, where we aim to minimize the cardinality of the set of vertices in a graph such that all critical points are either in the set or are adjacent to a vertex in the set.
- Clone this repository:
git clone https://github.com/Gklajer/AIR-BASE-DEFENSE.git. - Navigate to the project directory:
cd AIR-BASE-DEFENSE. - Install the required dependencies:
pip install -r requirements.txt.
- Python 3.6+
- See requirements.txt for the required packages
- AMPL
The program generates a random graph of military bases and identifies the critical bases that need to be protected. It then uses integer linear programming to find the minimum subset of bases that need to be armed to protect all critical points.
The output of the program is a visual representation of the graph, with the critical bases marked in red and the minimum subset of bases to arm marked with a diamond shape.
-
To run the main script that generates a graph of bases, saves it to PDF and DAT formats, and runs the AMPL model on the DAT file, run:
python base_defense.py
-
To run experiments on different versions of the greedy algorithm, run:
python experiments_greedy.py
This project is licensed under the MIT License.
Contributions to the project are welcome. If you find any bugs or issues, please create an issue in the project repository. Pull requests for bug fixes, new features, or improvements are also welcome.