Return to search

A lagrangian reconstruction of a class of local search methods.

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

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_322368
Date January 1998
ContributorsChoi, Mo Fung Kenneth., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, bibliography
Formatprint, x, 112 leaves ; 30 cm.
RightsUse 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.0017 seconds