Project Structure

APPALGO-SOSE24
│
│── LICENSE.txt
│
│── README.md
│
└── src
    |
    ├── solver.py
    |
    ├── solver.bat
    │
    └── requirements.txt

Description

This project is a STUDENT SUBMISSION and contains a solver for the PACE-Exact Track 2024 challenge. The solver aims to minimize crossings in bipartite graphs using linear programming and various optimization techniques.

Our approach first attempts to minimize crossings by assigning a truth value for each crossing. Due to this simplistic restriction, cycles can occur in the B partition (y). We then systematically try to reduce these cycles by adding constraints. Attempting to add all constraints initially sets too many constraints for the ILP solver, making it infeasible. However, the current solution is memory and runtime intensive.

From the medium_test_sets, only the following graphs run within the allotted time: 8.gr, 9.gr, 10.gr, 11.gr, 14.gr, 40.gr, 48.gr, 49.gr, 52.gr.

Setup

1. Install Python: go to python.org

2. Navigate to src:

   cd appalgo-sose24/src

3. Create and Activate a Virtual Environment (Optional but recommended):

   python3 -m venv venv

   In a Unix-based System run:

   source venv/bin/activate

   In Windows run:

   .venv\Scripts\activate

4. Install the External Libraries: This project requires to install the libraries in the requirements.txt:

   pip install -r requirements.txt

5. Run the code with given instances using PowerShell:

   To run the solver with an input file, use the following command:

   Get-Content path/to/input_file.gr | python solver.py

   Example:

   Get-Content githubtests/tiny_test_set/instances/complete_4_5.gr | python solver.py

Verifier and Tester in PowerShell

Installation

Install the verifier from pip with the requirements.

Usage

For tiny_test_sets only in Powershell

```bash
pace2024tester --instanceas=stdin --solutionas=stdout solver.bat
```

With medium_test_sets:

```bash
pace2024tester --test githubtests/medium_test_set --instanceas=stdin --solutionas=stdout solver.bat
```

With more_test_sets:

 pace2024tester --test <path/to/mytests1> --test <path/to/mytests2> --instanceas=stdin --solutionas=stdout solver.bat
 ```