Lei, Ka Man. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 81-83). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

在日常生活中，我們經常會接觸到資料序列。例如機器所作出的每一個動作、模擬下的每一個狀態或是琴譜上的每一個音符，都是各種資料序列。當事情隨時間而不斷產生變化時，這些資料序列中便會有無限多個的資料。一般而言，許多問題都可建模為有限定義域的約束滿足問題。可是對於一些問題中有隨時間而產生變化的量值，在建模時便會面對很多困難。當這些問題被建模為約束滿足問題時，為了配合有限的定義域，我們通常只能把問題限制於一段固定的時間間隔中。然而，在許多情況下，很多有用的資訊會因我們的限制而流失。隨時間而變化的數值猶如一串無窮無盡的資料流。我們為此提出對無限資料串流作約束編程。無限長的資料串流使得在表示、處理和推理時，都產生一定的難度。我們設計了一套建模語育，當中包括用於資料串流的運算子。我們針對兩類資料串流集合:一些具有最終重覆樣式的串流干日一些可構成ω-正規語育的串流。根據這兩類資料串流集合的特性，我們提出兩種求解方法。當問題涉及具有最終重覆樣式的串流時，我們會把問題分割成一系列無限個有限定義域的子問題，並把子問題逐一求解出來。而當問題的所有解可構成ω-正規語言時，我們會以搜尋樹來求解，並在過程中規避一些相等於己搜尋的空間。以這方法得出的搜尋圖，其形狀同構於用以表達所有解的自動機。同時，我們亦透過定義從最終重覆樣式的串流中得出偏好值的函數，以便對無限資料串流作約束優化。在求解中藉由執行一致性概念，我們可以減少搜尋空間。我們實作了一個求解程式，用以把問題從建模語言中建立模形，並且求得解答。從一些以模擬問題及生產音樂的實驗可以印證，我們所提出對無限資料串流作約束編程的建模及解決方法的可行性。 / Sequences of data items can be found in many daily life problems. Examples are the actions of a controller in each step, states of a simulation, and notes in a piece of music. When the problems go on forever, the sequences become infinite. While many problems can be modeled as finite domain constraint satisfaction problems (CSPs), it is difficult to model problems which contain timevarying quantities over discrete time points. The constrained variables thus usually represent only a limited scope of the quantities in a finite time interval. As a result, some useful information may be lost. Time varying-quantities in the problems resemble streams of data over discrete time points. We propose constraint programming on infinite data streams. The infinite nature of streams raises difficulties in representation, manipulation, and reasoning. We design a modeling language to specify the problems. Operators are adopted to manipulate the stream values. We identify two classes of stream sets: streams with ultimately periodic patterns and streams that form an ω-regular language. According to the structure of stream sets, we propose different solution techniques to solve the CSPs. A problem involving ultimately periodic streams is divided into an infinite sequence of finite domain sub-problems. We solve the sub-problems in the sequence iteratively. A problem with solution set forming an ω-regular language is solved by tree search which avoids searching indefinitely in an infinite domain by detecting equivalent visited search space. The resultant search graph is isomorphic to an automaton representing the solution set. Optimization on the problems is made possible with a measurement of preferences on ultimately periodic streams. Consistency notions are enforced during search to reduce search space. We implement a solver to interpret and solve the problems with stream variables. Experiments on problems in some simulations and music generation are conducted to show the feasibility of modeling and solving the stream CSPs. / Detailed summary in vernacular field only. / Siu, Fai Keung. / "October 2012." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 115-119). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction and Constraint Optimization --- p.1 / Chapter 1.2 --- Infinite Data Streams --- p.2 / Chapter 1.3 --- Motivations and Goals --- p.3 / Chapter 1.4 --- Overview of the Thesis --- p.4 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.6 / Chapter 2.1.1 --- Backtracking Tree Search --- p.8 / Chapter 2.1.2 --- Consistency Notions --- p.12 / Chapter 2.2 --- Constraint Optimization Problems --- p.15 / Chapter 2.3 --- Regular Languages and Finite State Automata --- p.20 / Chapter 2.4 --- Infinite Data Streams --- p.22 / Chapter 2.4.1 --- Pointwise Operators --- p.23 / Chapter 2.4.2 --- Temporal Operators --- p.24 / Chapter 3 --- Constraint Satisfaction on Ultimately Periodic Streams --- p.26 / Chapter 3.1 --- Stream Constraint Satisfaction Problem --- p.26 / Chapter 3.1.1 --- Stream Variables and Stream Variable Domains --- p.26 / Chapter 3.1.2 --- Stream Constraints --- p.27 / Chapter 3.1.3 --- Stream CSP --- p.28 / Chapter 3.2 --- Ultimately Periodic Streams --- p.31 / Chapter 3.3 --- Solving St-CSPs for UP Solutions --- p.35 / Chapter 3.3.1 --- Translation Scheme --- p.38 / Chapter 3.3.2 --- Excluding Solutions in Non-canonical Form --- p.42 / Chapter 3.4 --- Modeling Examples and Experiments --- p.44 / Chapter 3.4.1 --- The Game of Life --- p.46 / Chapter 3.4.2 --- The n-Puzzle Problem --- p.50 / Chapter 3.4.3 --- The Traffic Light Problem --- p.55 / Chapter 4 --- Stream Constraint Satisfaction for Omega-Regular Solution Sets --- p.60 / Chapter 4.1 --- Stream Constraint Satisfaction Problem --- p.60 / Chapter 4.2 --- Solving St-CSPs for Omega-Regular Solution Sets --- p.63 / Chapter 4.2.1 --- Search Tree --- p.63 / Chapter 4.2.2 --- Instantaneous CSP --- p.64 / Chapter 4.2.3 --- Search Algorithm --- p.65 / Chapter 4.2.4 --- Solution Sets of St-CSPs --- p.66 / Chapter 4.2.5 --- Primitive Stream Constraints --- p.69 / Chapter 4.3 --- Consistency Algorithm --- p.76 / Chapter 4.4 --- Modeling Examples and Experiments --- p.79 / Chapter 4.4.1 --- Simulation of Juggling --- p.79 / Chapter 4.4.2 --- Digit Invader Game --- p.82 / Chapter 4.4.3 --- Towards Generating Jazzy Harmonization --- p.83 / Chapter 5 --- Stream Constraint Optimization --- p.86 / Chapter 5.1 --- Infinite Streams as Domain of Objective Function --- p.86 / Chapter 5.1.1 --- Straight Line Representation of Cumulative Sum of Datons --- p.87 / Chapter 5.1.2 --- Trend Comparison --- p.94 / Chapter 5.2 --- Constraint Optimization on Ultimately Periodic Streams --- p.96 / Chapter 5.3 --- Modeling Examples and Experiments --- p.98 / Chapter 5.3.1 --- The Game of Life --- p.101 / Chapter 5.3.2 --- The n-Puzzle Problem --- p.101 / Chapter 5.3.3 --- The Traffic Light Problem --- p.103 / Chapter 5.4 --- Alternative Objective Functions --- p.105 / Chapter 6 --- Related Work --- p.108 / Chapter 6.1 --- Model Checking --- p.108 / Chapter 6.2 --- Dynamic Constraint Satisfaction Problems --- p.109 / Chapter 6.3 --- Cyclic Scheduling --- p.109 / Chapter 6.4 --- Dataflow Programming Language --- p.110 / Chapter 7 --- Concluding Remarks --- p.112 / Chapter 7.1 --- Contributions --- p.112 / Chapter 7.2 --- Future Work --- p.114 / Bibliography --- p.115

