Travelling Salesman Problem

[varghese]

( IMPORTANT. PLEASE NOTE. First copy the code exactly as it is from the Word files and paste them into an editor ( for eg:- Notepad++ ) and save them as '.php' files or as '.sql' files as the case may be. For eg:- 'tsp_1_epct.docx' should be converted into 'tsp_1_epct.php' file. 'List_of_tables.docx' should be converted into 'List_of_tables.sql' file. The 'List_of_tables.docx' file is uploaded in the last post, because a maximum of 5 files is only allowed to be uploaded in each post in the forum. )

The list of files to be converted is given below.
1) 'tsp_1_epct.docx' should be converted into 'tsp_1_epct.php'.
2) 'tsp_2_epct.docx' should be converted into 'tsp_2_epct.php'.
3) 'tsp_3_epct.docx' should be converted into 'tsp_3_epct.php'.
4) 'tsp_4_epct.docx' should be converted into 'tsp_4_epct.php'.
5) 'tsp_5_epct.docx' should be converted into 'tsp_5_epct.php'.
6) 'List_of_tables.docx' should be converted into 'List_of_tables.sql'.

The algorithm is called 'Travelling Salesman Problem Minimum Weight Hamilton Circuit' or 'TSP_MWHC'. The algorithm in this posting is called 'TSP_MWHC_1' because this program processes tables with EDGE_WEIGHT_TYPE of 'EXPLICIT' data as given in the TSPLIB Format. The algorithm in the next posting is given the title of 'TSP_MWHC_2'. The second algorithm is called 'TSP_MWHC_2' because it processes tables with EDGE_WEIGHT_TYPE of 'EUC_2D' data as given in the TSPLIB Format. This posting gives an explanation about 'TSP_MWHC_1'.

The general guideline is given below in 9 steps. These steps may vary according to the different type of computers and the different versions of XAMPP Webservers , PHP etc.. that are used in each type of computer.

1) Download 'XAMPP' for Windows from the internet and install 'XAMPP' Web server.
2) Create a folder for eg:- 'tsp_programs' in "C:\xampp\htdocs" folder.
3) Copy the php files ( ie :- 'tsp_1_epct.php' , 'tsp_2_epct.php' , 'tsp_3_epct.php' , 'tsp_4_epct.php' and 'tsp_5_epct.php') and paste the php files into ' C:\xampp\htdocs\tsp_programs' folder.
4) Open 'XAMPP' Control Panel and start Apache first and then start MySql.
5) Open Google Chrome browser and in the URL address, type 'localhost/phpmyadmin' and press enter.
The phpmyadmin page will be shown.
6) From phpmyadmin , create a database named 'tsp_data_for_program_database'.
( VERY IMPORTANT. PLEASE NOTE. When creating the new database, the database name should be exactly 'tsp_data_for_program_database'. If the name is different, the php files will not work. )
7) Import the example tables into "tsp_data_for_program_database" database using the import file 'List_of_tables.sql'.
8) Open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs' and press enter.
9) A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_epct.php'. From 'tsp_1_epct.php', the execution of the program can start, by clicking on 'tsp_1_epct.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )


A General Note about the PHP Program.


This PHP program finds the 'polynomial time' exact solution to the Travelling Salesman Problem for a 'Complete' graph using a database, so that data does not have to be typed in always.

This is a general optimal weight program in 'PHP' for solving the Travelling Salesman Problem for any number of vertices.

The input data during the execution of the program is only the name of each vertex and the weight of each edge present in the graph.

( PLEASE NOTE :- If for an example graph, if there is no edge between two vertices, then assign a weight to the imaginary edge connecting the two vertices. The weight can be equal to the sum of the weights of all the real edges present in the example graph. This imaginary edge with a weight is necessary because of the condition that this program works on 'Complete' graphs only. A 'Complete' graph is exactly the same mathematical object used in Graph Theory. Also please note that no edge in the example graph should have a weight of 0. )

To work with PHP files , 'XAMPP' Web Server has to be installed in the Computer. 'XAMPP' Web Server is available on the internet.

After installing XAMPP and when XAMPP Web Server is running , it is better not to connect to the internet , because of 'XAMPP' itself being a Web Server and so when XAMPP is running and if the computer is connected to the internet, other insecure connections can become connected to the computer. So as far as possible, once XAMPP is fully installed , and before starting to run XAMPP, it is better to disconnect the computer from the internet. After php program has finished executing, and Apache and Mysql has been stopped from the XAMPP control panel , and when XAMPP has been quit completely, then the computer can be connected to the internet.


Important details about database program

In this program , a 'Mysql' database is used , so that input need not always be typed in when executing the program. There are five php files which contain the php code for executing the program with a database. 'tsp_1_epct.php' , 'tsp_2_epct.php' , 'tsp_3_epct.php' , 'tsp_4_epct.php' and 'tsp_5_epct.php'are the five php files. The order of execution of the php files is 'tsp_1_epct.php' , 'tsp_2_epct.php' , 'tsp_3_epct.php' , 'tsp_4_epct.php' and 'tsp_5_epct.php'. The execution need only to be started from 'tsp_1_epct.php'.

The 'XAMPP' Web Server is used for executing the php files and for processing the table data present in the database. All the five 'php' files ( ie:- 'tsp_1_epct.php' , 'tsp_2_epct.php' , 'tsp_3_epct.php' , 'tsp_4_epct.php' and 'tsp_5_epct.php' ) can be put in 'C:\xampp\htdocs\tsp_programs' folder. The execution need only to be started from 'tsp_1_epct.php'.

If any of the example tables is imported into the database , it should always be imported into the database named " tsp_data_for_program_database". The 'phpmyadmin' database interface can be used for importing the table sql files.

An example of a table is as follows. A table 'vrts_15_po1_explicit' is present as an example of data of a fifteen vertex graph in the "List_of_tables.sql" table. For running the example of a 'fifteen' vertex graph, the 'vrts_15_po1_explicit' can be selected from the drop down list of the tables , when the file 'tsp_1_epct.php' is executed.

