Wong, Mei Ting. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 115-120). / Abstracts in English and Chinese. / Chapter 1. --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- Our Contributions --- p.4 / Chapter 1.3 --- Framework of Shelf Space Allocation Problem --- p.4 / Chapter 1.4 --- Organization --- p.6 / Chapter 2. --- Literature Review --- p.7 / Chapter 2.1 --- Introduction --- p.7 / Chapter 2.2 --- Commercial Approaches --- p.7 / Chapter 2.3 --- Experimental Approaches --- p.8 / Chapter 2.4 --- Optimization Approaches --- p.11 / Chapter 2.4.1 --- Exact Approaches --- p.11 / Chapter 2.4.2 --- Heuristics Approaches --- p.16 / Chapter 2.5 --- Summary --- p.19 / Chapter 3. --- Overview of Shelf Space Allocation Problem --- p.21 / Chapter 3.1 --- Introduction --- p.21 / Chapter 3.2 --- Problem description --- p.22 / Chapter 3.2.1 --- Mathematical Model --- p.24 / Chapter 3.2.1.1 --- Notations --- p.25 / Chapter 3.2.1.2 --- Model --- p.25 / Chapter 3.2.1.3 --- Assumption --- p.26 / Chapter 3.2.1.4 --- Notations of final model --- p.27 / Chapter 3.2.1.5 --- Final model --- p.27 / Chapter 3.3 --- Original Heuristic --- p.28 / Chapter 3.3.1 --- Yang (2001) Method --- p.28 / Chapter 3.3.2 --- Remarks on Original Heuristic --- p.29 / Chapter 3.4 --- Original Heuristic with Yang's Adjustment --- p.30 / Chapter 3.4.1 --- Remarks on Yang's Adjustment --- p.32 / Chapter 3.5 --- New Neighborhood Movements --- p.33 / Chapter 3.5.1 --- New Adjustment Phase --- p.33 / Chapter 3.6 --- Network Flow Model --- p.35 / Chapter 3.6.1 --- ULSSAP --- p.35 / Chapter 3.6.2 --- Transforming shelf space allocation problem (SSAP) --- p.38 / Chapter 3.7 --- Tabu Search --- p.41 / Chapter 3.7.1 --- Tabu Search Algorithm --- p.42 / Chapter 3.7.1.1 --- Neighborhood search moves --- p.42 / Chapter 3.7.1.2 --- Candidate list strategy --- p.45 / Chapter 3.7.1.3 --- Tabu list --- p.46 / Chapter 3.7.1.4 --- Aspiration criteria.........................................: --- p.47 / Chapter 3.7.1.5 --- Intensification and Diversification --- p.48 / Chapter 3.7.1.6 --- Stopping criterion --- p.49 / Chapter 3.7.1.7 --- Probabilistic choice --- p.50 / Chapter 3.7.2 --- General Process of Tabu Search --- p.51 / Chapter 3.7.3 --- Application of Tabu Search to SSAP --- p.54 / Chapter 3.7.4 --- Analysis of Tabu Search --- p.58 / Chapter 4. --- Tabu Search with Path Relinking --- p.60 / Chapter 4.1 --- Introduction --- p.60 / Chapter 4.2 --- Foundations of path relinking --- p.62 / Chapter 4.3 --- Path Relinking Template --- p.65 / Chapter 4.4 --- Identification of Reference set --- p.69 / Chapter 4.5 --- Choosing initial and guiding solution --- p.73 / Chapter 4.6 --- Neighborhood structure --- p.74 / Chapter 4.7 --- Moving along paths --- p.81 / Chapter 4.8 --- Application of Tabu Search with Path Relinking --- p.87 / Chapter 4.9 --- Conclusion --- p.90 / Chapter 5. --- Computational Studies --- p.92 / Chapter 5.1 --- Introduction --- p.92 / Chapter 5.2 --- General Parameter Setting --- p.92 / Chapter 5.3 --- Parameter values for Tabu search --- p.94 / Chapter 5.4 --- Sensitivity test for Tabu search with Path Relinking --- p.95 / Chapter 5.4.1 --- Reference Set Strategies and Initial and Guiding Solution Criteria --- p.96 / Chapter 5.4.2 --- Frequency of Path Relinking --- p.99 / Chapter 5.4.3 --- Size of reference set --- p.101 / Chapter 5.4.4 --- Comparison with Tabu Search --- p.102 / Chapter 5.5 --- Comparison with other heuristics --- p.105 / Chapter 5.6 --- Conclusion --- p.109 / Chapter 6. --- Conclusion --- p.111 / Chapter 6.1 --- Summary of achievements --- p.112 / Chapter 6.2 --- Future Works --- p.113 / Bibliography --- p.115

