This project forms part of Heuristic combinatorial optimization course that forms part of Computer Science degree at Facultad de Ciencias, Universidad Nacional Autónoma de México. It tries to find a solution to Minimum Weight Vertex Coverage Problem using Ant Colony Optimization algorithm with some few variants.
For further understanding you can refer to the PDF document in spanish.
Meson build system is used to compile this project. Running:
$ meson build && cd build
$ ninja
in the root directory should setup build directory with the executable inside.
Use $ build/MWVCP_AntColony -h
to know more about the available options.
$ ./MWVCP_AntColony -h
MWVCP solution using Ant Colony heuristic.
Usage:
./MWVCP_AntColony [OPTION...]
-h, --help Show help
-f, --file input_file Input file to read instance (ignore to read from
stdin)
-s, --seed N Seed to use. Default is 0
-g, --graph output_file Create gv file of the solution.
If dot is installed you can create svg using:
$ dot in.gv -Tsvg > out.svg
This option generates a dot file that represents the original graph with the vertex in best solution found coloured.
The ant colony optimization heuristic can be tuned to experiment different results. The header file include/AntColony.hpp contains the constraints that can be modified.
Credits to jarro2783 for his cxxopts library to parse command line options.