Travelling Salesman Programming Assignment
Write a multi-threaded program for solving the traveling salesman problem using the branch-and-bound technique. You may write your C++ assignment or Java assignment to implement this multi-threaded program.
Task assignments to the threads may be static or dynamic. Since the multi-thread program executes in a shared memory platform, both task assignment strategies can easily be adopted. Experiment with the different number of threads for both task assignment strategies, observe the execution times and report your observations.
Recall in employing the branch and bound technique for solving the traveling salesman problem, certain rules of inference would be useful in helping reduce the size of the state space tree:
1. Use a heuristic to compute a lower bound for each node.
2. When considering the inclusion of an edge in a branch step, if the inclusion will lead to more than 2 incident edges to a city, the branch can be terminated there.
3. When considering the inclusion of an edge in a branch step, if the inclusion will result in a premature cycle (i.e., a cycle of size < the number of cities in the map), the branch can be terminated there.
4. When considering the exclusion of an edge in a branch step, if the exclusion will lead to a city not having 2 edges incident to it in the end, the branch can be terminated there.
5. As soon as the search identifies a tour, record it as the best-cost-so-far. Update this cost when a new tour with a better cost is found. This cost can be used in pruning those tree nodes with lower bound >= this cost.
Solution:
#include < bits stdc++.h="">
#include < iostream>
#include < iomanip>
#include < ctime>
#include < fstream>
#include < pthread.h>
using namespace std;
#define maximum_of_city 100
int number_city;
int inputgraph[maximum_of_city][maximum_of_city];
int first = 0;
int threads = 2;
int flag;
struct tspSearchParams {
int curr;
bool visited_city[maximum_of_city];
int City[maximum_of_city];
float Lower_Bound = 0;
float edge_cost = 0;
float minimumcost = 0;
int level = 0;
int from = 0;
int to = 0;
bool multithread = false;
};
tspSearchParams* copyParams(tspSearchParams* origin) {
tspSearchParams* copy = new tspSearchParams();
for (int i = 0; ivisited_city[i] = origin->visited_city[i];
copy->City[i] = origin->City[i];
}
copy->Lower_Bound = origin->Lower_Bound;
copy->edge_cost = origin->edge_cost;
copy->minimumcost = origin->minimumcost;
copy->level = origin->level;
copy->from = 0;
copy->to = number_city;
copy->multithread = false;
return copy;
}
void input_print_Graph() {
cout << "Insert number of cities: ";
cin >> number_city;
cout << "Insert the graph: " << endl;
for(int i = 0; i < number_city; i++) {
for(int j = 0; j < number_city; j++) {
cin >> inputgraph[i][j];
}
}
cout << "The graph you input: " << endl;
for(int i = 0; i < number_city; i++) {
for(int j = 0; j < number_city; j++) {
cout << inputgraph[i][j] << " ";
}
cout << endl;
}
}
void readFile() {
fstream file("weightmatrix2.txt");
file >> number_city;
for(int i = 0; i < number_city; i++) {
for(int j = 0; j < number_city; j++){
file >> inputgraph[i][j];
}
}
file.close();
cout << "The City Matrix you input: " << endl;
for(int i = 0; i < number_city; i++) {
for(int j = 0; j < number_city; j++){
cout << inputgraph[i][j] << " ";
}
cout << endl;
}
}
//find smallest number in each row for input graph
float smallestnum(int v) {
int smallest = INT_MAX;
for (int j = 0; j < number_city; j++) {
if(v != j) {
if (inputgraph[v][j] < smallest) {
smallest = inputgraph[v][j];
}
}
}
return smallest;
}
//find second smallest number in each row for input graph
float secondsmallestnum(int v) {
int smallest = INT_MAX;
int secondsmallest = INT_MAX;
for (int j = 0; j < number_city; j++) {
if(v == j) {
continue;
}
if (inputgraph[v][j] <= smallest) {
secondsmallest = smallest;
smallest = inputgraph[v][j];
}
else if(inputgraph[v][j] <= secondsmallest && inputgraph[v][j] != smallest) {
secondsmallest = inputgraph[v][j];
}
}
return secondsmallest;
}
void compute_lowerbound(tspSearchParams* root) {
for (int i = 0; i < number_city; i++) {
root->Lower_Bound += (smallestnum(i) + secondsmallestnum(i)) / 2;
root->visited_city[i] = false;
}
}
void* TSPBnB(void* args) {
tspSearchParams* params = (tspSearchParams*)args;
int v = params->curr;
params->City[params->level] = v;
if (params->level + 1 < number_city) {
int level = params->level;
params->visited_city[v] = true;
if (params->level == 0 && !params->multithread) {
int div = number_city / threads;
int mod = number_city % threads;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
pthread_t pthreads[threads];
for (int j = 0; j < threads; j++) {
int from = div * j + ((j >= mod) ? mod : j);
int to = div * (j+1) + ((j+1 >= mod) ? mod : (j+1));
tspSearchParams* copy = copyParams(params);
copy->from = from;
copy->to = to;
copy->multithread = true;
pthread_create(&pthreads[j], &attr, TSPBnB, (void *)copy);
}
for (int j = 0; jminimumcost > 0 && (result->minimumcost < params->minimumcost || params->minimumcost < 1)) {
params->minimumcost = result->minimumcost;
for (int k = 0; kCity[k] = result->City[k];
}
}
delete result;
}
pthread_attr_destroy(&attr);
}
else {
for (int i = params->from; i < params->to; i++) {
if (params->visited_city[i] == false) {
float temp = params->Lower_Bound;
tspSearchParams* copy = copyParams(params);
copy->level++;
copy->curr = i;
copy->edge_cost += inputgraph[v][i];
if (copy->level == 1) {
copy->Lower_Bound -= ((smallestnum(copy->City[level]) + smallestnum(i)) / 2);
}
else {
copy->Lower_Bound -= ((secondsmallestnum(copy->City[level]) + smallestnum(i))/ 2);
}
if(copy->Lower_Bound + copy->edge_cost < copy->minimumcost || params->minimumcost < 1) {
TSPBnB(copy);
if (copy->minimumcost > 0 && (copy->minimumcost < params->minimumcost || params->minimumcost < 1)) {
params->minimumcost = copy->minimumcost;
for (int k = 0; kCity[k] = copy->City[k];
}
}
}
if(flag == 1) {
if(copy->Lower_Bound + copy->edge_cost >= copy->minimumcost) {
cout << copy->Lower_Bound + copy->edge_cost << " been pruned" << endl;
}
}
delete copy;
}
}
}
}
else {
params->edge_cost += inputgraph[v][first];
params->minimumcost = params->edge_cost;
if(flag == 1) {
cout << "Current minimum cost: " << params->minimumcost << endl;
}
}
return (void*)params;
}
int main() {
readFile();
cout << endl;
cout << endl;
cout << "Please insert 1 if you want verbose output (1/0): ";
cin >> flag;
clock_t start, end;
double total_time;
start = clock();
tspSearchParams* params = new tspSearchParams();
compute_lowerbound(params);
if(flag == 1) {
cout << "Root's lower bound: " << params->Lower_Bound << endl;
}
params->curr = first;
params->from = 0;
params->to = number_city;
params->multithread = false;
TSPBnB(params);
end = clock();
total_time = end - start;
cout << endl;
cout << "Final Path: ";
for (int i = 0; i < number_city; i++) {
cout << params->City[i] + 1 << " -> ";
}
cout << params->City[0] + 1 << endl;
cout << "Cost of the Final Path: " << params->minimumcost << endl;
cout << "Execution time: " << total_time << endl;
delete params;
return 0;
}