Project Intoduction

This project implements four algorithms (Branch-and-Bound, constructive heursitic with approximation guarantee, and two local searches) for the Minimum Vertex Cover (MVC) problem. The detailed definition for the MVC problem and these algorithm can be found in the accompanying report.

The project also executed these four algorithms on several test cases of various sizes, collected relevant data, and performed comparative analysis of these algorithms. The results can also be found in the accompanying report.

The following sections of this README file will further discuss the technical details of the project. Detailed discussions on the implementation logics can be found in comments and docstrings in the scripts. Other summarizing information and theoretical parts can be found in the accompanying report.

Project Environment

The project is written entirely in Python 3.9.5 on Windows 11, using Visual Studio Code version 1.73.1. The project is stored on a GitHub private repository, which is available for access upon request.

Project Structure

This section discusses the structure and organization of the project.

File Structure

During the implementation stage, the following structure is adopted for the main functionalities of the project:

• FOLDER: bin

  • main.py: main driver

  • MSC.py: key data structures

  • util.py: useful helper functions

  • BnB.py: Branch-and-bound algorithm

  • Approx.py: Constructive heuristic with approximation guarantee

  • LS1.py: Local search algorithm 1

  • LS2.py: Local searcth algorithm 2

  • verify.py: Verifies the consistency, validity and optimality of the outputs of an execution.

  • wrapper.py: A dynamically modified script for running and verifying multiple test cases.

  • QRTD_SQD.py: A file that parses outputs and generates QRTD, SQD, and Box plots.

• FOLDER: output

  • xxx.sol: contains final quality and solution to a given execution.

  • xxx.trace: contains the recorded qualities of a given execution over time.

• FOLDER: DATA

  • xxx.graph: graph files in Metis I/O format. Provided as inputs.

There are other folders and files used during implementation but are not included in the submission. These files are omitted here.

Imports

The external (to the project) Python packages imported include: numpy, time, copy, random, sys, os.path, subprocess, matplotlib.pyplot. Note that subprocess and matplotlib are only used in wrapper.py and QRTD_SQD.py, respectively, and are not required for executing the main functionality of the project.

Dependency

The following summarizes the dependency relationships between the scripts:

• main.py <- MSC.py

• MSC.py <- BnB.py, Approx.py, LS1.py, LS2.py

• util.py <- N/A

• BnB.py <- util.py

• Approx.py <- util.py

• LS1.py <- util.py

• LS2.py <- util.py

• verify.py <- MSC.py

• wrapper.py <- main.py, verify.py

• QRTD_SQD.py <- N/A

Details about the data structures and functions implemented can be found in the scripts.

Executation Instruction

There are several executions to this project:

main.py:

Peforms the main functionality of the project: finds a solution to a test case using a selected algorithm, under a certain cutoff time, with a random seed. The following structure is required for executing this file:

"python main.py -inst filename -alg [BnB|Approx|LS1|LS2] -time <cutoff in seconds> -seed <random seed>"

All elements are required. Even though Branch-and-Bound does not need a random seed, this term is still required, but will be ignored. (i.e. use any number).

verify.py

Verifies the solution files (.sol and .trace) are consistent (with each other), valid (valid vertex cover for the graph), and optimal. To run this script, use the following input argument:

"python verify.py filename_[BnB]_<cutoff in seconds>" for BnB cases,

or

"python verify.py filename_[Approx|LS1|LS2]_<cutoff in seconds>_<random seed>" for other algorithms.

wrapper.py

This file is executed without any input argument, and can be modified dynamically to specify test cases to run.

QRTD_SQD.py

This file is executed without any input argument, and will produce results automatically (no modification needed).