No description available.

Thesis (doctoral)--Ludwig-Maximilians-Universität München, 2003. / Includes bibliographical references.

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.

Epilepsy -- the condition of recurrent, unprovoked seizures -- manifests in brain voltage activity with characteristic spatio-temporal patterns. One of the patterns typically observed during a seizure is a traveling wave. To characterize these waves, we analyze high-density local field potential (LFP) data recorded in vivo from human cortex during a seizure from three patients. We show that traveling wave patterns emerge in the LFP with consistent quantitative features. Using a mean-field approach we model the neuronal population activity observed in the LFP and obtain explicit traveling wave solutions for this model. We then employ the LFP data to constrain the model and obtain parameter configurations that support traveling wave solutions with features consistent with the observed LFP waves. In particular, our model formulation is able to capture the "reverberation" of the activity following the traveling wave that was found in the clinical data. We obtain biologically reasonable parameter estimates for two important features: the timescales of the model and the extent of the connectivity. In this way, we link the observed LFP waves during seizure to proposed biological mechanisms. We also study the linear stability of the traveling wave solutions by constructing an Evans function. We find for some parameters the existence of two waves: one wave is slow and narrow whereas the other wave is fast and wide. Moreover, the fast and wide wave has speed and width consistent with the observed LFP waves. We numerically analyze the Evans function to determine stability (instability) of the fast (slow) wave.

In this thesis, we study nonlinear partial differential equations arising from image processing and cheomotaxis. We analyze mathematical models in conservative form from the perspective of traveling wave solutions. We show the existence and the stability of traveling wave solutions in the models, which helps to understand the behaviors of solutions in the models. The thesis largely consists of two parts: (1) We develop stability analysis for a traveling wave solution of a nonlinear conservation law arising from image processing. To be specific, we prove that if the initial perturbation between a solution and a traveling wave solution to the problem is small, the solution converges to the traveling wave solution.To show this, we construct a weight function in establishing energy estimates to overcome difficulties caused by the absence of the convexity of a flux of the conservation law. (2) We develop dynamical systems theory to study traveling wave solutions in a chemotaxis model. A traveling wave solution to the model in a partial differential equation is a heteroclinic/homoclinic orbit to the model in an ordinary differential equation. Thus, we investigate the existence and non-existence of a heteroclinic/homoclinic orbit in certain ranges of parameters in the model by applying dynamical systems theory.

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.

We analyze a pair of nonlinear PDEs describing viscoelastic fluid flow in one dimension. We give a summary of the physical derivation and nondimensionlize the PDE system. Based on the boundary conditions and parameters, we are able to classify three different categories of traveling wave solutions, consistent with the results in [?]. We extend this work by analyzing the stability of the traveling waves. We thoroughly describe the numerical schemes and software program, VISCO, that were designed specifically to analyze the model we study in this paper. Our simulations lead us to conjecture that the traveling wave solutions found in [?] are globally stable for all sets of initial conditions with the appropriate asymptotic boundary conditions. We are able give some analytical evidence in support of this hypothesis but are unsuccessful in providing a complete proof.