在約束滿足問題中使用集合變量時，一般會利用集合範團相容算法結合基數推理來進行求解。對比單獨運用集合範團相容算法產生更多的剪枝。多重集合變量是集合變量的推廣，同一個元素可以在一個多重集合中出現多次。在本論文中，我們先把基數推理運用到多重集合變量上。男外，我們提出在建模時把多重集合的品種(即不同元素的數量)一同考慮，使模型能更具體地把問題表達出來，以加強約束傳播能力。為此，我們推論出一系列有關多重集合的品種推理規則。我們還演示了如何在一些常見的約束上運用品種推理。在子集範圍的表示方法中，一些如變量的長度因素(基數)和字典序的位置的重要訊息一概都被忽略，而這些訊息往往在求解的過程中能增加約束傳播能力。因此，按照集合變量的長度法表示方法，我們為多重集合變量提供八種以字典序為基礎的表示方法。多重集合變量中的域會按照不同的字典序，以全序關係順序排列起來。實驗結果表明，子集範團表示方法結合基數推理和品種推理，可以有效地減少問題的搜索空間，從而提升包含多重集合變量的約束滿足問題的求解效率。對於某些問題，子集範圍表示方法和以字典序為基礎的表示方法相比，後者更能提高修剪的效果和減少求解時所需要的運行時間。 / Set variables in constraint satisfaction problems (CSPs) are typically propagated by enforcing set bounds consistency together with cardinality reasoning, which uses some inference rules involving the cardinality of a set variable to produce more prunings than set bounds propagation alone. Multiset variables are a generalization of set variables by allowing the elements to have repetitions. In this thesis, we first generalize cardinality reasoning for multiset variables. In addition, we propose to exploit the variety of a multiset--the number of distinct elements in it--to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. While the subset bounds representation neglects to consider the information about the length (cardinality) and position in the lexicographic ordering, which can be important in many problems, we follow the length-lex (LL) representation for set variables and consider eight lex-based representations which give a total order for the multiset domain. The bounds of the multiset variables are maintained according to eight different orderings: length(co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety-(co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. We implement both types of multiset variable representations and evaluate their performance. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving multiset CSPs. In some kinds of problems, lex-based representations offer significantly better pruning and runtime when compared to the subset bounds representations. / Detailed summary in vernacular field only. / Woo, Hiu Chun. / "October 2012." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 101-108). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Set Variables --- p.2 / Chapter 1.3 --- Multiset Variables --- p.3 / Chapter 1.4 --- Motivations and Goals --- p.3 / 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 --- p.10 / Chapter 2.1.3 --- Local Consistencies in Backtracking Search --- p.15 / Chapter 2.2 --- Set Variables --- p.17 / Chapter 2.2.1 --- Tree Searching --- p.19 / Chapter 2.2.2 --- Set Bounds Consistency --- p.21 / Chapter 2.2.3 --- Length-lex Representation --- p.22 / Chapter 2.3 --- Multiset Variables --- p.23 / Chapter 2.3.1 --- Basic Multiset Variable Representations --- p.24 / Chapter 2.3.2 --- Multiset Bounds Consistency --- p.27 / Chapter 2.3.3 --- Multiset Constraints --- p.28 / Chapter 2.3.4 --- Enforcing Local Consistency --- p.28 / Chapter 3 --- Cardinality and Variety Information in Multisets --- p.32 / Chapter 3.1 --- Cardinality Variable --- p.32 / Chapter 3.2 --- Cardinality Reasoning --- p.34 / Chapter 3.3 --- Variety Variable --- p.39 / Chapter 3.4 --- Inferences within One Multiset Variable --- p.42 / Chapter 3.4.1 --- Inferences between occ(i, S) and CS --- p.42 / Chapter 3.4.2 --- Inferences between occ(i, S) and VS --- p.43 / Chapter 3.4.3 --- Inferences between CS and VS --- p.44 / Chapter 3.4.4 --- Inferences among occ(i, S), CS, and VS --- p.45 / Chapter 3.4.5 --- Failure --- p.47 / Chapter 3.4.6 --- Discussion --- p.47 / Chapter 3.5 --- Cardinality-Variety Reasoning --- p.50 / Chapter 4 --- Lex-induced Orderings in Multisets --- p.56 / Chapter 4.1 --- Multiset Variables --- p.57 / Chapter 4.2 --- Lex Orderings --- p.57 / Chapter 4.2.1 --- Length-lex Ordering --- p.58 / Chapter 4.2.2 --- Variety-lex Ordering --- p.58 / Chapter 4.2.3 --- Length-variety-lex Ordering --- p.58 / Chapter 4.2.4 --- Variety-length-lex Ordering --- p.58 / Chapter 4.3 --- Colex Orderings --- p.59 / Chapter 4.3.1 --- Length-colex Ordering --- p.59 / Chapter 4.3.2 --- Variety-colex Ordering --- p.59 / Chapter 4.3.3 --- Length-variety-colex Ordering --- p.59 / Chapter 4.3.4 --- Variety-length-colex Ordering --- p.60 / Chapter 4.4 --- Exactness --- p.62 / Chapter 4.5 --- Compactness --- p.67 / Chapter 4.6 --- Empirical Comparisons --- p.69 / Chapter 4.7 --- Bounds Consistency --- p.73 / Chapter 5 --- Experiments --- p.78 / Chapter 5.1 --- Template Design Problem --- p.79 / Chapter 5.2 --- Generalized Extended Steiner System --- p.82 / Chapter 5.3 --- Generalized Social Golfer Problem --- p.85 / Chapter 5.4 --- Generalized Warehouse Location Problem --- p.87 / Chapter 5.5 --- Discussion --- p.90 / Chapter 6 --- Related Work --- p.93 / Chapter 6.1 --- Set Variables and Constraints --- p.93 / Chapter 6.1.1 --- Subset Bounds Representation --- p.94 / Chapter 6.1.2 --- Length-lex Representation --- p.95 / Chapter 6.2 --- Weighted Constraint Satisfaction with Set Variables --- p.96 / Chapter 6.3 --- Multiset Variables and Constraints --- p.96 / Chapter 7 --- Concluding Remarks --- p.98 / Chapter 7.1 --- Contributions --- p.98 / Chapter 7.2 --- Future Work --- p.99 / Bibliography --- p.101

Cheng Chi Kan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 101-105). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.4 / Chapter 2.1 --- Propagation Based Constraint Solving --- p.4 / Chapter 2.1.1 --- "Valuations, Domains and Constraints" --- p.4 / Chapter 2.1.2 --- Solving a CSP --- p.6 / Chapter 2.1.3 --- Propagators --- p.7 / Chapter 2.1.4 --- Domain Consistency --- p.8 / Chapter 2.1.5 --- Bounds Consistency --- p.9 / Chapter 2.1.6 --- Propagation-based Backtracking Search --- p.10 / Chapter 2.2 --- Disjunction --- p.12 / Chapter 2.2.1 --- Speculative --- p.12 / Chapter 2.2.2 --- Cardinality --- p.12 / Chapter 2.2.3 --- Constructive Disjunction --- p.13 / Chapter 3 --- Box Constraint Collections --- p.15 / Chapter 3.1 --- Box Constraint Collections --- p.15 / Chapter 3.2 --- Separable Constraints --- p.17 / Chapter 4 --- Building Box Constraint Collections --- p.22 / Chapter 4.1 --- The bccFinder Algorithm --- p.22 / Chapter 4.2 --- Heuristics for the bccFinder Algorithm --- p.30 / Chapter 4.2.1 --- The Order of Box Expansion --- p.30 / Chapter 4.2.2 --- The Conditions of Box Expansion --- p.35 / Chapter 5 --- Compiling BCCs into Indexicals --- p.37 / Chapter 5.1 --- Indexicals --- p.37 / Chapter 5.2 --- Basic Compilation --- p.45 / Chapter 5.3 --- Optimizing Compilation --- p.49 / Chapter 5.3.1 --- Subsumption Indexicals --- p.49 / Chapter 5.3.2 --- Union Indexicals --- p.50 / Chapter 5.4 --- Hybrid Approach --- p.71 / Chapter 6 --- Experiments --- p.76 / Chapter 7 --- Related Work --- p.93 / Chapter 8 --- Concluding Remarks --- p.98 / Chapter 8.1 --- Contributions --- p.98 / Chapter 8.2 --- Future Work --- p.99

