Branch and Bound TSP

Table Of Contents

• Branch and Bound TSP
  • Table Of Contents
  • Project Description
  • Input File
  • Running The Program
  • Project Dependencies
  • References

Project Description

This project is a Branch and Bound Algorithm implementation project for solving the TSP Problem, assigned as a bonus task for the Algorithm and Strategies Course. Given a graph representation as adjacency matrix, using the reduced cost matrix approach. Made by Kenneth Ezekiel 13521089, Bandung Institute of Technology.

The constraint in this implementation is that the adjacency matrix must contain all values (all nodes must be connected to every other node). This project is also made using Ruby.

Input File

Input files can be placed in the test folder, with the following constraints:

• Numbers must be separated by spaces
• The matrix must be a square matrix
• The diagonal of the matrix must be all inf signifying infinite
• All rows are separated by new lines or \n (simply press enter)

Running The Program

1. Make sure to have ruby installed
2. Open the root directory of this project in the terminal
3. Run the program using ruby src/tsp.rb
4. The program will ask for an input file name, which can be inserted into the test directory in the form of a .txt file

Project Dependencies

Ruby 3.1 - Installed from here

References

• Algorithm Strategies Course IF2211 2022/2023 Module from here