在約束滿足問題中，破壞指數量級數量的所有對稱通常過於昂貴。在實踐中，我們通常只有效地破壞對稱的一個子集。我們稱之為目標對稱。在靜態對稱破壞中，我們的目標是發佈一套約束去破壞這些目標對稱，以達到減少解集以及搜索空間的效果。一個問題中的所有對稱之間是互相交織的。一個旨在特定對稱的破壞對稱約束几乎總會產生副作用，而不僅僅破壞了預期的對稱。破壞相同目標對稱的不同約束可以有不同的副作用。傳統智慧告訴我們應該選擇一個破壞更多對稱從而有更多副作用的破壞對稱約束。雖然這樣的說法在許多方面上都是有效的，我們應該更加注意副作用發生的地方。 / 給與一個約束滿足問題，一個對稱被一個約束保留當且僅當該對稱仍然是新的約束滿足問題的對稱。這個新的約束滿足問題是有原問題加上該約束組成的。我們給出定律和例子，以表明發佈儘量保留目標對稱以及限制它的副作用發生在非目標對稱上的破壞約束是有利的。這些好處來自于被破壞的對稱數目以及一個對稱被破壞（或消除）的程度，并導致一個較小的解集和搜索空間。但是，對稱不一定會被保留。我們顯示，旨在一個已經被消除的目標對稱的破壞對稱約束仍然可以被發佈。我們建議根據問題的約束以及其他破壞對稱約束來選擇破壞對稱約束，以繼續消除更多的對稱。我們進行了廣泛的實驗來確認我們的建議的可行性與效率。 / Breaking the exponential number of all symmetries of a constraint satisfaction problem is often too costly. In practice, we often aim at breaking a subset of the symmetries efficiently, which we call target symmetries. In static sym-metry breaking, the goal is to post a set of constraints to break these target symmetries in order to reduce the solution set and thus also the search space. Symmetries of a problem are all intertwined. A symmetry breaking constraint intended for a particular symmetry almost always breaks more than just the intended symmetry as a side-effect. Different constraints for breaking the same target symmetry can have different side-effects. Conventional wisdom suggests that we should select a symmetry breaking constraint that has more side-effects by breaking more symmetries. While this wisdom is valid in many ways, we should be careful where the side-effects take place. / A symmetry σ of a CSP P =(V, D, C) is preserved by a set of symmetry breaking constraints C{U+02E2}{U+1D47} i σ is a symmetry of P¹ =(V, D, CU C{U+02E2}{U+1D47}). We give theorems and examples to demonstrate that it is beneficial to post symmetry breaking constraints that preserve the target symmetries and restrict the side-effects to only non-target symmetries as much as possible. The benefits are in terms of the number of symmetries broken and the extent to which a symmetry is broken (or eliminated), resulting in a smaller solution set and search space. However, symmetry preservation may not always hold. We illustrate that symmetry breaking constraints, which aim at a target symmetry that is already eliminated, can still be posted. To continue eliminating more symmetries, we suggest to select symmetry breaking constraints based on problem constraints and other symmetry breaking constraints. Extensive experiments are also conducted to confirm the feasibility and efficiency of our proposal empirically. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Jingying. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 101-112). / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Motivation and Goals --- p.3 / Chapter 1.3 --- Outline of Thesis --- p.5 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.8 / Chapter 2.1.1 --- Backtracking Search --- p.9 / Chapter 2.1.2 --- Consistency Techniques --- p.12 / Chapter 2.1.3 --- Local Consistencies with Backtracking Search --- p.15 / Chapter 2.2 --- Symmetry Breaking in CSPs --- p.16 / Chapter 2.2.1 --- Symmetry Classes --- p.18 / Chapter 2.2.2 --- Breaking Symmetries --- p.22 / Chapter 2.2.3 --- Variable and Value Symmetries --- p.23 / Chapter 2.2.4 --- Symmetry Breaking Constraints --- p.26 / Chapter 3 --- Effects of Symmetry Breaking Constraints --- p.29 / Chapter 3.1 --- Removing Symmetric Search Space --- p.29 / Chapter 3.1.1 --- Properties --- p.30 / Chapter 3.1.2 --- Canonical Variable Orderings --- p.31 / Chapter 3.1.3 --- Regenerating All Solutions --- p.33 / Chapter 3.1.4 --- Remaining Solution Set Sizes --- p.36 / Chapter 3.2 --- Constraint Interactions in Propagation --- p.43 / Chapter 4 --- Choices of Symmetry Breaking Constraints --- p.45 / Chapter 4.1 --- Side-Effects --- p.45 / Chapter 4.2 --- Symmetry Preservation --- p.50 / Chapter 4.2.1 --- De nition and Properties --- p.50 / Chapter 4.2.2 --- Solution Reduction --- p.54 / Chapter 4.2.3 --- Preservation Examples --- p.55 / Chapter 4.2.4 --- Preserving Order --- p.64 / Chapter 4.3 --- Eliminating Eliminated Symmetries --- p.65 / Chapter 4.3.1 --- Further Elimination --- p.65 / Chapter 4.3.2 --- Aggressive Elimination --- p.71 / Chapter 4.4 --- Interactions with Problem Constraints --- p.72 / Chapter 4.4.1 --- Further Simplification --- p.72 / Chapter 4.4.2 --- Increasing Constraint Propagation --- p.73 / Chapter 5 --- Experiments --- p.75 / Chapter 5.1 --- Symmetry Preservation --- p.75 / Chapter 5.1.1 --- Diagonal Latin Square Problem --- p.76 / Chapter 5.1.2 --- NN-Queen Problem --- p.77 / Chapter 5.1.3 --- Error Correcting Code - Lee Distance (ECCLD) --- p.78 / Chapter 5.2 --- Eliminating Eliminated Symmetries --- p.80 / Chapter 5.2.1 --- Equidistance Frequency Permutation Array Problem --- p.80 / Chapter 5.2.2 --- Cover Array Problem --- p.82 / Chapter 5.2.3 --- Sports League Scheduling Problem --- p.83 / Chapter 6 --- Related Work --- p.86 / Chapter 6.1 --- Symmetry Breaking Approaches --- p.86 / Chapter 6.2 --- Reducing Overhead and Increasing Propagation --- p.90 / Chapter 6.3 --- Selecting and Generating Choices --- p.91 / Chapter 6.3.1 --- Reducing Conflict with Search Heuristic --- p.92 / Chapter 6.3.2 --- Choosing the Subset of Symmetries --- p.93 / Chapter 6.4 --- Detecting Symmetries --- p.93 / Chapter 7 --- Conclusion and Remarks --- p.95 / Chapter 7.1 --- Conclusion --- p.95 / Chapter 7.2 --- Discussions --- p.97 / Chapter 7.3 --- Future Work --- p.99 / Bibliography --- p.101