Most applications spend a significant amount of time in the iterative parts of a computation. They typically iterate over the same set of operations with different values. These values either depend on inputs or values calculated in previous iterations. While loops capture some iterative behavior, in many cases such a behavior is spread over whole program sometimes through recursion. Understanding iterative behavior of the computation can be very useful to fine-tune it. In this thesis, we present a profiling based framework to understand and improve performance of iterative computation. We capture the state of iterations in two aspects 1) Algorithmic State 2) Program State. We demonstrate the applicability of our framework for capturing algorithmic state by applying it to the SAT Solvers and program state by applying it to a variety of benchmarks exhibiting completely parallelizable loops. Further, we show that such a performance characterization can be successfully used to improve the performance of the underlying application. Many high performance combinatorial optimization applications involve SAT solving. A variety of SAT solvers have been developed that employ different data structures and different propagation methods for converging on a fixed point for generating a satisfiable solution. The performance debugging and tuning of SAT solvers to a given domain is an important problem encountered in practice. Unfortunately not much work has been done to quantify the iterative efficiency of SAT solvers. In this work, we develop quantifiable measures for calculating convergence efficiency of SAT solvers. Here, we capture the Algorithmic state of the application by tracking the assignment of variables for each iteration. A compact representation of profile data is developed to track the rate of progress and convergence. The novelty of this approach is that it is independent of the specific strategies used in individual solvers, yet it gives key insights into the "progress" and "convergence behavior" of the solver in terms of a specific implementation at hand. An analysis tool is written to interpret the profile data and extract values of the following metrics such as: average convergence rate, efficiency of iteration and variable stabilization. Finally, using this system we produce a study of 4 well known SAT solvers to compare their iterative efficiency using random as well as industrial benchmarks. Using the framework, iterative inefficiencies that lead to slow convergence are identified. We also show how to fine-tune the solvers by adapting the key steps. We also show that the similar profile data representation can be easily applied to loops, in general, to capture their program state. One of the key attributes of the program state inside loops is their branch behavior. We demonstrate the applicability of the framework by profiling completely parallelizable loops (no cross-iteration dependence) and by storing the branching behavior of each iteration. The branch behavior across a group of iterations is important in devising the thread warps from parallel loops for efficient execution on GPUs. We show how some loops can be effectively parallelized on GPUs using this information.

Otimização estrutural é uma área relativamente nova que vem sendo cada vez mais explorada. Existem muitos métodos clássicos, e outros mais recentes vem surgindo para disputar em eficiência, confiabilidade e rapidez na obtenção de um resultado ótimo. Os algoritmos são classificados em algoritmos determinísticos, que utilizam a informação do gradiente, ou seja, usam os valores das funções e suas derivadas, e os meta-heurísticos, algoritmos de otimização aleatórios que são métodos probabilísticos não baseados em gradiente, ou seja, usam somente a avaliação da função objetivo. São apresentados dois algoritmos meta-heurísticos relativamente recentes: o Harmony Search, baseado na improvisação musical em busca da harmonia perfeita, e o Firefly Algorithm, que é inspirado no comportamento da luz dos vagalumes. Vários exemplos clássicos de treliças 2-D e 3-D considerando otimização paramétrica e de forma, com restrições de tensão, deslocamento, flambagem e frequência natural, são apresentados para demonstrar a eficiência dos métodos. Os resultados são comparados aos de outros autores usando diferentes métodos encontrados na literatura. Os resultados indicam que os algoritmos de otimização estudados neste trabalho são melhores ou tão eficientes quanto os demais. Por fim, os métodos são aplicados à estrutura de um projeto de engenharia adaptado. / Structural optimization is a relatively new area that has been increasingly exploited. There are many classical methods, and newer are emerging to compete on efficiency, reliability and speed in obtaining an optimal result. The algorithms are classified into deterministic algorithms, which use the gradient information, i.e., use the values of the functions and their derivatives, and meta-heuristic algorithms, random optimization methods which are probabilistic methods not based on gradient, i.e., they use only objective function evaluation. Two relatively recent meta-heuristics algorithms are presented, Harmony Search, based on musical improvisation in search of the perfect harmony, and Firefly Algorithm, which is inspired by the behavior of the light of fireflies. Several benchmarks of 2-D and 3-D trusses considering size and shape optimization, with stress, displacement, buckling and natural frequency constraints, are presented to demonstrate the effectiveness of the methods. The results are compared to the others authors using different methods found in the literature. The results indicate that optimization algorithms studied in this work are better than or as efficient as others. Finally, the methods are applied to the structure of an adapted engineering design.

