M.Sc., Faculty of Sciences, University of the Witwatersrand, 2011 / Abstract This dissertation is concerned with discrete global optimization of nonlinear problems. These problems are constrained and unconstrained and are not easily solvable since there exists multiplicity of local and global minima. In this dissertation, we study the current methods for solving such problems and highlight their ine ciencies. We introduce a new local search procedure. We study the rapidly-exploring random tree (RRT) method, found mostly in the research area of robotics. We then design two global optimization algorithms based on RRT. RRT has never been used in the eld of global optimization. We exploit its attractive properties to develop two new algorithms for solving the discrete nonlinear optimization problems. The rst method is called RRT-Optimizer and is denoted as RRTOpt. RRTOpt is then modi ed to include probabilistic elements within the RRT. We have denoted this method by RRTOptv1. Results are generated for both methods and numerical comparisons are made with a number of recent methods.

A crescente necessidade de buscar operações mais eficientes, com menor custo e mais sustentáveis tem feito com que empresas passassem a procurar oportunidades pelas quais estes objetivos pudessem ser atingidos. Na área de transportes encontrou-se na colaboração uma oportunidade para tal. Este trabalho trata o problema de cobertura rotas com cardinalidade restrita (PCRCR), onde empresas que realizam viagens de carga cheia se unem com o objetivo de reduzir o deslocamento vazio de veículos através da formação de ciclos. É chamado de problema de cardinalidade restrita uma vez que limitamos o número de máximo de viagens no ciclo, o que torna este problema NP-Hard. Existem na literatura duas heurísticas (construtivas) e um modelo por programação linear inteira para a solução deste problema. Este trabalho apresenta uma heurística baseada em um método de busca local que reduziu em média 3,19% os melhores resultados apresentados na literatura. Também são apresentados os tempos de execução de cada um dos algoritmos e a importância de escolher de uma boa solução inicial quando se deseja implantar uma Heurística com Busca Local. / The growing need to seek more efficient, lower cost and more sustainable operations has caused industries to seek opportunities in which these objectives could be achieved. In the area of transportation, collaboration is an opportunity for that. This work deals with the cardinality constrained lane covering problem (CCLCP), where companies who uses full truck loads join efforts in order to reduce empty vehicle travel through closed cycle formation. It is known as cardinality constraint problem as the maximum number of trips in the cycle is limited to an integer number, which makes this problem NP-Hard. There are two heuristics in the literature (constructive) and an integer linear programming model for solving this problem. This work presents a heuristic based on a local search method that reduced an average of 3.19% the better results in the literature. It also presents the execution times of each algorithm and the importance of choosing a good initial solution when you want to create a Local Search Heuristic.

Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2012

The propositional satisfiability (SAT) problem is of considerable theoretical and practical relevance to the artificial intelligence (AI) community and has been used to model many pervasive AI tasks such as default reasoning, diagnosis, planning, image interpretation, and constraint satisfaction. Computational methods for SAT have historically fallen into two broad categories: complete search and local search. Within the local search category, clause weighting methods are amongst the best alternatives for SAT, becoming particularly attractive on problems where a complete search is impractical or where there is a need to find good candidate solutions within a short time. The thesis is concerned with the study of improvements to clause weighting local search methods for SAT. The main contributions are: A component-based framework for the functional analysis of local search methods. A clause weighting local search heuristic that exploits longer-term memory arising from clause weight manipulations. The approach first learns which clauses are globally hardest to satisfy and then uses this information to treat these clauses differentially during weight manipulation [Ferreira Jr and Thornton, 2004]. A study of heuristic tie breaking in the domain of additive clause weighting local search methods, and the introduction of a competitive method that uses heuristic tie breaking instead of the random tie breaking approach used in most existing methods [Ferreira Jr and Thornton, 2005]. An evaluation of backbone guidance for clause weighting local search, and the introduction of backbone guidance to three state-of-the-art clause weighting local search methods [Ferreira Jr, 2006]. A new clause weighting local search method for SAT that successfully exploits synergies between the longer-term memory and tie breaking heuristics developed in the thesis to significantly improve on the performance of current state-of-the-art local search methods for SAT-encoded instances containing identifiable CSP structure. Portions of this thesis have appeared in the following refereed publications: Longer-term memory in clause weighting local search for SAT. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, volume 3339 of Lecture Notes in Artificial Intelligence, pages 730-741, Cairns, Australia, 2004. Tie breaking in clause weighting local search for SAT. In Proceedings of the 18th Australian Joint Conference on Artificial Intelligence, volume 3809 of Lecture Notes in Artificial Intelligence, pages 70–81, Sydney, Australia, 2005. Backbone guided dynamic local search for propositional satisfiability. In Proceedings of the Ninth International Symposium on Artificial Intelligence and Mathematics, AI&M, Fort Lauderdale, Florida, 2006.

Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].

