by Choi Mo Fung Kenneth. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 105-112). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.2 / Chapter 1.2 --- Constraint Satisfaction Techniques --- p.2 / Chapter 1.3 --- Motivation of the Research --- p.4 / Chapter 1.4 --- Overview of the Thesis --- p.5 / Chapter 2 --- Related Work --- p.7 / Chapter 2.1 --- Min-conflicts Heuristic --- p.7 / Chapter 2.2 --- GSAT --- p.8 / Chapter 2.3 --- Breakout Method --- p.8 / Chapter 2.4 --- GENET --- p.9 / Chapter 2.5 --- E-GENET --- p.9 / Chapter 2.6 --- DLM --- p.10 / Chapter 2.7 --- Simulated Annealing --- p.11 / Chapter 2.8 --- Genetic Algorithms --- p.12 / Chapter 2.9 --- Tabu Search --- p.12 / Chapter 2.10 --- Integer Programming --- p.13 / Chapter 3 --- Background --- p.15 / Chapter 3.1 --- GENET --- p.15 / Chapter 3.1.1 --- Network Architecture --- p.15 / Chapter 3.1.2 --- Convergence Procedure --- p.18 / Chapter 3.2 --- Classical Optimization --- p.22 / Chapter 3.2.1 --- Optimization Problems --- p.22 / Chapter 3.2.2 --- The Lagrange Multiplier Method --- p.23 / Chapter 3.2.3 --- Saddle Point of Lagrangian Function --- p.25 / Chapter 4 --- Binary CSP's as Zero-One Integer Constrained Minimization Prob- lems --- p.27 / Chapter 4.1 --- From CSP to SAT --- p.27 / Chapter 4.2 --- From SAT to Zero-One Integer Constrained Minimization --- p.29 / Chapter 5 --- A Continuous Lagrangian Approach for Solving Binary CSP's --- p.33 / Chapter 5.1 --- From Integer Problems to Real Problems --- p.33 / Chapter 5.2 --- The Lagrange Multiplier Method --- p.36 / Chapter 5.3 --- Experiment --- p.37 / Chapter 6 --- A Discrete Lagrangian Approach for Solving Binary CSP's --- p.39 / Chapter 6.1 --- The Discrete Lagrange Multiplier Method --- p.39 / Chapter 6.2 --- Parameters of CSVC --- p.43 / Chapter 6.2.1 --- Objective Function --- p.43 / Chapter 6.2.2 --- Discrete Gradient Operator --- p.44 / Chapter 6.2.3 --- Integer Variables Initialization --- p.45 / Chapter 6.2.4 --- Lagrange Multipliers Initialization --- p.46 / Chapter 6.2.5 --- Condition for Updating Lagrange Multipliers --- p.46 / Chapter 6.3 --- A Lagrangian Reconstruction of GENET --- p.46 / Chapter 6.4 --- Experiments --- p.52 / Chapter 6.4.1 --- Evaluation of LSDL(genet) --- p.53 / Chapter 6.4.2 --- Evaluation of Various Parameters --- p.55 / Chapter 6.4.3 --- Evaluation of LSDL(max) --- p.63 / Chapter 6.5 --- Extension of LSDL --- p.66 / Chapter 6.5.1 --- Arc Consistency --- p.66 / Chapter 6.5.2 --- Lazy Arc Consistency --- p.67 / Chapter 6.5.3 --- Experiments --- p.70 / Chapter 7 --- Extending LSDL for General CSP's: Initial Results --- p.77 / Chapter 7.1 --- General CSP's as Integer Constrained Minimization Problems --- p.77 / Chapter 7.1.1 --- Formulation --- p.78 / Chapter 7.1.2 --- Incompatibility Functions --- p.79 / Chapter 7.2 --- The Discrete Lagrange Multiplier Method --- p.84 / Chapter 7.3 --- A Comparison between the Binary and the General Formulation --- p.85 / Chapter 7.4 --- Experiments --- p.87 / Chapter 7.4.1 --- The N-queens Problems --- p.89 / Chapter 7.4.2 --- The Graph-coloring Problems --- p.91 / Chapter 7.4.3 --- The Car-Sequencing Problems --- p.92 / Chapter 7.5 --- Inadequacy of the Formulation --- p.94 / Chapter 7.5.1 --- Insufficiency of the Incompatibility Functions --- p.94 / Chapter 7.5.2 --- Dynamic Illegal Constraint --- p.96 / Chapter 7.5.3 --- Experiments --- p.97 / Chapter 8 --- Concluding Remarks --- p.100 / Chapter 8.1 --- Contributions --- p.100 / Chapter 8.2 --- Discussions --- p.102 / Chapter 8.3 --- Future Work --- p.103 / Bibliography --- p.105
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_322368 |
| Date | January 1998 |
| Contributors | Choi, Mo Fung Kenneth., 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 | print, x, 112 leaves ; 30 cm. |
| 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.0024 seconds