在加權約束滿足問題中使用多元價值函數需要強大的一致相容性技術，而在多元價值函數中維護一致相容性並不是一項簡單的工作。能在多項式時間內找出多元價值函數的最少價值，而且不被投影及擴展操作所破壞，是讓該多元價值函數實用的主要條件。但是，有很多有用的多元價值函數尚未有多項式時間的算法找出其最少價值，因而未能在加權約束滿足問題中實用地使用它們。 / 我們定義了一類可被建構為整數線性規劃的多元價值函數，並稱它們為多項式線性投影安全(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
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328445 |
| Date | January 2012 |
| Contributors | Shum, Yu Wai., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (ix, 92 leaves) : ill. |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0151 seconds