Also the format of the example tables in the database should be followed exactly for creating new example tables , otherwise the program will not work. An example of what is meant by format of the table, is that in the example table, there is no primary key column. So addition , deletion etc.. of data , while in phpmyadmin , cannot be done quickly on the tables, if changes need to be made on the data in the tables. So when creating a new table, create a temporary primary key column in order to quickly insert data into the example tables. After all the data has been entered into the example table, then the primary key column can be removed. ( Please note that a creation of a primary key column is not necessary and need only be created if data needs to be entered faster while working in phpmyadmin. )


Important properties of the PHP Program

The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

The program is an iteration type program and will give 1 or more hamilton circuits which may have the minimum weights. If more that one hamilton circuit is output, take the hamilton circuit with the least weight as the hamilton circuit with the most minimum weight.

The program process is divided into 2 parts. The first part gives an approximate minimum weight hamilton circuit. Then the program asks to press the button to find the optimal hamilton circuit and the optimal hamilton circuit is given in the second part of the process of the program.

The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

When a 33 vertex graph or a graph containing more than 33 vertices are given for processing to the program, errors showing 'undefined weights' and 'input values of 1000 exceeded' are given as output if the default value of the constant 'max_input_vars' in php is 1000.

In a 33 vertex graph, there are 1056 edges ( ie:- 33*32 = 1056 , since there are 33 vertices in the graph and there are 32 edges attached to each vertex ) or 1056 input values. 1056 is greater than 1000 and so the program will output an error since the number of input values exceed 1000.

For eg:- if a 50 vertex graph is to be processed, then there are 2450 edges ( ie:- 50*49 = 2450 , since there are 50 vertices in the graph and there are 49 edges attached to each vertex ) or 2450 input values. So 'max_input_vars' can be given a value higher than 2450 for eg:- 3000. So the 'max_input_vars' constant in php can be changed by uncommenting the line 'max_input_vars=1000' and giving a value of 'max_input_vars=3000' to the 'max_input_vars' constant.

The 'max_input_vars' constant can be found in 'php.ini' file which is present in 'C:/xampp/php' folder.

To verify if 'max_input_vars' has the required value, the function 'phpinfo()' can be typed in any empty php file and the file executed. This information displayed after execution of the 'phpinfo()' function will contain the value of 'max_input_vars' along with other information that the function will display.

Vertex names which are input into the program should begin with an english alphabet. The rest of the name should contain a combination of english alphabets or positive integer numbers or a combination of both english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

Each vertex name should be different from every other vertex name. No two or more vertices should have the same name.

Only positive numbers should be used for the weight values of the edges.

No edge should have a weight with a value of 0.

In "tsp_4_epct.php" , in line no 3 and line no 4, the following code is given. The code is as follows :-

Code Begin
ini_set('memory_limit', '2024M');
ini_set('max_execution_time', 86400);
Code End

( Note:- 'Code Begin' and 'Code End' are just markers to show the beginning and the ending of the code. )

The above code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default value given in php. To prevent this, the code ' ini_set('max_execution_time', 86400);' is given.

Also for the code given below as
Code Begin
'<?php
session_start();
?>'
Code End
( which is present at the very beginning of a php file ) please note that there should not be a space or even an empty line above this code if any code modification is made in the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code (ie:- the code included between the single apostrophies ) is present at the very beginning of the code file, without even a single space preceeding this line of code.

The files for 'TSP_MWHC_1' program are uploaded in this post.

[varghese]

( IMPORTANT. PLEASE NOTE. First copy the code exactly as it is from the Word files and paste them into an editor ( for eg:- Notepad++ ) and save them as '.php' files or as '.sql' files as the case may be. For eg:- 'tsp_1_db.docx' should be converted into 'tsp_1_db.php' file. 'List_of_tables.docx' should be converted into 'List_of_tables.sql' file. )

The list of files to be converted is given below.
1) 'tsp_1_db.docx' should be converted into 'tsp_1_db.php'.
2) 'tsp_2_db.docx' should be converted into 'tsp_2_db.php'.
3) 'tsp_3_db.docx' should be converted into 'tsp_3_db.php'.
4) 'tsp_4_db.docx' should be converted into 'tsp_4_db.php'.
5) 'List_of_tables.docx' should be converted into 'List_of_tables.sql'.

The algorithm is called 'Travelling Salesman Problem Minimum Weight Hamilton Circuit' or 'TSP_MWHC'. The algorithm in this posting is called 'TSP_MWHC_2' because this program processes tables with EDGE_WEIGHT_TYPE of 'EUC_2D' data as given in the TSPLIB Format. This posting gives an explanation about 'TSP_MWHC_2'.

The general guideline is given below in 9 steps. These steps may vary according to the different type of computers and the different versions of XAMPP Webservers , PHP etc.. that are used in each type of computer.

1) Download 'XAMPP' for Windows from the internet and install 'XAMPP' Web server.
2) Create a folder for eg:- 'tsp_programs' in "C:\xampp\htdocs" folder.
3) Copy the php files ( ie :- 'tsp_1_db.php' , 'tsp_2_db.php' , 'tsp_3_db.php' and 'tsp_4_db.php') and paste the php files into ' C:\xampp\htdocs\tsp_programs' folder.
4) Open 'XAMPP' Control Panel and start Apache first and then start MySql.
5) Open Google Chrome browser and in the URL address, type 'localhost/phpmyadmin' and press enter.
The phpmyadmin page will be shown.
6) From phpmyadmin , create a database named 'tsp_data_for_program_database'.
( VERY IMPORTANT. PLEASE NOTE. When creating the new database, the database name should be exactly 'tsp_data_for_program_database'. If the name is different, the php files will not work. )
7) Import the example tables into "tsp_data_for_program_database" database using the import file 'List_of_tables.sql'.
8) Open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs' and press enter.
9) A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_db.php'. From 'tsp_1_db.php', the execution of the program can start, by clicking on 'tsp_1_db.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )


A General Note about the PHP Program.


