• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 137
  • 28
  • 14
  • 11
  • 5
  • 5
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 204
  • 204
  • 95
  • 85
  • 48
  • 47
  • 47
  • 32
  • 32
  • 32
  • 31
  • 28
  • 20
  • 19
  • 15
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Consistency techniques for linear global cost functions in weighted constraint satisfaction.

January 2012 (has links)
在加權約束滿足問題中使用多元價值函數需要強大的一致相容性技術,而在多元價值函數中維護一致相容性並不是一項簡單的工作。能在多項式時間內找出多元價值函數的最少價值,而且不被投影及擴展操作所破壞,是讓該多元價值函數實用的主要條件。但是,有很多有用的多元價值函數尚未有多項式時間的算法找出其最少價值,因而未能在加權約束滿足問題中實用地使用它們。 / 我們定義了一類可被建構為整數線性規劃的多元價值函數,並稱它們為多項式線性投影安全(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
2

Box constraint collections for adhoc constraints.

January 2003 (has links)
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
3

Maintaining soft arc consistencies in BNB-ADOPT⁺ during search for distributed constraint optimization problems. / CUHK electronic theses & dissertations collection

January 2013 (has links)
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.
4

Constraint programming on infinite data streams. / CUHK electronic theses & dissertations collection

January 2013 (has links)
在日常生活中,我們經常會接觸到資料序列。例如機器所作出的每一個動作、模擬下的每一個狀態或是琴譜上的每一個音符,都是各種資料序列。當事情隨時間而不斷產生變化時,這些資料序列中便會有無限多個的資料。一般而言,許多問題都可建模為有限定義域的約束滿足問題。可是對於一些問題中有隨時間而產生變化的量值,在建模時便會面對很多困難。當這些問題被建模為約束滿足問題時,為了配合有限的定義域,我們通常只能把問題限制於一段固定的時間間隔中。然而,在許多情況下,很多有用的資訊會因我們的限制而流失。隨時間而變化的數值猶如一串無窮無盡的資料流。我們為此提出對無限資料串流作約束編程。無限長的資料串流使得在表示、處理和推理時,都產生一定的難度。我們設計了一套建模語育,當中包括用於資料串流的運算子。我們針對兩類資料串流集合:一些具有最終重覆樣式的串流干日一些可構成ω-正規語育的串流。根據這兩類資料串流集合的特性,我們提出兩種求解方法。當問題涉及具有最終重覆樣式的串流時,我們會把問題分割成一系列無限個有限定義域的子問題,並把子問題逐一求解出來。而當問題的所有解可構成ω-正規語言時,我們會以搜尋樹來求解,並在過程中規避一些相等於己搜尋的空間。以這方法得出的搜尋圖,其形狀同構於用以表達所有解的自動機。同時,我們亦透過定義從最終重覆樣式的串流中得出偏好值的函數,以便對無限資料串流作約束優化。在求解中藉由執行一致性概念,我們可以減少搜尋空間。我們實作了一個求解程式,用以把問題從建模語言中建立模形,並且求得解答。從一些以模擬問題及生產音樂的實驗可以印證,我們所提出對無限資料串流作約束編程的建模及解決方法的可行性。 / 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
5

Utilizing cardinality and variety information in multiset variables in constraint programming. / CUHK electronic theses & dissertations collection

January 2013 (has links)
在約束滿足問題中使用集合變量時,一般會利用集合範團相容算法結合基數推理來進行求解。對比單獨運用集合範團相容算法產生更多的剪枝。多重集合變量是集合變量的推廣,同一個元素可以在一個多重集合中出現多次。在本論文中,我們先把基數推理運用到多重集合變量上。男外,我們提出在建模時把多重集合的品種(即不同元素的數量)一同考慮,使模型能更具體地把問題表達出來,以加強約束傳播能力。為此,我們推論出一系列有關多重集合的品種推理規則。我們還演示了如何在一些常見的約束上運用品種推理。在子集範圍的表示方法中,一些如變量的長度因素(基數)和字典序的位置的重要訊息一概都被忽略,而這些訊息往往在求解的過程中能增加約束傳播能力。因此,按照集合變量的長度法表示方法,我們為多重集合變量提供八種以字典序為基礎的表示方法。多重集合變量中的域會按照不同的字典序,以全序關係順序排列起來。實驗結果表明,子集範團表示方法結合基數推理和品種推理,可以有效地減少問題的搜索空間,從而提升包含多重集合變量的約束滿足問題的求解效率。對於某些問題,子集範圍表示方法和以字典序為基礎的表示方法相比,後者更能提高修剪的效果和減少求解時所需要的運行時間。 / 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
6

Improving backtrack search : three case studies of localized dynamic hybridization

El-Sakkout, Hani January 1999 (has links)
No description available.
7

The P-norm surrogate-constraint algorithm for polynomial zero-one programming.

January 1999 (has links)
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
8

Design and implementation of a graph-based constraint model for local search /

Bohlin, Markus. January 2004 (has links) (PDF)
Lic.-avh. Västerås : Mälardalens högskola, 2004. / S. 129-136: Bibliografi.
9

Hybrid algorithms for solving routing problems

Guimarans Serrano, Daniel 27 July 2012 (has links)
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.
10

A Computational Study of Problems in Sports

Russell, Tyrel Clinton January 2010 (has links)
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.

Page generated in 0.1633 seconds