Chen, Jiayi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (p. 86-94). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Introduction --- p.1 / Chapter 1.1 --- Introduction to the Capacitated Lot Sizing (CLS )problem --- p.1 / Chapter 1.2 --- Our contributions --- p.2 / Chapter 1.3 --- Organization of the thesis --- p.4 / Literature Review --- p.5 / Chapter 2.1 --- Research in CLS problem --- p.5 / Chapter 2.1.1 --- Reviews in CLS problems --- p.8 / Chapter 2.1.2 --- Approaches and methods to solve the traditional CLS problems --- p.9 / Chapter 2.1.3 --- Research on Fixed-Charge-Transportation-typed models for CLS problems --- p.13 / Chapter 2.2 --- Research in Genetic Algorithm (GA) --- p.15 / Chapter 2.3 --- Conclusion --- p.17 / Problem Description and Formulation --- p.18 / Chapter 3.1 --- The formulation --- p.18 / Chapter 3.2 --- Comparison with the traditional formulation --- p.24 / Chapter 3.3 --- Conclusion --- p.28 / Description of the Heuristic --- p.29 / Chapter 4.1 --- Initialization --- p.32 / Chapter 4.1.1 --- Setup string generation --- p.32 / Chapter 4.1.2 --- Transportation problem --- p.35 / Chapter 4.1.3 --- Consistency test --- p.47 / Chapter 4.2 --- Selection --- p.50 / Chapter 4.3 --- Crossover --- p.50 / Chapter 4.4 --- Mutation --- p.52 / Chapter 4.5 --- Evaluation --- p.53 / Chapter 4.6 --- Termination --- p.54 / Chapter 4.7 --- Conclusion --- p.54 / Design of Experiments and Computational Results --- p.56 / Chapter 5.1 --- Design of experiments --- p.57 / Chapter 5.2 --- Discussion of lower bound procedures --- p.63 / Chapter 5.3 --- Computational results --- p.65 / Chapter 5.3.1 --- CLS problems with setup times --- p.65 / Chapter 5.3.2 --- CLS problems without setup times --- p.77 / Chapter 5.4 --- Conclusion --- p.82 / Conclusion --- p.83 / Bibliography --- p.86

Many models exist in the aerospace industry that attempt to replicate the National Airspace System (NAS). The complexity of the NAS makes it a system that can be modeled in a variety of ways. While some NAS models are very detailed and take many factors into account, runtime of these simulations can be on the magnitude of hours (to simulate a single day). Other models forgo details in order to decrease the runtime of their simulation. Most models are capable of simulating a 24 hour period in the NAS. An analysis of an entire year would mean running the simulation for every day in the year, which would result in a long run time. The following thesis work presents a tool that is capable of giving the user a day that can be used in a simulation and will produce results similar to simulating the entire year. Taking in parameters chosen by the user, the tool outputs a single day, multiple days, or a composite day (based on percentages of days). Statistical methods were then used to compare each day to the overall year. On top of finding a single representative day, the ability to find a composite day was added. After implementing a brute force search technique to find the composite day, the long runtime was deemed inconvenient for the user. To solve this problem, a heuristic search method was created that would search the solution space in a short time and still output a composite day that represented the year. With a short runtime, the user would be able to run the program multiple times. Once the heuristic method was implemented, it was found that it performed well enough to make it an option for the user to choose. The final version of this tool was used to find a representative day and the result was used in comparison with output data from a NAS simulation model. Because the tool found the representative day based on historical data, it could be used to validate the effectiveness of the simulation model. The following thesis will go into detail about how this tool, the Representative Day Finder, was created.