This PHP program finds the 'polynomial time' exact solution to the Travelling Salesman Problem for a 'Complete' graph using a database, so that data does not have to be typed in always.

This is a general optimal weight program in 'PHP' for solving the Travelling Salesman Problem for any number of vertices.

The input data during the execution of the program is only the name of each vertex and the weight of each edge present in the graph.

( PLEASE NOTE :- If for an example graph, if there is no edge between two vertices, then assign a weight to the imaginary edge connecting the two vertices. The weight can be equal to the sum of the weights of all the real edges present in the example graph. This imaginary edge with a weight is necessary because of the condition that this program works on 'Complete' graphs only. A 'Complete' graph is exactly the same mathematical object used in Graph Theory. Also please note that no edge in the example graph should have a weight of 0. )

To work with PHP files , 'XAMPP' Web Server has to be installed in the Computer. 'XAMPP' Web Server is available on the internet.

After installing XAMPP and when XAMPP Web Server is running , it is better not to connect to the internet , because of 'XAMPP' itself being a Web Server and so when XAMPP is running and if the computer is connected to the internet, other insecure connections can become connected to the computer. So as far as possible, once XAMPP is fully installed , and before starting to run XAMPP, it is better to disconnect the computer from the internet. After php program has finished executing, and Apache and Mysql has been stopped from the XAMPP control panel , and when XAMPP has been quit completely, then the computer can be connected to the internet.


Important details about database program

In this program , a 'Mysql' database is used , so that input need not always be typed in when executing the program. There are five php files which contain the php code for executing the program with a database. 'tsp_1_db.php' , 'tsp_2_db.php' , 'tsp_3_db.php' and 'tsp_4_db.php' are the four php files. The order of execution of the php files is 'tsp_1_db.php' , 'tsp_2_db.php' , 'tsp_3_db.php' and 'tsp_4_db.php'. The execution need only to be started from 'tsp_1_db.php'.

The 'XAMPP' Web Server is used for executing the php files and for processing the table data present in the database. All the four 'php' files ( ie:- 'tsp_1_db.php' , 'tsp_2_db.php' , 'tsp_3_db.php' and 'tsp_4_db.php' ) can be put in 'C:\xampp\htdocs\tsp_programs' folder. The execution need only to be started from 'tsp_1_db.php'.

If any of the example tables is imported into the database , it should always be imported into the database named " tsp_data_for_program_database". The 'phpmyadmin' database interface can be used for importing the table sql files.

An example of a table is as follows. A table 'vrts_15_po1_explicit' is present as an example of data of a fifteen vertex graph in the "List_of_tables.sql" table. For running the example of a 'fifteen' vertex graph, the 'vrts_15_po1_explicit' can be selected from the drop down list of the tables , when the file 'tsp_1_db.php' is executed.

Also the format of the example tables in the database should be followed exactly for creating new example tables , otherwise the program will not work. An example of what is meant by format of the table, is that in the example table, there is no primary key column. So addition , deletion etc.. of data , while in phpmyadmin , cannot be done quickly on the tables, if changes need to be made on the data in the tables. So when creating a new table, create a temporary primary key column in order to quickly insert data into the example tables. After all the data has been entered into the example table, then the primary key column can be removed. ( Please note that a creation of a primary key column is not necessary and need only be created if data needs to be entered faster while working in phpmyadmin. )


Important properties of the PHP Program

The program is designed to solve for any number of vertices for the Travelling Salesman Problem for Complete graphs.

The program is an iteration type program and will give 1 or more hamilton circuits which may have the minimum weights. If more that one hamilton circuit is output, take the hamilton circuit with the least weight as the hamilton circuit with the most minimum weight.

The program process is divided into 2 parts. The first part gives an approximate minimum weight hamilton circuit. Then the program asks to press the button to find the optimal hamilton circuit and the optimal hamilton circuit is given in the second part of the process of the program.

The number of vertices to be entered in the program can only be a positive integer which is equal to or greater than 4.

When a 33 vertex graph or a graph containing more than 33 vertices are given for processing to the program, errors showing 'undefined weights' and 'input values of 1000 exceeded' are given as output if the default value of the constant 'max_input_vars' in php is 1000.

In a 33 vertex graph, there are 1056 edges ( ie:- 33*32 = 1056 , since there are 33 vertices in the graph and there are 32 edges attached to each vertex ) or 1056 input values. 1056 is greater than 1000 and so the program will output an error since the number of input values exceed 1000.

For eg:- if a 50 vertex graph is to be processed, then there are 2450 edges ( ie:- 50*49 = 2450 , since there are 50 vertices in the graph and there are 49 edges attached to each vertex ) or 2450 input values. So 'max_input_vars' can be given a value higher than 2450 for eg:- 3000. So the 'max_input_vars' constant in php can be changed by uncommenting the line 'max_input_vars=1000' and giving a value of 'max_input_vars=3000' to the 'max_input_vars' constant.

The 'max_input_vars' constant can be found in 'php.ini' file which is present in 'C:/xampp/php' folder.

To verify if 'max_input_vars' has the required value, the function 'phpinfo()' can be typed in any empty php file and the file executed. This information displayed after execution of the 'phpinfo()' function will contain the value of 'max_input_vars' along with other information that the function will display.

Vertex names which are input into the program should begin with an english alphabet. The rest of the name should contain a combination of english alphabets or positive integer numbers or a combination of both english alphabets and positive integer numbers only. No other type of characters are allowed to be used in the vertex name.

Each vertex name should be different from every other vertex name. No two or more vertices should have the same name.

Only positive numbers should be used for the weight values of the edges.

No edge should have a weight with a value of 0.

In "tsp_4_db.php" , in line no 3 and line no 4, the following code is given. The code is as follows :-

Code Begin
ini_set('memory_limit', '2024M');
ini_set('max_execution_time', 86400);
Code End

( Note:- 'Code Begin' and 'Code End' are just markers to show the beginning and the ending of the code. )