by Won, Hon Wing Stephen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 95-101). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problem --- p.1 / Chapter 1.2 --- CSP Solving Techniques --- p.2 / Chapter 1.3 --- Motivation of the Dissertation --- p.4 / Chapter 1.4 --- Overview of the Dissertation --- p.6 / Chapter 2 --- Related Work --- p.8 / Chapter 2.1 --- Heuristic Repair Method --- p.8 / Chapter 2.2 --- GSAT --- p.8 / Chapter 2.3 --- GENET --- p.9 / Chapter 2.4 --- Simulated Annealing --- p.9 / Chapter 2.5 --- Genetic Algorithms --- p.10 / Chapter 3 --- Overview of GENET --- p.11 / Chapter 3.1 --- Network Architecture --- p.11 / Chapter 3.2 --- Convergence Procedure --- p.12 / Chapter 3.3 --- The illegal and atmost Constraints --- p.13 / Chapter 3.3.1 --- The illegal Constraint --- p.14 / Chapter 3.3.2 --- The atmost Constraint --- p.14 / Chapter 3.4 --- General Non-Binary Constraints --- p.15 / Chapter 3.4.1 --- Constraint Transformation --- p.15 / Chapter 3.4.2 --- Using the illegal Constraints --- p.17 / Chapter 3.4.3 --- Problem Transformation --- p.17 / Chapter 4 --- An Extended GENET --- p.20 / Chapter 4.1 --- Network Architecture --- p.20 / Chapter 4.2 --- Convergence Procedure --- p.22 / Chapter 4.3 --- E-GENET as a Generalization of GENET --- p.24 / Chapter 4.3.1 --- Constraints --- p.30 / Chapter 4.3.2 --- Network Architecture --- p.31 / Chapter 4.4 --- Properties of E-GENET --- p.32 / Chapter 4.4.1 --- Incompleteness of E-GENET --- p.33 / Chapter 4.4.2 --- Making E-GENET Complete --- p.36 / Chapter 4.5 --- Storage Scheme --- p.38 / Chapter 4.5.1 --- The illegal and atmost Constraint --- p.39 / Chapter 4.5.2 --- The Disequality Constraint --- p.39 / Chapter 4.5.3 --- General Constraints --- p.40 / Chapter 4.6 --- Benchmarking Results --- p.40 / Chapter 4.6.1 --- The Graph-Coloring Problem --- p.41 / Chapter 4.6.2 --- The N-queens Problem --- p.42 / Chapter 4.6.3 --- The Car-Sequencing Problem --- p.43 / Chapter 4.6.4 --- The Cryptarithmetic Problem --- p.44 / Chapter 4.6.5 --- The Hamiltonian Path Problem --- p.45 / Chapter 5 --- Optimizations to E-GENET --- p.47 / Chapter 5.1 --- Inadequacies of E-GENET --- p.47 / Chapter 5.1.1 --- Cumbrous Constraint Node --- p.48 / Chapter 5.1.2 --- Inefficiency of the min-conflicts heuristic --- p.48 / Chapter 5.2 --- Optimizations --- p.50 / Chapter 5.2.1 --- Intermediate Node --- p.50 / Chapter 5.2.2 --- New Assignment Scheme of Initial Penalty Values --- p.55 / Chapter 5.2.3 --- Concept of Contribution --- p.57 / Chapter 5.2.4 --- Learning Heuristic --- p.62 / Chapter 6 --- A Comprehensive Constraint Library --- p.63 / Chapter 6.1 --- Elementary Constraints --- p.64 / Chapter 6.1.1 --- Linear Arithmetic Constraints --- p.64 / Chapter 6.1.2 --- The atmost Constraint --- p.66 / Chapter 6.1.3 --- Disjunctive Constraints --- p.69 / Chapter 6.2 --- Global Constraints --- p.71 / Chapter 6.2.1 --- The cumulative Constraint --- p.72 / Chapter 6.2.2 --- The among Constraint --- p.77 / Chapter 6.2.3 --- The diffn Constraint --- p.82 / Chapter 6.2.4 --- The cycle Constraint --- p.85 / Chapter 7 --- Conclusion --- p.89 / Chapter 7.1 --- Contributions --- p.89 / Chapter 7.2 --- Discussions --- p.90 / Chapter 7.3 --- Future Work --- p.94 / Bibliography --- p.95

