No description available.

Mixed integer programming (MIP) provides an important modeling and decision support tool for a wide variety of real-life problems. Unfortunately, practical MIPs are large-scale in size and pose serious difficulties to the available solution methodology and software. / This thesis presents a novel solution approach for large-scale mixed integer programming that integrates three bodies of research: interior point methods, decomposition techniques and branch-and-bound approaches. The combination of decomposition concepts and branch-and-bound is commonly known as branch-and-price, while the integration of decomposition concepts and interior point methods lead to the analytic centre cutting plane method (ACCPM). Unfortunately, the use of interior point methods within branch-and-bound methods could not compete with simplex based branch-and-bound due to the inability of "warm" starting. / The motivation for this study stems from the success of branch-and-price and ACCPM in solving integer and non-differentiable optimization problems respectively and the quest for a method that efficiently integrates interior-point methods and branch-and-bound. / The proposed approach is called an Interior Point Branch-and-Price method (IP-B&P) and works as follows. First, a problem's structure is exploited using Lagrangean relaxation. Second, the resulting master problem is solved using ACCPM. Finally, the overall approach is incorporated within a branch-and-bound scheme. The resulting method is more than the combination of three different techniques. It addresses and fixes complications that arise as a result of this integration. This includes the restarting of the interior-point methods, the branching rule and the exploitation of past information as a warm start. / In the first part of the thesis, we give the details of the interior-point branch-and-price method. We start by providing, discussing and implementing new ideas within ACCPM, then detail the IP-B&P method and its different components. To show the practical applicability of IP-B&P, we use the method as a basis for a new solution methodology for the production-distribution system design (PDSD) problem in supply chain management. In this second part of the thesis, we describe a two-level Lagrangean relaxation heuristic for the PDSD. The numerical results show the superiority of the method in providing the optimal solution for most of the problems attempted.

We propose an analytic center cutting plane algorithm for semidefinite programming (SDP). Reformulation of the dual problem of SDP into an eigenvalue optimization, when the trace of any feasible primal matrix is a positive constant, is well known. We transform the eigenvalue optimization problem into a convex feasibility problem. The problem of interest seeks a feasible point in a bounded convex set, which contains a full dimensional ball with &egr;(<1) radius and is contained in a compact convex set described by matrix inequalities, known as the set of localization. At each iteration, an approximate analytic center of the set of localization is computed. If this point is not in the solution set, an oracle is called to return a p-dimensional semidefinite cut. The set of localization then, is updated by adding the semidefinite cut through the center. We prove that the analytic center is recovered after adding a p-dimensional semidefinite cut in O(plog(p + 1)) damped Newton's iteration and that the ACCPM with semidefinite cuts is a fully polynomial approximation scheme. We report the numerical result of our algorithm when applied to the semidefinite relaxation of the Max-Cut problem.

No description available.

No description available.

Recongurable computing technology has progressed to a stage where it is now possible to achieve orders of magnitude performance and power eciency gains over conventional computer architectures for a subset of high performance computing applications. In this thesis, we investigate the potential of recongurable computers to accelerate genomic sequence alignment specically for genome sequencing applications. We present a highly optimized implementation of a parallel sequence alignment algorithm for the Berkeley Emulation Engine (BEE2) recongurable computer, allowing a single BEE2 to align simultaneously hundreds of sequences. For each recongurable processor (FPGA), we demonstrate a 61X speedup versus a state-of-the-art implementation on a modern conventional CPU core, and a 56X improvement in performance-per-Watt. We also show that our implementation is highly scalable and we provide performance results from a cluster implementation using 32 FPGAs. We conclude that reconfigurable computers provide an excellent platform on which to run sequence alignment, and that clusters of recongurable computers will be able to cope far more easily with the vast quantities of data produced by new ultra-high-throughput sequencers.

There exist several challenges in supporting mobile applications. For example, creating a separate target application for each device type, leaving developers with a huge maintenance chore. Most desktop applications run on largely homogenous hardware so instead of writing the same code over and over again, developers only need to write modules to implement a particular need. This is because even though there are differences in PC hardware configurations, the same desktop application will work fine on any hardware as the operating system provides an abstract layer. This is the way mobile applications are expected to work. However, this has been divided into dozens of ill-assorted versions. Java mobile applications developers spend more time rewriting code to run on different versions of mobile devices more than they do actually creating application in the first place. This is an intolerable burden for small mobile developers, and it stifles mobile software innovation overall. Mobile devices differ in a variety of attributes, such as screen size, colour depth and the optional hardware devices they support such as cameras, GPS etc. The differences often require special code or project settings for successful deployment for each device a developer is targeting but this creates a huge logistical overhead. One potential solution that is shipped with NetBeans IDE is to add a new configuration for each device, modify the project properties, add some pre-processing code, then build and deploy the application. In most cases, one configuration for each distribution of the Java Archive (JAR) one plans to build for the project is created. For example, if a developer is planning to support three different screen sizes using two sets of vendor specific APIs, one needs to create six configurations. This reduces the performance of the application drastically and increases the size at the same time. This is not acceptable for mobile devices where memory size and processor performance are limited. The goal of this research work is to support mobile application development through a Java IDE (the NetBeans IDE in this case). Therefore, our approach will be to modify the NetBeans IDE to better address the difficulty that was mentioned above – namely targeting applications for different platforms. Our solution is to integrate another type of a preprocessor into the NetBeans IDE that will help alleviate the problems of the existing tool. Our approach is to directly implement this inside the NetBeans IDE to further support mobile application development with the NetBeans IDE.

Clusters of commodity, "off the shelf" workstations have given developers and users access to scalable and affordable computing resources. However, unlike large, symmetric multi-processing machines, these clusters have an up front cost in complexity, both for the developer and the user. Existing software frameworks have attempted to mitigate this complexity with varied success. In most frameworks, the user is forgotten and left to deal with an unwieldy application. This thesis presents the design, development and testing of a new C++ computer programming library, Scopira Agents Library (SAL). SAL is a message passing interface and implementation suitable for building parallel applications, with a focus on developer ease of use and user application deployment specification. The target developers and users of such a solution would be those who prefer an easy to develop library, with simpler deployment and application integration options with acceptable sacrifices to performance and scalability. The novelty of this parallel programming library is that it is more user-friendly than other existing libraries. This novelty has two major facets: (i) programmer-usability and productivity and (ii) application integration. Together, they permit a wider range of programmers to utilize parallel programming in a wider range of new and existing applications. This goal, user-friendliness, is rare among current parallel programming libraries. The result of the novelty is that parallel programming can be embedded into more applications, especially desktop applications. The user base and use cases for parallel applications can be increased, resulting in more efficient use of resources in a variety of applications. With increased efficiency, work can be performed in less time and larger problems can be tackled.

No description available.

No description available.