Electric propulsion has recently become a viable technology for spacecraft, enabling shorter flight times, fewer required planetary gravity assists, larger payloads, and/or smaller launch vehicles. With the maturation of this technology, however, comes a new set of challenges in the area of trajectory design. Because low-thrust trajectory optimization has historically required long run-times and significant user-manipulation, mission design has relied on expert-based knowledge for selecting departure and arrival dates, times of flight, and/or target bodies and gravitational swing-bys. These choices are generally based on known configurations that have worked well in previous analyses or simply on trial and error. At the conceptual design level, however, the ability to explore the full extent of the design space is imperative to locating the best solutions in terms of mass and/or flight times. Beginning in 2005, the Global Trajectory Optimization Competition posed a series of difficult mission design problems, all requiring low-thrust propulsion and visiting one or more asteroids. These problems all had large ranges on the continuous variables - launch date, time of flight, and asteroid stay times (when applicable) - as well as being characterized by millions or even billions of possible asteroid sequences. Even with recent advances in low-thrust trajectory optimization, full enumeration of these problems was not possible within the stringent time limits of the competition. This investigation develops a systematic methodology for determining a broad suite of good solutions to the combinatorial, low-thrust, asteroid tour problem. The target application is for conceptual design, where broad exploration of the design space is critical, with the goal being to rapidly identify a reasonable number of promising solutions for future analysis. The proposed methodology has two steps. The first step applies a three-level heuristic sequence developed from the physics of the problem, which allows for efficient pruning of the design space. The second phase applies a global optimization scheme to locate a broad suite of good solutions to the reduced problem. The global optimization scheme developed combines a novel branch-and-bound algorithm with a genetic algorithm and an industry-standard low-thrust trajectory optimization program to solve for the following design variables: asteroid sequence, launch date, times of flight, and asteroid stay times. The methodology is developed based on a small sample problem, which is enumerated and solved so that all possible discretized solutions are known. The methodology is then validated by applying it to a larger intermediate sample problem, which also has a known solution. Next, the methodology is applied to several larger combinatorial asteroid rendezvous problems, using previously identified good solutions as validation benchmarks. These problems include the 2nd and 3rd Global Trajectory Optimization Competition problems. The methodology is shown to be capable of achieving a reduction in the number of asteroid sequences of 6-7 orders of magnitude, in terms of the number of sequences that require low-thrust optimization as compared to the number of sequences in the original problem. More than 70% of the previously known good solutions are identified, along with several new solutions that were not previously reported by any of the competitors. Overall, the methodology developed in this investigation provides an organized search technique for the low-thrust mission design of asteroid rendezvous problems.

Motivated by operational issues in real-world glass manufacturing, this thesis addresses a problem of laying out and sequencing the orders so as to minimize wasted glass, called scrap. This optimization problem combines aspects of traditional cutting problems and traditional scheduling and sequencing problems. In so far as we know, the combination of cutting and scheduling has not been modeled, or solved. We propose a two-phase approach: snap construction and constructing cutting and offload schedules. Regarding the second phase problem, we introduce FGSP (float glass scheduling problem), and provide its solution structure, called coveys. We analyze simple sub-models of FGSP considering the main elements: time, unit, and width. For each model, we provide either a polynomial time algorithm or a proof of NP-completeness. Since FGSP is NP-complete, we propose a heuristic algorithm, Longest Unit First (LUF), and analyze the worst case performance of the algorithm in terms of the quality of solutions; the worst case performance bound is {1+(m-1)/m}+{1/3-1/(3m)} where m is the number of machines. It is 5/3 when m=2. For the real-world problem, we propose two different methods for snap construction, and we apply two main approaches to solve cutting and offloading schedules: an MIP approach and a heuristic approach. Our solution approach produces manufacturing yields greater than 99%; current practice is about 95%. This is a significant improvement and these high-yield solutions can save millions of dollars.