Mak, Wai Keung Terrence. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 100-104). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.2 / Chapter 1.3 --- Quantified Constraint Satisfaction Problems --- p.3 / Chapter 1.4 --- Motivation and Goal --- p.4 / Chapter 1.5 --- Outline of the Thesis --- p.6 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.7 / Chapter 2.1.1 --- Backtracking Tree Search --- p.9 / Chapter 2.1.2 --- Local Consistencies for solving CSPs --- p.11 / Node Consistency (NC) --- p.13 / Arc Consistency (AC) --- p.14 / Searching by Maintaining Arc Consistency --- p.16 / Chapter 2.1.3 --- Constraint Optimization Problems --- p.17 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.19 / Chapter 2.2.1 --- Branch and Bound Search (B&B) --- p.23 / Chapter 2.2.2 --- Local Consistencies for WCSPs --- p.25 / Node Consistency --- p.26 / Arc Consistency --- p.28 / Chapter 2.3 --- Quantified Constraint Satisfaction Problems --- p.32 / Chapter 2.3.1 --- Backtracking Free search --- p.37 / Chapter 2.3.2 --- Consistencies for QCSPs --- p.38 / Chapter 2.3.3 --- Look Ahead for QCSPs --- p.45 / Chapter 3 --- Quantified Weighted CSPs --- p.48 / Chapter 4 --- Branch & Bound with Consistency Techniques --- p.54 / Chapter 4.1 --- Alpha-Beta Pruning --- p.54 / Chapter 4.2 --- Consistency Techniques --- p.57 / Chapter 4.2.1 --- Node Consistency --- p.62 / Overview --- p.62 / Lower Bound of A-Cost --- p.62 / Upper Bound of A-Cost --- p.66 / Projecting Unary Costs to Cθ --- p.67 / Chapter 4.2.2 --- Enforcing Algorithm for NC --- p.68 / Projection Phase --- p.69 / Pruning Phase --- p.69 / Time Complexity --- p.71 / Chapter 4.2.3 --- Arc Consistency --- p.73 / Overview --- p.73 / Lower Bound of A-Cost --- p.73 / Upper Bound of A-Cost --- p.75 / Projecting Binary Costs to Unary Constraint --- p.75 / Chapter 4.2.4 --- Enforcing Algorithm for AC --- p.76 / Projection Phase --- p.77 / Pruning Phase --- p.77 / Time complexity --- p.79 / Chapter 5 --- Performance Evaluation --- p.83 / Chapter 5.1 --- Definitions of QCOP/QCOP+ --- p.83 / Chapter 5.2 --- Transforming QWCSPs into QCOPs --- p.90 / Chapter 5.3 --- Empirical Evaluation --- p.91 / Chapter 5.3.1 --- Random Generated Problems --- p.92 / Chapter 5.3.2 --- Graph Coloring Game --- p.92 / Chapter 5.3.3 --- Min-Max Resource Allocation Problem --- p.93 / Chapter 5.3.4 --- Value Ordering Heuristics --- p.94 / Chapter 6 --- Concluding Remarks --- p.96 / Chapter 6.1 --- Contributions --- p.96 / Chapter 6.2 --- Limitations and Related Works --- p.97 / Chapter 6.3 --- Future Works --- p.99 / Bibliography --- p.100

