Thesis (M.Sc. (Computing Sc.)) - Simon Fraser University, 2004. / Theses (School of Computing Science) / Simon Fraser University.

Global optimization methods can be classified into two non-overlapping classes with respect to accuracy: those with guaranteed accuracy and those without. The former are called bounding methods, the latter point methods. Bounding methods compute lower and upper bounds of function over a box and give a lower bound and an upper bound for the minimum. Point methods compute function values at points and output as the minimum the function value at a point. R. E. Moore was the first to propose the bounding method using interval arithmetic for unconstrained global optimization. The first bounding method using interval arithmetic for constrained global optimization was due to E. R. Hansen and S. Sengupta. These methods are the well known bounding methods. Since these methods use interval arithmetic, we call them interval arithmetic methods. This dissertation studies the new bounding methods that use interval constraints, which is called interval constraint methods. We prove that interval constraints is a generalization of interval arithmetic, computing an interval function in interval constraints gives the same result as in interval arithmetic. We propose a hypernarrowing algorithm using interval constraints. This algorithm produces a smaller interval result for the range of function f over a given domain than interval arithmetic. We present a generic Branch-and-Bound algorithm for unconstrained global optimization, prove the properties of the algorithm, and propose improvements on the algorithm. From this algorithm, we can obtain its interval arithmetic version and interval constraint version. We investigate the role of interval constraints in global optimization and discuss the performance and characteristics of interval arithmetic methods and interval constraint ones. Based on the Branch-and-Bound algorithm for unconstrained global optimization, we present a generic Branch-and-Bound algorithm for constrained global optimization, study the effect of Fritz-John conditions as redundant constraints and compare the interval arithmetic method for constrained optimization with the interval constraint one. / Graduate

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

Bryan Chi-ho Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 163-166). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Background --- p.4 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.4 / Chapter 2.2 --- Systematic Search --- p.5 / Chapter 2.3 --- Stochastic Search --- p.6 / Chapter 2.3.1 --- Overview --- p.6 / Chapter 2.3.2 --- GENET --- p.8 / Chapter 2.3.3 --- CSVC --- p.10 / Chapter 2.3.4 --- Adaptive Search --- p.12 / Chapter 2.4 --- Hybrid Approach --- p.13 / Chapter 3 --- Progressive Stochastic Search --- p.14 / Chapter 3.1 --- Progressive Stochastic Search --- p.14 / Chapter 3.1.1 --- Network Architecture --- p.15 / Chapter 3.1.2 --- Convergence Procedure --- p.16 / Chapter 3.1.3 --- An Illustrative Example --- p.21 / Chapter 3.2 --- Incremental Progressive Stochastic Search --- p.23 / Chapter 3.2.1 --- Network Architecture --- p.24 / Chapter 3.2.2 --- Convergence Procedure --- p.24 / Chapter 3.2.3 --- An Illustrative Example --- p.25 / Chapter 3.3 --- Heuristic Cluster Selection Strategy --- p.28 / Chapter 4 --- Experiments --- p.31 / Chapter 4.1 --- N-Queens Problems --- p.32 / Chapter 4.2 --- Permutation Generation Problems --- p.53 / Chapter 4.2.1 --- Increasing Permutation Problems --- p.54 / Chapter 4.2.2 --- Random Permutation Generation Problems --- p.75 / Chapter 4.3 --- Latin Squares and Quasigroup Completion Problems --- p.96 / Chapter 4.3.1 --- Latin Square Problems --- p.96 / Chapter 4.3.2 --- Quasigroup Completion Problems --- p.118 / Chapter 4.4 --- Random CSPs --- p.120 / Chapter 4.4.1 --- Tight Random CSPs --- p.139 / Chapter 4.4.2 --- Phase Transition Random CSPs --- p.156 / Chapter 5 --- Concluding Remarks --- p.159 / Chapter 5.1 --- Contributions --- p.159 / Chapter 5.2 --- Future Work --- p.161

Mak, Wai Keung Terrence. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 100-104). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.2 / Chapter 1.3 --- Quantified Constraint Satisfaction Problems --- p.3 / Chapter 1.4 --- Motivation and Goal --- p.4 / 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 for solving CSPs --- p.11 / Node Consistency (NC) --- p.13 / Arc Consistency (AC) --- p.14 / Searching by Maintaining Arc Consistency --- p.16 / Chapter 2.1.3 --- Constraint Optimization Problems --- p.17 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.19 / Chapter 2.2.1 --- Branch and Bound Search (B&B) --- p.23 / Chapter 2.2.2 --- Local Consistencies for WCSPs --- p.25 / Node Consistency --- p.26 / Arc Consistency --- p.28 / Chapter 2.3 --- Quantified Constraint Satisfaction Problems --- p.32 / Chapter 2.3.1 --- Backtracking Free search --- p.37 / Chapter 2.3.2 --- Consistencies for QCSPs --- p.38 / Chapter 2.3.3 --- Look Ahead for QCSPs --- p.45 / Chapter 3 --- Quantified Weighted CSPs --- p.48 / Chapter 4 --- Branch & Bound with Consistency Techniques --- p.54 / Chapter 4.1 --- Alpha-Beta Pruning --- p.54 / Chapter 4.2 --- Consistency Techniques --- p.57 / Chapter 4.2.1 --- Node Consistency --- p.62 / Overview --- p.62 / Lower Bound of A-Cost --- p.62 / Upper Bound of A-Cost --- p.66 / Projecting Unary Costs to Cθ --- p.67 / Chapter 4.2.2 --- Enforcing Algorithm for NC --- p.68 / Projection Phase --- p.69 / Pruning Phase --- p.69 / Time Complexity --- p.71 / Chapter 4.2.3 --- Arc Consistency --- p.73 / Overview --- p.73 / Lower Bound of A-Cost --- p.73 / Upper Bound of A-Cost --- p.75 / Projecting Binary Costs to Unary Constraint --- p.75 / Chapter 4.2.4 --- Enforcing Algorithm for AC --- p.76 / Projection Phase --- p.77 / Pruning Phase --- p.77 / Time complexity --- p.79 / Chapter 5 --- Performance Evaluation --- p.83 / Chapter 5.1 --- Definitions of QCOP/QCOP+ --- p.83 / Chapter 5.2 --- Transforming QWCSPs into QCOPs --- p.90 / Chapter 5.3 --- Empirical Evaluation --- p.91 / Chapter 5.3.1 --- Random Generated Problems --- p.92 / Chapter 5.3.2 --- Graph Coloring Game --- p.92 / Chapter 5.3.3 --- Min-Max Resource Allocation Problem --- p.93 / Chapter 5.3.4 --- Value Ordering Heuristics --- p.94 / Chapter 6 --- Concluding Remarks --- p.96 / Chapter 6.1 --- Contributions --- p.96 / Chapter 6.2 --- Limitations and Related Works --- p.97 / Chapter 6.3 --- Future Works --- p.99 / Bibliography --- p.100

Thesis (Ph. D.)--University of Missouri-Columbia, 1999. / Typescript. Vita. Includes bibliographical references (leaves 139-149). Also available on the Internet.

Thesis (Ph. D.)--University of Missouri-Columbia, 1999. / Typescript. Vita. Includes bibliographical references (leaves 139-149). Also available on the Internet.

Not available / text

Thesis (M.Info.Sys)--University of Wollongong, 2005. / Typescript. Includes bibliographical references: leaf 84-87.

Thesis (Ph. D.)--University of Texas at Austin, 2005. / Supervisor: Aloysius K Mok. Vita. Includes bibliographical references.