This thesis presents several decentralized, learning-based algorithms for on-line routing of bandwidth guaranteed paths. The presented routing algorithms do not need any a-priori knowledge of traffic demand; they use only their locally observed events and update their routing policy using learning schemes. The employed learning algorithms are either learning automata or the multi-armed bandit algorithms. We investigate the asymptotic behavior of the proposed routing algorithms and prove the convergence of one of them to the user equilibrium. Discrete event simulation results show the merit of these algorithms in terms of improving the resource utilization and increasing the network admissibility compared with shortest path routing. / We investigate the performance degradation due to decentralized routing as opposed to centralized optimal routing policies in practical scenarios. The system optimal and the Nash bargaining solutions are two centralized benchmarks used in this study. We provide nonlinear programming formulations of these problems along with a distributed recursive approach to compute the solutions. An on-line partially-decentralized control architecture is also proposed to achieve the system optimal and the Nash bargaining solution performances. Numerical results in some practical scenarios with well engineered networks, where the network resources and traffic demand are well matched, indicate that decentralized learning techniques provide efficient, stable and scalable approaches for routing the bandwidth guaranteed paths. / In the context of on-line learning, we propose a new algorithm to track the best action-selection policy when it abruptly changes over time. The proposed algorithm employs change detection mechanisms to detect the sudden changes and restarts the learning process on the detection of an abrupt change. The performance analysis of this study reveals that when all the changes are detectable by the change detection mechanism, the proposed tracking the best action-selection policy algorithm is rate optimal. On-line routing of bandwidth guaranteed paths with the potential occurrence of network shocks such as significant changes in the traffic demand is one of the applications of the devised algorithm. Simulation results show the merit of the proposed algorithm in tracking the optimal routing policy when it abruptly changes.

Successful tracking of a mobile target with a sensor network requires effective answers to the challenges of uncertainty in the measured data, small latency in acquiring and reporting the tracking information, and compliance with the stringent constraints imposed by the scarce resources available on each sensor node: limited available power, restricted availability of the inter-node communication links, relatively moderate computational power. This thesis introduces the architecture of a hierarchical, self-organizing, two-tier, mission-specific sensor network, composed of sensors and routers, to track the trajectory and velocity of a single mobile target in a two-dimensional convex sensor field. A query-driven approach is proposed to input configuration parameters to the network, which allow sensors to self-configure into regions, and routers into tree-like structures, with the common goal of sensing and tracking the target in an energy-aware manner, and communicating this tracking data to a base station node incurring low-overhead responses, respectively. The proposed algorithms to define and organize the sensor regions, establish the data routing scheme, and create the data stream representing the real-time location/velocity of a target, are heuristic, distributed, and represent localized node collaborations. Node behaviours have been modeled using state diagrams and inter-node collaborations have been designed using straightforward messaging schemes. This work has attempted to establish that by using a query-driven approach to track a target, high-level knowledge can be injected to the sensor network self-organization processes and its following operation, which allows the implementation of an energy-efficient, low-overhead tracking scheme. The resulting system, although built upon simple components and interactions, is complex in extension, and not directly available for exact evaluation. However, it provides intuitively advantageous behaviours. / Thesis (Master, Computing) -- Queen's University, 2009-03-04 11:18:14.392

Technologies like IEEE 802.16j wireless mesh networks are drawing increasing attention of the research community. Mesh networks are economically viable and may extend services such as Internet to remote locations. This thesis takes interest into a planning problem in IEEE 802.16j networks, where we need to establish minimum cost relay and base stations to cover the bandwidth demand of wireless clients. A special feature of this planning problem is that any node in this network can send data to at most one node towards the next hop, thus traffic flow is unsplittable from source to destination. We study different integer programming formulations of the problem. We propose four types of heuristic algorithms that uses greedy, local search, variable neighborhood search and Lagrangian relaxation based approaches for the problem. We evaluate the algorithms on database of network instances of 500-5000 nodes, some of which are randomly generated network instances, while other network instances are generated over geometric distribution. Our experiments show that the proposed algorithms produce satisfactory result compared to benchmarks produced by generalized optimization problem solver software. / x, 131 leaves : ill. ; 29 cm