We develop a framework for finding robust solutions of constraint programs. Our approach is based on the notion of fault tolerance. We formalise this concept within constraint programming, extend it in several dimensions and introduce some algorithms to find robust solutions efficiently. When applying constraint programming to real world problems we often face uncertainty. Whilst reactive methods merely deal with the consequences of an unexpected change, taking a more proactive approach may guarantee a certain level of robustness. We propose to apply the fault tolerance framework, introduced in [Ginsberg 98], to constraint programming: A robust solution is one such that a small perturbation only requires a small response. We identify, define and classify a number of abstract problems related to stability within constraint satisfaction or optimisation. We propose some efficient and effective algorithms for solving these problems. We then extend this framework by allowing the repairs and perturbations themselves to be constrained. Finally, we assess the practicality of this framework on constraint satisfaction and scheduling problems.

Un component important de molts sistemes de distribució és el càlcul de les rutes dels vehicles per servir els clients. El Vehicle Routing Problem (VRP) proporciona el marc teòric per tractar aquest tipus de problemes logístics relacionats amb la distribució física de béns. Per la seva complexitat i aplicabilitat, aquest tipus de problemes logístics es troba entre les línies de recerca més populars en optimització combinatòria. Aquesta tesi de doctorat té com a objectiu la introducció de tres metodologies diferents per resoldre el VRP. Aquestes metodologies han estat especialment dissenyades per ser flexibles, en el sentit que poden ser utilitzades, amb adaptacions menors, per resoldre diferents variants del VRP presents en casos d’aplicació industrial. En les tres metodologies descrites en aquest treball s’utilitzen diferents tècniques per aconseguir la flexibilitat, l’eficiència i la robustesa desitjades. Constraint Programming (CP) ha estat escollit com a paradigma de modelat per descriure les principals restriccions presents en el VRP. CP proporciona la flexibilitat desitjada per les tres metodologies, atès que afegir restriccions addicionals presents en molts casos d’aplicació real només afecta al modelat del problema, però no a la definició dels algorismes de cerca. En les dues primeres metodologies descrites, el model de CP només s’utilitza per comprovar la factibilitat de les solucions durant la cerca. La tercera metodologia presenta un model més ric del VRP que permet tractar diferents variants del problema. En aquest cas, la cerca es realitza i es controla fent servir els mecanismes que CP proporciona. La Relaxació Lagrangiana (LR) i una versió probabilística de l’heurística Clarke and Wright Savings (RCWS) s’utilitzen amb una finalitat molt específica dins de les metodologies. LR s’utilitza per minimitzar la distància total recorreguda pels vehicles, mentre que la RCWS es fa servir per calcular una solució inicial de bona qualitat. Ambdós mètodes proporcionen una aproximació eficient als problemes respectius. A més, la utilització de LR permet reduir la complexitat computacional dels processos de cerca local i, d’aquesta manera, redueix el temps computacional necessari per resoldre el VRP. Totes les metodologies es basen en la metaheurística coneguda com Variable Neighborhood Search (VNS). El VNS està format per una família d’algorismes que aprofiten sistemàticament la idea de canviar el veïnat explorat al voltant d’una solució, tant en el procés de cerca per trobar un mínim local com en el procés de pertorbació, per escapar de la vall corresponent. Malgrat que és un mètode bastant estès, hi ha pocs exemples d’aplicació en el VRP. En tot cas, fins i tot els mètodes VNS més simples han aconseguit bons resultats quan han estat aplicats en aquest problema. Aquesta tesi té com a objectiu contribuir en la recerca de l’aplicació de la metaheurística VNS en el VRP. Aquesta ha estat escollida com a marc en el que integrar les tècniques mencionades. Així, la metaheurística s’utilitza per guiar la cerca, mentre que l’eficiència desitjada s’aconsegueix mitjançant els mètodes que s’hi integren. D’altra banda, utilitzar CP com a paradigma de modelat proporciona la flexibilitat requerida. Aquesta característica és especialment rellevant en el cas de la darrera metodologia descrita. En aquest cas, la cerca de CP es guia mitjançant una combinació de les metaheurístiques VNS i Large Neighborhood Search (LNS). Aquesta metodologia representa una primera aproximació a la resolució eficient de problemes VRP més complexos, similars a casos d’aplicació real. / An important component of many distribution systems is routing vehicles to serve customers. The Vehicle Routing Problem (VRP) provides a theoretical framework for approaching this class of logistics problems dealing with physical distribution. Because of its complexity and applicability, this class of logistics problems is among the most popular research areas in combinatorial optimization. This PhD. Thesis is aimed to introduce three different yet related hybrid methodologies to solve the VRP. These methodologies have been especially designed for being flexible in the sense that they can be used, with minor adaptations, for solving different variants of the VRP present in industrial application cases. In the three methodologies described in this work, different technologies are used to achieve the desired flexibility, efficiency, and robustness. Constraint Programming (CP) has been chosen as the modeling paradigm to describe the main constraints involved in the VRP. CP provides the pursued flexibility for the three methodologies, since adding side constraints present in most real application cases becomes a modeling issue and does not affect the search algorithm definition. In the first two hybrid methodologies, the CP model is used to check solution's feasibility during search. The third methodology presents a richer model for the VRP capable of tackling different problem variants. In this case, the search is performed and controlled from a CP perspective. Lagrangian Relaxation (LR) and a probabilistic version of the Clarke and Wright Savings (CWS) heuristic are used for specific purposes within the proposed methodologies. The former is used for minimizing the total traveled distance and the latter to provide a good initial solution. Both methods provide an efficient approach to the respectively faced problems. Moreover, the use of LR permits reducing the computational complexity of the performed local search processes and therefore reduces the required computational time to solve the VRP. All methodologies are based on the so-called Variable Neighborhood Search (VNS) metaheuristic. The VNS is formed by a family of algorithms that exploits systematically the idea of neighborhood changes both in the search phase to find a local minimum, and in perturbation phase, to escape from the corresponding valley. Although it is an extended method, there are few examples of its application to the VRP. However, interesting results have been obtained even applying the simplest VNS algorithms to this problem. The present thesis is aimed to contribute to the current research on the application of the VNS metaheuristic to the VRP. It has been chosen as the framework where the mentioned techniques are embedded. Hence, the metaheuristic is used to guide the search, while the desired efficiency is provided by the composing methods. On the other hand, using CP as the modeling paradigm provides the required flexibility. This characteristic is enhanced in the last described methodology. In this case, the CP search is guided by a combination of the VNS and the Large Neighborhood Search (LNS) metaheuristics. This methodology represents an initial approach for tackling efficiently more complex and richer VRP, similar to real application cases.