在加權約束滿足問題中使用多元價值函數需要強大的一致相容性技術，而在多元價值函數中維護一致相容性並不是一項簡單的工作。能在多項式時間內找出多元價值函數的最少價值，而且不被投影及擴展操作所破壞，是讓該多元價值函數實用的主要條件。但是，有很多有用的多元價值函數尚未有多項式時間的算法找出其最少價值，因而未能在加權約束滿足問題中實用地使用它們。 / 我們定義了一類可被建構為整數線性規劃的多元價值函數，並稱它們為多項式線性投影安全(PLPS)價值函數。該類價值函數的最少價值能由解答整數線性規劃中找出，而這個特性並不會被投影及擴展操作所影響。線性鬆馳能讓我們找出一個最少價值的接近值，並避免了解答整數線性規劃的NP-難困難性。該最少價值的接近值能作為最少價值的下限以供維護鬆馳一致相容性概念。 / 在實踐中我們示範了使用PLPS價值函數的組合的好處。我們定義了整數多項式線性投影安全(IPLPS)價值函數作為PLPS價值函數的一個子類，並讓我們表示組合該類價值函數的好處。在一個加權約束滿足問題的一致相容性α中，我們表示了在IPLPS價值函數的組合中維護鬆馳α比在單獨的IPLPS價值函數中維護α強大。這結果可用在能在多項式時間中找出最少價值，但不能在多項式時間中找出它們的組合的最少價值的IPLPS價值函數中。基於流量投影安全(flow-based projection-safe)及可多項式分解(polynomially decomposable)價值函數的一個重要的子類屬於這一類的IPLPS價值函數。 / 在實驗中我們展示了我們的方法的可行性和效率。無論在時間或搜索空間的改進上，與現有的方法相比，在使用PLPS價值函數的組合和 IPLPS價值函數的組合時我們觀察到一個數量級的改進。 / The solving of Weighted CSP (WCSP) with global cost functions relies on powerful consistency techniques, but enforcing these consistencies on global cost functions is not a trivial task. Lee and Leung suggest that a global cost function can be used practically if we can find its minimum cost and perform projections/extensions on it in polynomial time, and at the same time projections and extensions should not destroy those conditions. However, there are many useful cost functions with no known polynomial time algorithms to compute the minimum costs yet. / We propose a special class of global cost functions which can be modeled as integer linear programs, called polynomially linear projection-safe (PLPS) cost functions. We show that their minimum cost can be computed by integer programming and this property is unaffected by projections/extensions. By linear relaxation we can avoid the possible NP-hard time taken to solve the integer programs, as the approximation of their actual minimum costs can be obtained to serve as a good lower bound in enforcing the relaxed forms of common consistencies. / We show the benets of using the conjunctions of PLPS cost functions empir-ically in terms of runtime. We introduce integral polynomially linear projection-safe (IPLPS) cost functions as a subclass of PLPS cost functions whose allow us to characterize the benets of using the conjunctions of them. Given a standard WCSP consistency α, we give theorems showing that maintaining relaxed α on a conjunction of IPLPS cost functions is stronger than maintaining α on the individual cost functions. A useful application of our method is on some IPLPS global cost functions, whose minimum cost computations are tractable and yet those for their conjunctions are not. We show that an important subclass of flow-based projection-safe and polynomially decomposable cost functions falls into this category. / Experiments are conducted to demonstrate the feasibility and efciency of our framework. We observe orders of magnitude in runtime and search space improvements by using the conjunctions of PLPS and IPLPS cost functions with relaxed consistencies when compared with the existing approaches. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Shum, Yu Wai. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 87-92). / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Weighted Constraint Satisfaction Problems --- p.2 / Chapter 1.2 --- Motivation and Goal --- p.2 / Chapter 1.3 --- Outline of the Thesis --- p.4 / Chapter 2 --- Related Work --- p.6 / Chapter 2.1 --- Soft Constraint Frameworks --- p.6 / Chapter 2.2 --- Integer Linear Programming --- p.8 / Chapter 2.3 --- Global Cost Functions in WCSP --- p.8 / Chapter 3 --- Background --- p.11 / Chapter 3.1 --- Weighted Constraint Satisfaction Problems --- p.11 / Chapter 3.1.1 --- Branch and Bound Search --- p.14 / Chapter 3.1.2 --- Local consistencies in WCSP --- p.15 / Chapter 3.1.3 --- Global Cost Functions --- p.30 / Chapter 3.2 --- Integer Linear Programming --- p.31 / Chapter 4 --- Polynomially Linear Projection-Safe Cost Functions --- p.33 / Chapter 4.1 --- Non-tractable Global Cost Functions in WCSPs --- p.34 / Chapter 4.2 --- Polynomially Linear Projection-Safe Cost Functions --- p.37 / Chapter 4.3 --- Relaxed Consistencies on Polynomially Linear Projection-Safe Cost Functions --- p.44 / Chapter 4.4 --- Conjoining Polynomially Linear Projection-Safe Cost Functions --- p.50 / Chapter 4.5 --- Modeling Global Cost Functions as Polynomially Linear Projection- Safe Cost Functions --- p.53 / Chapter 4.5.1 --- The SOFT SLIDINGSUM{U+1D48}{U+1D52}{U+1D9C} Cost Function --- p.53 / Chapter 4.5.2 --- The SOFT EGCC{U+1D5B}{U+1D43}{U+02B3} Cost Function --- p.54 / Chapter 4.5.3 --- The SOFT DISJUNCTIVE/CUMULATIVE Cost Function --- p.56 / Chapter 4.6 --- Implementation Issues --- p.59 / Chapter 4.7 --- Experimental Results --- p.60 / Chapter 4.7.1 --- Generalized Car Sequencing Problem --- p.62 / Chapter 4.7.2 --- Magic Series Problem --- p.63 / Chapter 4.7.3 --- Weighted Tardiness Scheduling Problem --- p.65 / Chapter 5 --- Integral Polynomially Linear Projection-Safe Cost Functions --- p.68 / Chapter 5.1 --- Integral Polynomially Linear Projection-Safe Cost Functions --- p.69 / Chapter 5.2 --- Conjoining Global Cost Functions as IPLPS --- p.72 / Chapter 5.3 --- Experimental Results --- p.76 / Chapter 5.3.1 --- Car Sequencing Problem --- p.77 / Chapter 5.3.2 --- Examination Timetabling Problem --- p.78 / Chapter 5.3.3 --- Fair Scheduling --- p.79 / Chapter 5.3.4 --- Comparing WCSP Approach with Integer Linear programming Approach --- p.81 / Chapter 6 --- Conclusions --- p.83 / Chapter 6.1 --- Contributions --- p.83 / Chapter 6.2 --- Future Work --- p.85 / Bibliography --- p.87