One of the challenges for the constraint satisfaction community has been to develop an automated approach to solving Constraint Satisfaction Problems (CSPs) rather than creating specific algorithms for specific problems. Much of this work has concentrated on the development and improvement of general purpose backtracking techniques. However, the success of relatively simple local search techniques on larger satisfiability problems [Selman et a!. 1992] and CSPs such as the n-queens [Minton et al. 1992] has caused interest in applying local search to constraint satisfaction. In this thesis we look at the usefulness of constraint weighting as a local search technique for constraint satisfaction. The work is based on the clause weighting ideas of Selman and Kautz [1993] and Moths [1993] and applies, evaluates and extends these ideas from the satisfiability domain to the more general domain of CSPs. Specifically, the contributions of the thesis are: 1. The introduction of a local search taxonomy. We examine the various better known local search techniques and recognise four basic strategies: restart, randomness, memory and weighting. 2. The extension of the CSP modelling framework. In order to represent and efficiently solve more realistic problems we extend the C SP modelling framework to include array-based domains and array-based domain use constraints. 3. The empirical evaluation of constraint weighting. We compare the performance of three constraint weighting strategies on a range of CSP and satisflability problems and with several other local search techniques. We find that no one technique dominates in all problem domains. 4. The characterisation of constraint weighting performance. Based on our empirical study we identiIS' the weighting behaviours and problem features that favour constrtt weighting. We conclude weighting does better on structured problems where the algorithm can recognise a harder sub-group of constraints. 5. The extension of constraint weighting. We introduce an efficient arc weighting algorithm that additionally weights connections between constraints that are simultaneously violated at a local minimum. This algorithm is empirically shown to outperform standard constraint weighting on a range of CSPs and within a general constraint solving system. Also we look at combining constraint weighting with other local search heuristics and find that these hybrid techniques can do well on problems where the parent algorithms are evenly matched. 6. The application of constraint weighting to over constrained domains. Our empirical work suggests constraint weighting does well for problems with distinctions between constraint groups. This led us to investigate solving real-world over constrained problems with hard and soft constraint groups and to introduce two dynamic constraint weighting heuristics that maintain a distinction between hard and soft constraint groups while still adding weights to violated constraints in a local minimum. In an empirical study, the dynamic schemes are shown to outperform other fixed weighting and non-weighting systems on a range of real world problems. In addition, the performance of weighting is shown to degrade less severely when soft constraints are added to the system, suggesting constraint weighting is especially applicable to realistic, hard and soft constraint problems