The above code will become necessary when the number of vertices increases. This code is for increasing the processing memory and for increasing the execution time limit. If this code is not there, then sometimes php will stop program execution with error messages. For eg:- if the processing time exceeds 30 seconds, then php will automatically stop execution after 30 seconds, since 30 seconds is the default value given in php. To prevent this, the code ' ini_set('max_execution_time', 86400);' is given.

Also for the code given below as
Code Begin
'<?php
session_start();
?>'
Code End
( which is present at the very beginning of a php file ) please note that there should not be a space or even an empty line above this code if any code modification is made in the php file. Even if there is a single space before this line of code, the error of 'header output already sent' is most likely to be shown. So please make sure that this code (ie:- the code included between the single apostrophies ) is present at the very beginning of the code file, without even a single space preceeding this line of code.



The files for 'TSP_MWHC_2' program are uploaded in this post.

[varghese]

The file containing the tables is 'List_of_tables.docx'. 'List_of_tables.docx' should be converted into 'List_of_tables.sql' in order to import the file into Mysql database.

In the pdf file given in the website 'https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp95.pdf' for the details of the TSPLIB format, in 'Section 1.1.6' , for the EDGE_WEIGHT_TYPE , the type of 'EXPLICIT' and 'EUC_2D' are given. 'TSP_MWHC_1' is the program for processing the 'EXPLICIT' type of data and 'TSP_MWHC_2' is the program for processing the 'EUC_2D' type of data.

I have not uploaded the program for processing the 'ATT' and 'GEO' type of data for the 'EDGE_WEIGHT_TYPE' because in the present posts I am only giving the program for 'EXPLICIT' and 'EUC_2D' data types in order to avoid confusion. Also all the programs that I have is only able to process only upto 35 vertices on my laptop computer for a reasonable amount of time for eg:- upto a limit from 20 minutes to 1 hour. For higher than 35 vertices, a more powerful workstation computer is required in order to obtain the answer in a reasonable amount of time for eg:- a powerful workstation computer may solve a 100 vertices problem in 1 or 2 hours.

The list of tables that are present in the database file 'List_of_tables.sql' are

1) vrts_15_po1_explicit
2) vrts_bayg29_epxlicit
3) vrts_bays29_explicit
4) vrts_berlin52_euc_2d
5) vrts_dantzig42_explicit
6) vrts_dj38_euc_2d
7) vrts_dka1376_euc_2d
8) vrts_eil51_euc_2d
9) vrts_eil76_euc_2d
10) vrts_eil101_euc_2d
11) vrts_fri26_explicit
12) vrts_gr17_explicit
13) vrts_gr21_explicit
14) vrts_gr24_explcit
15) vrts_kroa100_euc_2d
16) vrts_krob100_euc_2d
17) vrts_kroc100_euc_2d
18) vrts_krod100_euc_2d
19) vrts_pbk411_euc_2d
20) vrts_pr76_euc_2d
21) vrts_st70_euc_2d
22) vrts_wi29_euc_2d
23) vrts_xit1083_euc_2d
24) vrts_xqf131_euc_2d
25) vrts_xqg237_euc_2d

The tables given above are of 2 types depending on the data they contain. For eg:- table 'vrts_15_po1_explicit' contains data of 'EXPLICIT' type for the 'EDGE_WEIGHT_TYPE'. So 'vrts_15_po1_explicit' can be used for processing only by 'TSP_MWHC_1' program. Table 'vrts_berlin52_euc_2d' contains data of 'EUC_2D' type for the 'EDGE_WEIGHT_TYPE'. So 'vrts_berlin52_euc_2d' can be used for processing only by 'TSP_MWHC_2' program. So the appropriate table has to be taken when processing for the 'TSP_MWHC_1' program or the 'TSP_MWHC_2' program. The suffix '_explicit' and '_euc_2d' present in the table names above determine if the table data is of 'EXPLICIT' data type or of 'EUC_2D' data type.

The tables given in the websites which correspond to the tables given in the list above are given in the list given below. In the format 'Table_m -> Table_n' , 'Table_m' refers to the table name given in the website and 'Table_n' refers to the table name given in the database.

The tables present in the different websites and the corresponding table names given in the database are given as follows :-

1) 'http://www.math.uwaterloo.ca/tsp/world/countries.html'
'Djibouti - 38 cities' -> vrts_dj38_euc_2d
'Western Sahara - 29 cities' -> vrts_wi29_euc_2d

2) 'http://www.math.uwaterloo.ca/tsp/vlsi/index.html'
XQF131 -> vrts_xqf131_euc_2d
XQG237 -> vrts_xqg237_euc_2d
PBK411 -> vrts_pbk411_euc_2d

3) 'http://www.math.uwaterloo.ca/tsp/vlsi/page2.html'
XIT1083 -> vrts_xit1083_euc_2d
DKA1376 -> vrts_dka1376_euc_2d

4) 'https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html'
P01 ( A set of 15 cities ) -> vrts_15_po1_explicit

5) 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html'
bayg29 -> vrts_bayg29_epxlicit
bays29 -> vrts_bays29_explicit
berlin52 -> vrts_berlin52_euc_2d
dantzig42 -> vrts_dantzig42_explicit
eil51 -> vrts_eil51_euc_2d
eil76 -> vrts_eil76_euc_2d
eil101 -> vrts_eil101_euc_2d
fri26 -> vrts_fri26_explicit
gr17 -> vrts_gr17_explicit
gr21 -> vrts_gr21_explicit
gr24 -> vrts_gr24_explcit
kroa100 -> vrts_kroa100_euc_2d
krob100 -> vrts_krob100_euc_2d
kroc100 -> vrts_kroc100_euc_2d
krod100 -> vrts_krod100_euc_2d
pr76 -> vrts_pr76_euc_2d
st70 -> vrts_st70_euc_2d


The file 'List_of_tables.docx' is uploaded in this post.

[varghese]

Hello to All,

I forgot to give a brief note about what the posts are about( ie:- the posts that I had posted on 24th May 2018 ).