This thesis examines three computational problems in sports. The first problem addressed is determining the minimum number of points needed to guarantee qualification for the playoffs and the minimum number of points needed to have a possibility of qualification for the playoffs of the National Hockey League (NHL). The problem is solved using a phased approach that incrementally adds more complicated tie-breaking constraints if a solution is not found. Each of the phases is solved using a combination of network flows, enumeration and constraint programming. The experimental results show that the solver efficiently solves instances at any point of the season. The second problem addressed is determining the complexity, either worst-case theoretical or practical, of manipulation strategies in sports tournaments. The two most common types of competitions, cups and round robins, are considered and it is shown that there exists a number of polynomial time algorithms for finding manipulation strategies in basic cups and round robins as well as variants. A different type of manipulation, seeding manipulation, is examined from a practical perspective. While the theoretical worst-case complexity remains open, this work shows that, at least on random instances, seeding manipulation even with additional restrictions remains practically manipulable. The third problem addressed is determining whether manipulation strategies can be detected if they were executed in a real tournament. For cups and round robins, algorithms are presented which identify whether a coalition is manipulating the tournament with high accuracy. For seeding manipulation, it is determined that even with many different restrictions it is difficult to determine if manipulation has occurred.

This thesis examines three computational problems in sports. The first problem addressed is determining the minimum number of points needed to guarantee qualification for the playoffs and the minimum number of points needed to have a possibility of qualification for the playoffs of the National Hockey League (NHL). The problem is solved using a phased approach that incrementally adds more complicated tie-breaking constraints if a solution is not found. Each of the phases is solved using a combination of network flows, enumeration and constraint programming. The experimental results show that the solver efficiently solves instances at any point of the season. The second problem addressed is determining the complexity, either worst-case theoretical or practical, of manipulation strategies in sports tournaments. The two most common types of competitions, cups and round robins, are considered and it is shown that there exists a number of polynomial time algorithms for finding manipulation strategies in basic cups and round robins as well as variants. A different type of manipulation, seeding manipulation, is examined from a practical perspective. While the theoretical worst-case complexity remains open, this work shows that, at least on random instances, seeding manipulation even with additional restrictions remains practically manipulable. The third problem addressed is determining whether manipulation strategies can be detected if they were executed in a real tournament. For cups and round robins, algorithms are presented which identify whether a coalition is manipulating the tournament with high accuracy. For seeding manipulation, it is determined that even with many different restrictions it is difficult to determine if manipulation has occurred.

No description available.

No description available.

We develop a framework for finding robust solutions of constraint programs. Our approach is based on the notion of fault tolerance. We formalise this concept within constraint programming, extend it in several dimensions and introduce some algorithms to find robust solutions efficiently. When applying constraint programming to real world problems we often face uncertainty. Whilst reactive methods merely deal with the consequences of an unexpected change, taking a more proactive approach may guarantee a certain level of robustness. We propose to apply the fault tolerance framework, introduced in [Ginsberg 98], to constraint programming: A robust solution is one such that a small perturbation only requires a small response. We identify, define and classify a number of abstract problems related to stability within constraint satisfaction or optimisation. We propose some efficient and effective algorithms for solving these problems. We then extend this framework by allowing the repairs and perturbations themselves to be constrained. Finally, we assess the practicality of this framework on constraint satisfaction and scheduling problems.