Thesis (M.Phil.)--University of Hong Kong, 2003. / Includes bibliographical references (leaves 49-50) Also available in print.

M.Sc. (Computer Science) / The STSP (symmetric travelling salesman problem) involves finding the cheapest tour through a number of cities. It is a difficult problem and until recently algorithms for the TSP could not find the optimal tour in a reasonable time if the number of cities exceeded 100. In 1987 Padberg and Rinaldi published their computational experience with a new branch-and-cut algorithm. They were able to solve problems with up to 2392 cities on a CDC CYBER 205 supercomputer. Padberg and Rinaldi used a standard LP (linear programming) solver in their implementation of the branch-and-cut algorithm. The algorithm first solves the continuous 2-matching problem (RMP2) using the LP solver. It then repeatedly identifies constraints of the TSP which are not satisfied by the current RMP2-solution and solve RMP2 with the identified TSP-constraints as side constraints. However, RMP2 is a linear programming problem with a very special structure which we exploited in an implementation of the primal simplex algorithm for RMP2. Our computational experience with this implementation indicates that it is almost 400 times faster than a commercial LP solver on problems with 200 cities. We developed an implementation of the dual simplex algorithm which exploits the special structure of both RMP2 and the side constraints identified in the branch-and-cut algorithm. An existing set of side constraints for solving a 48-eity problem was used to test our implementation of the dual simplex algorithm. We implemented the procedure described by Padberg & Rinaldi to identify subtour elimination side constraints (one type of side constraint) for the 48-eity problem. Our implementation of the identification procedure was then used in conjunction with our implementation of the dual simplex algorithm. The maximum flow problem has to be solved in the algorithm for identification of subtour elimination constraints. We implemented the Sleator-Tarjan algorithm for this purpose.

M.Sc. (Computer Science) / The Travelling Salesman Problem (TSP) comprises the following: A salesman is required, by definition of his job description, to visit a set of cities. He leaves from a base city, visits each of the other cities exactly once and then returns to his base city. In travelling between city pairs, he incurs certain costs. It is a travelling salesman's constant endeavour, therefore, to find the cheapest route. A combinatorial optimisation problem involves the selection of the best alternative from a finite set of alternatives. The TSP is one of the best known and most studied combinatorial optimisation problems. At present, the branch-and-cut algorithm of Padberg and Rinaldi is the most successful algorithm for solving large-scale instances of the TSP. Padberg and Rinaldi used a general LP solver to solve the subproblem P(L, F0 , F1 ), where L is a set of side constraints, F0 is the set of variables fixed at 0 and F1 is the set of variables fixed at 1. As noted by Smith and Leenen, however, this subproblem has a special structure that was exploited by them to solve the subproblem more efficiently. In this dissertation, we would like to present improvements on Leenen's contribution. For this purpose, we compared our results with those of a commercial LP solver. It was found that our program on average executed in half the time of that of the commercial LP solver. The problem P(L, F0 , F1;) has to be solved many times in the branch-and-cut algorithm before a solution to the TSP is obtained. For large-scale instances of the TSP, a substantial portion of the execution time of the entire branch-and-cut algorithm is spent in the linearprogram optimiser. The branch-and-cut algorithm could,• therefore, be potentially more efficient if the special structure were utilised. We constructed a full implementation of the branch-and-cut algorithm, utilising the special structure. We did not, however, implement all the refinements discussed by Padberg and Rinaldi. Padberg and Rinaldi used four classes of TSP constraints: subtour elimination, 2-matching, comb and clique-tree inequalities. Owing to time constraints and the complexity of identifying the other classes of constraints, we decided to implement subtour elimination constraints only. We subsequently compared our results with those of Padberg and Rinaldi, and realised that we totally underestimated the importance of using more classes of constraints. Our search trees had become extremely huge. We realised, therefore, that more classes of constraints were essential for solving large instances of the TSP. Even though numerical errors still posed a problem, they might disappear if the size of the search tree were reduced to that obtained by Padberg and Rinaldi.

Microaggregation is a method of statistical disclosure control that attempts to reconcile the need to release information to researchers with the need to protect privacy of individual records in a dataset. Under microaggregation, records are divided into groups containing at least k members. Actual data values of the members are replaced by the mean value of the group, such that each record in the group is indistinguishable from at least k-1 other records. The goal of microaggregation is to create groups of similar records such that information loss is minimized, where information loss is the sum squared deviation between the actual data values and the group means. Optimal multivariate microaggregation is an NP-hard problem, and heuristics have been proposed to generate solutions in reasonable running time. New heuristics are desirable for either producing groups with lower information loss, or for producing groups with similar information loss but lower computational complexity. Some of the best performing existing microaggregation heuristics are based on record ordering, since it has been proven that for a given ordering of records, the optimal set of groups for that particular ordering can be efficiently computed. This dissertation improves on previous heuristics that order records in a dataset and subsequently use this record ordering to generate high quality microaggregated k- partitions. This was accomplished by using heuristics from the traveling salesman problem (TSP) literature in order to more effectively order the records. In particular, two tour construction heuristics - the Greedy heuristic and the Quick Boruvka heuristic - that are comparable in complexity to extant microaggregation methods were investigated. Next, three tour improvement heuristics - 2-opt, 3-opt, and Lin-Kernighan - were used on the tours constructed to investigate whether further reduction in information loss could be achieved. The tour improvement heuristics - particularly the 3-opt and Lin-Kernighan heuristics - provided microaggregation solutions better than the best previous known solutions across several datasets and values of k.

Genetic algorithms are an evolutionary technique that use crossover and mutation operators to solve optimization problems using a survival of the fittest idea. They have been used successfully in a variety of different problems, including the traveling salesman problem. In the traveling salesman problem we wish to find a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling salesman problem is NP-hard but has many real world applications so a good solution would be useful. Many different crossover and mutation operators have been devised for the traveling salesman problem and each give different results. We compare these results and find that operators that use heuristic information or a matrix representation of the graph give the best results.

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

published_or_final_version / Mathematics / Master / Master of Philosophy

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

No description available.

Thesis (M. Phil.)--University of Hong Kong, 2000. / Includes bibliographical references (leaves 112-117).