The posts are about a polynomial time program that gives exact optimal minimum weight solutions for the Travelling Salesman Problem.

[varghese]

Hello to All,

I am just giving a very brief note about the main points that have to done before and during the execution of the PHP Program. This brief note is a very condensed note of the post that I had posted on '24th May 2018'.

BEGINNING OF NOTE :-


The PHP program which I had uploaded in the post dated '24th May 2018' works with a database , so it is important that the database import file ie:- 'List_of_tables.sql' which also was uploaded in the post dated '24th May 2018' should be imported into the
database for the PHP program to work.

Download 'XAMPP' for Windows from the internet and install 'XAMPP' Web server.

Create a folder for eg:- 'tsp_programs' in "C:\xampp\htdocs" folder.

First copy the code exactly as it is from the Word files that were uploaded in the post with the date of '24th May 2018' and paste them into an editor ( for eg:- Notepad++ ) and save them as '.php' files or as '.sql' files as the case may be. For eg:-
'tsp_1_epct.docx' should be converted into 'tsp_1_epct.php' file. The database file 'List_of_tables.docx' should be converted into 'List_of_tables.sql' file.

From phpmyadmin , create a database named 'tsp_data_for_program_database'.

Import the file 'List_of_tables.sql' into the database 'tsp_data_for_program_database'. If the file 'List_of_tables.sql' is imported into a database having a name , different from the name 'tsp_data_for_program_database' , then the PHP program will not work. So the database has to be named exactly 'tsp_data_for_program_database'.

The full form of 'TSP_MWHC' is 'Travelling Salesman Problem Minimum Weight Hamilton Circuit'.

'TSP_MWHC_1' is the program for processing the database data of 'EXPLICIT' type of the 'EDGE_WEIGHT_TYPE' as given in the TSPLIB format.

Create a folder for eg:- 'TSP_EXPLICIT_DATA' in "C:\xampp\htdocs\tsp_programs" folder.

'TSP_EXPLICIT_DATA' is a folder within the 'tsp_programs' folder.

The PHP code files for 'TSP_MWHC_1' program are
1) 'tsp_1_epct.php'
2) 'tsp_2_epct.php'
3) 'tsp_3_epct.php'
4) 'tsp_4_epct.php'
5) 'tsp_5_epct.php'

The files for 'TSP_MWHC_1' can be put in the folder ' C:\xampp\htdocs\tsp_programs\TSP_EXPLICIT_DATA'.

'TSP_MWHC_2' is the program for processing the database data of 'EUC_2D' type of the 'EDGE_WEIGHT_TYPE' as given in the TSPLIB format.

Create a folder for eg:- 'TSP_EUC_2D_DATA' in "C:\xampp\htdocs\tsp_programs" folder.

'TSP_EUC_2D_DATA' is a folder within 'tsp_programs' folder.

The PHP code files for 'TSP_MWHC_2' program are
1) 'tsp_1_db.php'
2) 'tsp_2_db.php'
3) 'tsp_3_db.php'
4) 'tsp_4_db.php'

The files for 'TSP_MWHC_2' can be put in the folder ' C:\xampp\htdocs\tsp_programs\TSP_EUC_2D_DATA'.

'TSP_EXPLICIT_DATA' and 'TSP_EUC_2D_DATA' folders had been created , so that less confusion will be there and the location of 'TSP_MWHC_1' and 'TSP_MWHC_2' program files will be more well known and so that the appropriate program can be selected according to whether the data is of 'EXPLICIT' type or 'EUC_2D' type is required to be processed.

If the data required to be processed is of 'EXPLICIT' type as for eg:- in the database table named 'vrts_15_po1_explicit' , then 'TSP_MWHC_1' is to be executed.

To run 'TSP_MWHC_1' , open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs/TSP_EXPLICIT_DATA' and press enter.

A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_epct.php'.

From 'tsp_1_epct.php', the execution of the program can start, by clicking on 'tsp_1_epct.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )

If the data is of 'EUC_2D' type as for eg:- in the database table named 'vrts_wi29_euc_2d' , then 'TSP_MWHC_2' is to be executed.

To run 'TSP_MWHC_2' , open a new tab in Google Chrome browser and in the URL address, type 'localhost/tsp_programs/TSP_EUC_2D_DATA' and press enter.

A listing of the php files will be shown for eg:- one of the files shown will be 'tsp_1_db.php'.

From 'tsp_1_db.php', the execution of the program can start, by clicking on 'tsp_1_db.php'.
( IMPORTANT. PLEASE NOTE. When the execution starts, please select a table from the select box containing the tables in the beginning page of the execution. )

The appropriate table has to be selected from the select box when the 'TSP_MWHC_1' program or the 'TSP_MWHC_2' program is executed.

The suffix '_explicit' or '_euc_2d' already present in the table names determine if the table data is of 'EXPLICIT' data type or of 'EUC_2D' data type.


END OF NOTE.

[varghese]

Hello to All,

I also wanted to mention a note , that for the TSPLIB example graphs given in the website 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html' , the minimum weight results of these graphs are given in the website 'https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/STSP.html'.

[varghese]

Hello to All,

I just wanted to emphasize one point which was already mentioned in the post which was posted on '24th May 2018'.

The point is that the PHP program gives solution to any graphs with below 35 vertices ( including the 'TSPLIB' examples ) within 20 minutes upto 1 and half hours on my ordinary 'TSOHIBA Satellite C640' laptop. For more than 35 vertices , a workstation computer ( such as those in research laboratories ) needs to be used to get the result for eg:- a 100 vertices graph within 1 or 2 hours.

Also please note that this PHP Program is 'not' a program 'which is used only for special cases of graphs'. This PHP Program 'is a general program used for solving for any kind of graphs' for the Travelling Salesman Problem.

In the 'List_of_tables.docx' file uploaded in the post dated '24th May 2018' , a '38' , '42' , '51' and a '100' vertices table are also included for use as test data for the program ( There are also higher number of vertices graphs also included as test data
in the 'List_of_tables.docx' file. ) while testing it on a workstation or a supercomputer.