No description available.

by Wang Jun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 82-86). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- The polynomial zero-one programming problem --- p.2 / Chapter 1.3 --- Motivation --- p.3 / Chapter 1.4 --- Thesis outline --- p.4 / Chapter 2 --- Literature Survey --- p.6 / Chapter 2.1 --- Lawler and Bell's method --- p.7 / Chapter 2.2 --- The covering relaxation algorithm for polynomial zero-one pro- gramming --- p.8 / Chapter 2.3 --- The method of reducing polynomial integer problems to linear zero- one problems --- p.9 / Chapter 2.4 --- Pseudo-boolean programming --- p.11 / Chapter 2.5 --- The Balasian-based algorithm for polynomial zero-one programming --- p.12 / Chapter 2.6 --- The hybrid algorithm for polynomial zero-one programming --- p.12 / Chapter 3 --- The Balasian-based Algorithm --- p.14 / Chapter 3.1 --- The additive algorithm for linear zero-one programming --- p.15 / Chapter 3.2 --- Some notations and definitions referred to the Balasian-based al- gorithm --- p.17 / Chapter 3.3 --- Identification of all the feasible solutions to the master problem --- p.18 / Chapter 3.4 --- Consistency check of the feasible partial solutions --- p.19 / Chapter 4 --- The p-norm Surrogate Constraint Method --- p.21 / Chapter 4.1 --- Introduction --- p.21 / Chapter 4.2 --- Numerical example --- p.23 / Chapter 5 --- The P-norm Surrogate-constraint Algorithm --- p.26 / Chapter 5.1 --- Main ideas --- p.26 / Chapter 5.2 --- The standard form of the polynomial zero-one programming problem --- p.27 / Chapter 5.3 --- Definitions and notations --- p.29 / Chapter 5.3.1 --- Partial solution in x --- p.29 / Chapter 5.3.2 --- Free term --- p.29 / Chapter 5.3.3 --- Completion --- p.29 / Chapter 5.3.4 --- Feasible partial solution --- p.30 / Chapter 5.3.5 --- Consistent partial solution --- p.30 / Chapter 5.3.6 --- Partial solution in y --- p.30 / Chapter 5.3.7 --- Free variable --- p.31 / Chapter 5.3.8 --- Augmented solution in x --- p.31 / Chapter 5.4 --- Solution concepts --- p.33 / Chapter 5.4.1 --- Fathoming --- p.33 / Chapter 5.4.2 --- Backtracks --- p.41 / Chapter 5.4.3 --- Determination of the optimal solution in y --- p.42 / Chapter 5.5 --- Solution algorithm --- p.42 / Chapter 6 --- Numerical Examples --- p.46 / Chapter 6.1 --- Solution process by the new algorithm --- p.46 / Chapter 6.1.1 --- Example 5 --- p.46 / Chapter 6.1.2 --- Example 6 --- p.57 / Chapter 6.2 --- Solution process by the Balasian-based algorithm --- p.61 / Chapter 6.3 --- Comparison between the p-norm surrogate constraint algorithm and the Balasian-based algorithm --- p.71 / Chapter 7 --- Application to the Set Covering Problem --- p.74 / Chapter 7.1 --- The set covering problem --- p.74 / Chapter 7.2 --- Solving the set covering problem by using the new algorithm . .。 --- p.75 / Chapter 8 --- Conclusions and Future Work --- p.80 / Bibliography --- p.82