Tourists' information processing is a dynamic process in that their information use depends on the surrounding context. From tourists' personal characteristics (e.g., age, gender, and travel experience), nature of tourism products (e.g., intangibility and variability), to the development of information technology (e.g., the prevalent usage of mobile devices for information search), a variety of contextual factors are involved when tourists process information for decision-making. Given the importance of online reviews in the hospitality and tourism field as information sources, this dissertation aims to understand the contextual effects of online reviews on tourists' decision-making. By selecting several contextual factors, three independent and interrelated essays examine how tourists' cognitive or behavioral responses to online reviews are affected by those factors. Considering that local search (e.g., looking for nearby restaurants by using "restaurants near me" as a search query) becomes an important context for using online reviews, both Study 1 and 2 focus on the local search context. Study 1 investigates the role of online reviews in the local search context; specifically, how online reviews are used as ranking factors by local search platforms (LSPs), is examined with an analytical approach. Study 2 investigates tourists' processing of online reviews in the local search context; specifically, how online reviews are differently processed in the local search context (e.g., searching for a restaurant that can be visited immediately) compared with the non-local context (e.g., searching for a restaurant that can be visited in a month), is examined by conducting an experiment. Building on Study 2, Study 3 investigates how tourists' processing of online reviews is affected by another contextual factor, the nature of tourism products; specifically, how the variability of tourism products (i.e., their change in quality over time) influences the way tourists process online reviews, is examined through social media analytics. Results of the three essays provide empirical support for the underlying argument of this dissertation: understanding tourists' responses to online reviews depends on factors that transcend their information characteristics. As a whole, the findings of this dissertation suggest the need for considering the surrounding context to further understand how online reviews affect tourists' decision-making. As practical implications, this dissertation discusses the importance of leveraging various types of information about tourists' context (e.g., location accessed from smartphones, and physiological condition accessed through smartwatches). / Doctor of Philosophy / Tourists use online reviews within specific situations. The effects of such reviews on tourists' decision-making are difficult to explain without considering the surrounding contexts. Depending on when (e.g., before or during the trip), where (e.g., at home or destination), or for which products (e.g., restaurants, attractions, or hotels) they use online reviews, even the same online review can be differently perceived by tourists (e.g., how helpful it is). Therefore, the reviews have an increased or reduced influence on their product choices. This dissertation aims to understand the context-dependence of tourist's use of online reviews. The three essays in this dissertation examine how online reviews are used or processed by tourists under certain context: how online reviews affect tourist's decision-making in the local search context (e.g., searching for "restaurants near me" using smartphones during the trip) (Study 1); how tourists process online reviews while relying on reviews for immediately choosing places to visit (Study 2); and how tourists perceive online reviews when they are recently posted (Study 3). The findings confirm the dynamic nature of tourist's use of online reviews and offer several insights for tourism businesses to hone their strategies on marketing online reviews.

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.

This dissertation explores approaches to the satisfiability problem, focusing on local search methods. The research endeavours to better understand how and why some local search methods are effective. At the root of this understanding are a set of metrics that characterize the behaviour of local search methods. Based on this understanding, two new local search methods are proposed and tested, the first, SDF, demonstrating the value of the insights drawn from the metrics, and the second, ESG, achieving state-of-the-art performance and generalizing the approach to arbitrary 0-1 integer linear programming problems. This generality is demonstrated by applying ESG to combinatorial auction winner determination. Further augmentations to local search are proposed and examined, exploring hybrids that incorporate aspects of backtrack search methods.

We consider the lower-bounded facility location (LBFL) problem (, also known as load-balanced facility location), which is a generalization of uncapacitated facility location (UFL) problem where each open facility is required to serve a minimum number of clients. More formally, in the LBFL problem, we are given a set of clients Ɗ , a set of facilities Ƒ, a non-negative facility-opening cost f_i for each i ∈ Ƒ, a lower bound M, and a distance metric c(i,j) on the set Ɗ ∪ Ƒ, where c(i,j) denotes the cost of assigning client j to facility i. A feasible solution S specifies the set of open facilities F_S ⊆ Ƒ and the assignment of each client j to an open facility i(j) such that each open facility serves at least M clients. Our goal is to find feasible solution S that minimizes ∑_{i ∈ F_S} f_i + ∑_j c(i,j). The current best approximation ratio for LBFL is 550. We substantially advance the state-of-the-art for LBFL by devising an approximation algorithm for LBFL that achieves a significantly-improved approximation guarantee of 83.