So if a Research Scientist could test this PHP Program for a 100 vertices graph on a workstation or a supercomputer and if the PHP Program gives the correct answer within a reasonable amount of time (for eg:- within 1 or 2 hours), it will give a more strong basis for the PHP Program being a general polynomial time program for solving the Travelling Salesman Problem.

[varghese]

Hello to All,

In this post I am giving the Algorithm for the latest PHP Program ( ie:- the PHP Program which is a polynomial time program and which gives exact solutions to the Travelling Salesman Problem that I had posted on 'May 24th 2018' ).

When writing the document , the figures were not displaying correctly along with the text , so in order to finish the document as soon as possible , I put all the figures in a separate document file. So the full document which explains the Algorithm consists of two documents ie:- 'Travelling Salesman Problem Solution Algorithm 2018 Notes.docx' and 'Travelling Salesman Problem Solution Algorithm 2018 Diagrams.docx'. These two documents gives all the details about the Algorithm for solving and obtaining the exact solution for the Travelling Salesman Problem.

I have attached the documents 'Travelling Salesman Problem Solution Algorithm 2018 Notes.docx' and 'Travelling Salesman Problem Solution Algorithm 2018 Diagrams.docx' in this post.

Please kindly note that the Algorithm is a very simple algorithm and is not a complicated algorithm at all.

[varghese]

Hello to All,

I am just giving a very short description of the algorithm for the program that I had uploaded in the post dated on "24th May 2018".

The very short description of the algorithm is as follows :-

BEGINNING OF ALGORITHM

Step 1) Find an approximately minimum weight hamilton circuit as close to the exact optimal weight hamilton circuit as possible.

Step 2) Use the 2-opt procedure on the hamilton circuit obtained.

Step 3) A local minimum weight hamilton circuit is obtained.

Step 4) Collect all the edges of the graph ( ie:- the graph which contains the local minimum weight hamilton circuit. Also the edges collected contains all the edges of the graph but it does not include the edges which are present in the local minimum weight hamilton circuit of the graph ).

Step 5) From the collection of edges, take each edge one by one.

Step 6) For a single edge , put the edge in 4 positions in the local minimum weight hamilton circuit. For each position , do the 2-opt procedure on the modified hamilton circuit. After 4 hamilton circuits are obtained from the 4 positions , check the weight of each hamilton circuit with the weight of the local minimum weight hamilton circuit. If the weights are not less than the weight of the local minimum weight hamilton circuit and if the edge is the last edge from the collection of edges , then the local minimum weight hamilton circuit is the global minimum weight hamilton circuit. Then go to Step 7. But if the edge is not the last edge and if the weights are not less than the weight of the local minimum weight hamilton circuit , then go to Step 5 ( ie:- take the next edge ). But if any of the 4 hamilton circuits have a weight less than the local minimum weight hamilton circuit , then this new hamilton circuit is taken as the new approximate minimum weight hamilton circuit and then go to Step 2.

Step 7) End of process.

END OF ALGORITHM

In the more detailed algorithm notes , a modified version of the 2-opt algorithm is implemented in which there are a few more extra steps to be done. In order to make shorter notes , I have written the procedure as 2-opt procedure. Because if needed , 2-opt procedure can also be used. But in order to increase efficiency , more optimization steps can be done in the algorithm. But here in order to give a clear idea of what the main algorithm is about , I have written the notes as short as possible and 2-opt procedure is menitioned here as being used rather than the modified version of the 2-opt method.

I have also attached a short description of the algorithm named 'Short description of Algorithm.docx' along with this email which contains a little more description for explanation if the above very short description is not enough to get a basic idea of how the algorithm works.

[varghese]

Hello to All,

I am also giving a time complexity proof of the algorithm that was posted on '24th May 2018'. I have also attached the file 'TSP TIME COMPLEXITY PROOF.docx' which contains the exact copy of the details given here , since the MS Word document contains the details in more clearer text. The details is as follows :-

Travelling Salesman Problem Time Complexity Proof

First the notations are given. Then the algorithm is given , so that the time complexity calculations can be understood more easily by using the explanation of the algorithm alongside the calculations.

- Beginning of Notations -

1) n^m ::-
It means n raised to the power of m where n and m are real numbers.

2) [AWHC] ::-
It denotes the 'approximate weight hamilton circuit' which has a weight as close as possible to the optimal minimum weight.

3) [LMWHC] ::-
It denotes the local minimum weight hamilton circuit.

4) [GMWHC] ::-
It denotes the global minimum weight hamilton circuit.