Lic.-avh. Västerås : Mälardalens högskola, 2004. / S. 129-136: Bibliografi.

Constraint Programming is a powerful technique for solving large-scale combinatorial (optimisation) problems. However, it is often inaccessible to users without expert knowledge in the area, precluding the wide-spread use of Constraint Programming techniques. This thesis addresses this issue in three main contributions. First, we propose a simple ‘model-and-solve’ approach, consisting of a framework where the user formulates a solver-independent problem model, which is then automatically tailored to the input format of a selected constraint solver (a process similar to compiling a high-level modelling language to machine code). The solver is then executed on the input, solver, and solutions (if they exist) are returned to the user. This allows the user to formulate constraint models without requiring any particular background knowledge of the respective solver and its solving technique. Furthermore, since the framework can target several solvers, the user can explore different types of solvers. Second, we extend the tailoring process with model optimisations that can compensate for a wide selection of poor modelling choices that novices (and experts) in Constraint Programming often make and hence result in redundancies. The elimination of these redundancies by the proposed optimisation techniques can result in solving time speedups of over an order of magnitude, in both naive and expert models. Furthermore, the optimisations are particularly light-weight, adding negligible overhead to the overall translation process. The third contribution is the implementation of this framework in the tool TAILOR, that currently translates 2 different solver-independent modelling languages to 3 different solver formats and is freely available online. It performs almost all optimisation techniques that are proposed in this thesis and demonstrates its significance in our empirical analysis. In summary, this thesis presents a framework that facilitates modelling for both experts and novices: problems can be formulated in a clear, high-level fashion, without requiring any particular background knowledge about constraint solvers and their solving techniques, while (sometimes naturally occurring) redundancies in the model are eliminated for practically no additional cost, improving the respective model in solving performance by up to an order of magnitude.