5) [LMWHC_#_M] ::-
It denotes the local minimum weight hamilton circuit which is modified. For eg:- [LWMHC_2_M] means [LMWHC] having a number 2 and which is modified.

6) [RHC_#] ::-
It denotes the hamilton circuit , with the number '#' , which has been obtained after the 2-opt process has been done on the [LMWHC_#_M]. The value of '#' in both [RHC_#] and [LMWHC_#_M] both should be the same because in order to show that [RHC_#] is obtained from the corresponding [LMWHC_#_M]. The 'R' in 'RHC' means 'resultant' ie:- 'RHC' means resultant hamilton circuit.

7) ( Step m )-> ::-
It means step with value of 'm' where 'm' is a number. The number denotes the value of the step number of an algorithm.

- End of Notations -


- Beginning of TSP Algorithm -

( Step 1 )->
Find the best possible heuristic weight hamilton circuit of the graph which is as close to the exact optimal minimum weight ie:- [AWHC].

( Step 2 )->
Use the 2-opt method on [AWHC] to get [LMWHC].

( Step 3 )->
Collect all the edges of the graph in which [LMWHC] is present ( Note that the collection of the edges does not contain the edges present in the hamilton circuit of [LMWHC] ie:- the collection of the edges contain all the edges of the graph but does not include the edges which are present in [LMWHC] ).

( Step 4 )->
From the collection of edges , take each edge one by one for processing.

( Step 5 )->
Take one edge from the collection of edges.

( Step 6 )->
For this single edge , there are a total of 4 positions that the edge has to be replaced in [LMWHC]. The processing is done for each position. For eg:- taking an edge from the collection, [LMWHC] has 4 positions for this edge. So the 4 modified hamilton circuits for this edge are
[LMWHC_1_M],
[LMWHC_2_M],
[LMWHC_3_M],
[LMWHC_4_M].
For each modified hamilton circuit , do the 2-opt process on the modified hamilton circuit. A new 'resultant' hamilton circuit is obtained. For eg:- after the 2-opt process is done on [LMWHC_1_M] , the new 'resultant' hamilton circuit is [RHC_1]. So the corresponding 'resultant' hamilton circuits for the 4 modified hamilton circuits are :-
[LMWHC_1_M] => [RHC_1]
[LMWHC_2_M] => [RHC_2]
[LMWHC_3_M] => [RHC_3]
[LMWHC_4_M] => [RHC_4]
( Note:- The '=>' denotes that the right hand side hamilton circuit is obtained from the left hand side hamilton circuit after a process is carried out on the left hand side hamilton circuit. )
Now the weight of the 4 'resultant' hamilton circuits ie:- [RHC_1] , [RHC_2] , [RHC_3] and [RHC_4] should be compared with the weight of [LMWHC]. If the weights are greater than the weight of [LMWHC] , then check if the edge which was processed is the last edge. If it is the last edge, then [LMWHC] is the [GMWHC] and then go to Step 7. If the edge was not the last edge and if the weights of each of [RHC_1] , [RHC_2] , [RHC_3] and [RHC_4] are greater than the weight of [LMWHC], then goto Step 5. If any of the weights of [RHC_1] , [RHC_2] , [RHC_3] or [RHC_4] was lesser than the weight of [LMWHC] , then that hamilton circuit will be assigned to [LMWHC] ( For eg:- if [RHC_2] had lesser weight than [LMWHC] , then [RHC_2] will be assigned to [LMWHC] ie:- the new [LMWHC] is [RHC_2] ) , and then go to Step 3.

( Step 7 )->
End of process.

- End of TSP Algorithm -


- Description of Time Complexity for Worst Case -

There are 3 cases for the worst case time complexity. The step numbers mentioned are the step numbers of the TSP algorithm which is given above.

- Beginning of Case 1 -

In Case 1 , assume that in the beginning of the execution of the algorithm , the [LMWHC] which is obtained in Step 2 is itself the [GMWHC]. And then it needs to be checked if [LMWHC] is indeed the [GMWHC]. So for Case 1 , the steps of the algorithm are shown below.

In Step 2 , time complexity is O(n^2).
In Step 3 , all the edges of the graph(ie:- including the edges of the hamilton circuit present in the graph is taken). So the number of edges taken are 'n*(n-1)/2'.
In Step 6 , each edge has to be placed in 4 positions to obtain 4 modified hamilton circuits. So for ' n*(n-1)/2' edges , the total hamilton circuits obtained is '4*[n*(n-1)/2]' hamilton circuits. On each of the hamilton circuits , the 2-opt process has to be done.
So total time complexity is
O(2-opt method in Step 2) + 4 * [n*(n-1)/2] * O(2-opt method)
ie:- n^2 + 4 * [n*(n-1)/2] * O(2-opt method)
ie:- n^2 + 4 * [n*(n-1)/2] * O(n^2)
ie:- n^2 + 4 * [n*(n-1)/2] * n^2
ie:- O(n^4).

So time complexity for Case 1 is O(n^4).

- End of Case 1 -


- Beginning of Case 2 -

In Case 2 , assume that in the beginning of the execution of the algorithm , the [LMWHC] which is obtained in Step 2 is very near the the optimal weight hamilton circuit (ie:- the [GMWHC]) , so that the number of times the execution goes from Step 6 to Step 3 may be a small number say for eg:- 5 times . So here also the time complexity remains the same. So Case 2 , the steps of the algorithm are shown below.

In Step 2 , time complexity is O(n^2).
In Step 3 , all the edges of the graph(ie:- including the edges of the hamilton circuit present in the graph is taken). So the number of edges taken are 'n*(n-1)/2'.
In Step 6 , each edge has to be placed in 4 positions to obtain 4 modified hamilton circuits. So for ' n*(n-1)/2' edges , the total hamilton circuits obtained is '4*[n*(n-1)/2]' hamilton circuits. On each of the hamilton circuits , the 2-opt process has to be done.
So time complexity for the loop of going from Step 6 to Step 3 for eg:- 5 times is :-
5 * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- 20 * [(n^2 - n)/2] * n^2

So total time complexity is
O(2-opt method in Step 2) + 5 * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- n^2 + 5 * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- n^2 + 5 * ( 4 * [n*(n-1)/2] * O(n^2) )
ie:- n^2 + 20 * [n*(n-1)/2] * n^2
ie:- n^2 + O(n^4)
ie:- O(n^4)

So time complexity for Case 2 is O(n^4).

- End of Case 2 -


- Beginning of Case 3 -

In Case 3 , assume that in the beginning of the execution of the algorithm , the weight of [LMWHC] which is obtained in Step 2 is very far from the the weight of the optimal weight hamilton circuit (ie:- the [GMWHC]) , so that the number of times the execution goes from Step 6 to Step 3 may be a large number say for eg:- the number of edges in the graph ie:- [n*(n-1)/2] . So for Case 3 , the steps of the algorithm are shown below.

In Step 2 , time complexity is O(n^2).
In Step 3 , all the edges of the graph(ie:- including the edges of the hamilton circuit present in the graph is taken). So the number of edges taken are 'n*(n-1)/2'.
In Step 6 , each edge has to be placed in 4 positions to obtain 4 modified hamilton circuits. So for ' n*(n-1)/2' edges , the total hamilton circuits obtained is '4*[n*(n-1)/2]' hamilton circuits. On each of the hamilton circuits , the 2-opt process has to be done.
So time complexity for the loop of going from Step 6 to Step 3 for [n*(n-1)/2] times is :-
[n*(n-1)/2] * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- [n*(n-1)/2] * 4 * [(n^2 - n)/2] * n^2

So total time complexity is
O(2-opt method in Step 2) + [n*(n-1)/2] * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- n^2 + [n*(n-1)/2] * ( 4 * [n*(n-1)/2] * O(2-opt method) )
ie:- n^2 + [n*(n-1)/2] * ( 4 * [n*(n-1)/2] * O(n^2) )
ie:- n^2 + [n*(n-1)/2] * 4 * [n*(n-1)/2] * n^2
ie:- n^2 + O(n^6)
ie:- O(n^6)

So time complexity for Case 3 is O(n^6).

- End of Case 3 -

- CONCLUSION -
The conclusion is that it can be observed that if the total weight of the approximate heuristic minimum weight hamilton circuit which is got at the beginning of the execution of the algorithm , has a value which is very near to the weight of the global optimal minimum weight hamilton circuit , then the worst case time complexity of the algorithm is O(n^4).

[varghese]

I had developed a new PHP Program in January 2021.

I am writing down the results that I had obtained from the PHP Program of January 2021.

I have divided the result details into 5 sections , in order to make the notes as simple and easier to read as much as possible and to avoid notations as much as possible.

SECTION 1

This section gives the website addresses of where the examples are found.

1) 'http://www.math.uwaterloo.ca/tsp/world/countries.html'
dj38 -> Djibouti 38 cities.
wi29 -> Western Sahara 29 cities.


2) 'https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html'
P01 -> A set of 15 cities.

3) 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html'

[ Note :- 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/stsp-sol.html' gives the answers to the problems given in 'http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html'. ]

att48
bayg29
bays29
berlin52
burma14
dantzig42
eil51
eil76
eil101
fri26
gr17
gr21
gr24
kroa100
krob100
kroc100
krod100
pr76
st70
ts225
ulysses16
ulysses22

5) 'http://www.math.uwaterloo.ca/tsp/vlsi/index.html'

XQF131
XQG237
PBK411


SECTION 2

This section gives the optimum minimum weights of the examples as given in the websites. The weight of each example is given the symbol 'W_1'. The weight is given after the colon ie:- after ':'.

For eg:- W_1 of dj38 is 6656.

dj38 : 6656
wi29 : 27603
P01 : 291
att48 : 10628
bayg29 : 1610
bays29 : 2020
berlin52 : 7542
burma14 : 3323
dantzig42 : 699
eil51 : 426
eil76 : 538
eil101 : 629
fri26 : 937
gr17 : 2085
gr21 : 2707
gr24 : 1272
kroa100 : 21282
krob100 : 22141
kroc100 : 20749
krod100 : 21294
pr76 : 108159
st70 : 675
ts225 : 126643
ulysses16 : 6859
ulysses22 : 7013
XQF131 : 564
XQG237 : 1019
PBK411 : 1343


SECTION 3

This section gives the weights of the examples as given by the PHP Program. This weight is denoted by the symbol 'W_2'. The weight is given after the colon ie:- after ':'.

For eg:- W_2 of dj38 is 6656.

dj38 : 6656
wi29 : 27603
P01 : 291
att48 : 10628
bayg29 : 1610
bays29 : 2020
berlin52 : 7542
burma14 : 3323
dantzig42 : 699
eil51 : 426
eil76 : 538
eil101 : 635
fri26 : 937
gr17 : 2085
gr21 : 2707
gr24 : 1272
kroa100 : 21282
krob100 : 22141
kroc100 : 20749
krod100 : 21294
pr76 : 108159
st70 : 677
ts225 : 127438
ulysses16 : Same minimum route as given in website.
ulysses22 : Same minimum route as given in website.
XQF131 : 565
XQG237 : 1029
PBK411 : 1468


SECTION 4

This section gives the time taken by the PHP Program to obtain the hamilton circuit weight. The time format is 'T[h : m]' where 'T[]' denotes that the value is time. 'h' means number in hours and 'm' means the time in minutes.
The value of time is given after the colon ie:- after ':'.

For eg:- time taken to get the result of dj38 from the program is T[0:0] ie:- 0 hours and 0 minutes.

dj38 : T[0:0]
wi29 : T[0:0]
P01 : T[0:0]
att48 : T[0:2]
bayg29 : T[0:0]
bays29 : T[0:0]
berlin52 : T[0:2]
burma14 : T[0:0]
dantzig42 : T[0:0]
eil51 : T[0:3]
eil76 : T[0:9]
eil101 : T[0:15]
fri26 : T[0:0]
gr17 : T[0:0]
gr21 : T[0:0]
gr24 : T[0:0]
kroa100 : T[0:9]
krob100 : T[0:12]
kroc100 : T[0:7]
krod100 : T[0:16]
pr76 : T[0:6]
st70 : T[0:6]
ts225 : T[0:14]
ulysses16 : T[0:0]
ulysses22 : T[0:0]
XQF131 : T[0:21]
XQG237 : T[0:22]
PBK411 : T[0:52]


SECTION 5

This section gives the difference in weights between the weight obtained by the PHP Program and the optimum weight as given in the website. The difference in value is denoted by the symbol 'DF'. The value of 'DF' is :-
DF = W_2 - W_1

The value of DF is given after the colon ie:- after ':'.

For eg:- DF of dj38 is W_2 - W_1 = 6656 - 6656 = 0.

dj38 : 0
wi29 : 0
P01 : 0
att48 : 0
bayg29 : 0
bays29 : 0
berlin52 : 0
burma14 : 0
dantzig42 : 0
eil51 : 0
eil76 : 0
eil101 : 6
fri26 : 0
gr17 : 0
gr21 : 0
gr24 : 0
kroa100 : 0
krob100 : 0
kroc100 : 0
krod100 : 0
pr76 : 0
st70 : 2
ts225 : 795
ulysses16 : 0
ulysses22 : 0
XQF131 : 1
XQG237 : 10
PBK411 : 125