by Hui Kau Cheung Henry. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 107-112). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgments --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.1 / Chapter 1.2 --- Organizations of the Thesis --- p.2 / Chapter 2 --- Background --- p.4 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.4 / Chapter 2.1.1 --- Local Consistency Algorithm --- p.5 / Chapter 2.1.2 --- Backtracking Solver --- p.8 / Chapter 2.1.3 --- The Branch-and-Bound Algorithm --- p.10 / Chapter 2.2 --- Over-constrained Problems --- p.14 / Chapter 2.2.1 --- Weighted Constraint Satisfaction Problems --- p.15 / Chapter 2.2.2 --- Possibilistic Constraint Satisfaction Problems --- p.15 / Chapter 2.2.3 --- Fuzzy Constraint Satisfaction Problems --- p.16 / Chapter 2.2.4 --- Partial Constraint Satisfaction Problems --- p.17 / Chapter 2.2.5 --- Semiring-Based Constraint Satisfaction Problems --- p.18 / Chapter 2.2.6 --- Valued Constraint Satisfaction Problems --- p.22 / Chapter 2.3 --- The Theory of Constraint Hierarchies --- p.23 / Chapter 2.4 --- Related Work --- p.26 / Chapter 2.4.1 --- An Incremental Hierarchical Constraint Solver --- p.28 / Chapter 2.4.2 --- Transforming Constraint Hierarchies into Ordinary Con- straint System --- p.29 / Chapter 2.4.3 --- The SCSP Framework --- p.30 / Chapter 2.4.4 --- The DeltaStar Algorithm --- p.32 / Chapter 2.4.5 --- A Plug-In Architecture of Constraint Hierarchy Solvers --- p.34 / Chapter 3 --- Local Consistency in Constraint Hierarchies --- p.36 / Chapter 3.1 --- A Reformulation of Constraint Hierarchies --- p.37 / Chapter 3.1.1 --- Error Indicators --- p.37 / Chapter 3.1.2 --- A Reformulation of Comparators --- p.38 / Chapter 3.1.3 --- A Reformulation of Solution Set --- p.40 / Chapter 3.2 --- Local Consistency in Classical CSPs --- p.41 / Chapter 3.3 --- Local Consistency in SCSPs --- p.42 / Chapter 3.4 --- Local Consistency in CHs --- p.46 / Chapter 3.4.1 --- The Operations of Error Indicator --- p.47 / Chapter 3.4.2 --- Constraint Hierarchy k-Consistency --- p.49 / Chapter 3.4.3 --- A Comparsion between CHAC and PAC --- p.50 / Chapter 3.4.4 --- The CHAC Algorithm --- p.52 / Chapter 3.4.5 --- Time and Space Complexities of the CHAC Algorithm --- p.53 / Chapter 3.4.6 --- Correctness of the CHAC Algorithm --- p.56 / Chapter 4 --- A Consistency-Based Finite Domain Constraint Hierarchy Solver --- p.59 / Chapter 4.1 --- The Branch-and-Bound CHAC Solver --- p.59 / Chapter 4.2 --- Correctness of the Branch-and-Bound CHAC Solver --- p.61 / Chapter 4.3 --- An Example Execution Trace --- p.64 / Chapter 4.4 --- Experiments and Results --- p.66 / Chapter 4.4.1 --- Experimental Setup --- p.68 / Chapter 4.4.2 --- The First Experiment --- p.71 / Chapter 4.4.3 --- The Second Experiment --- p.94 / Chapter 5 --- Concluding Remarks --- p.103 / Chapter 5.1 --- Summary and Contributions --- p.103 / Chapter 5.2 --- Future Work --- p.104 / Bibliography --- p.107