by Lui Oi Lun Irene. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 128-132). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Constraint Satisfaction Problem and Satisfiability Problem --- p.4 / Chapter 2.1 --- Constraint Programming --- p.4 / Chapter 2.2 --- Satisfiability Problem --- p.6 / Chapter 2.3 --- Methods in Solving SAT problem --- p.7 / Chapter 2.3.1 --- Davis-Putnam-Loveland Procedure --- p.7 / Chapter 2.3.2 --- SATZ by Chu-Min Li --- p.8 / Chapter 2.3.3 --- Local Search for SAT --- p.11 / Chapter 2.3.4 --- Integer Linear Programming Method for SAT --- p.12 / Chapter 2.3.5 --- Semidefinite Programming Method --- p.13 / Chapter 2.4 --- Softwares for SAT --- p.15 / Chapter 2.4.1 --- SAT01 --- p.15 / Chapter 2.4.2 --- "SATZ and SATZ213, contributed by Chu-Min Li" --- p.15 / Chapter 2.4.3 --- Others --- p.15 / Chapter 3 --- Integer Programming --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.1.1 --- Formulation of IPs and BIPs --- p.18 / Chapter 3.1.2 --- Binary Search Tree --- p.19 / Chapter 3.2 --- Methods in Solving IP problem --- p.19 / Chapter 3.2.1 --- Branch-and-Bound Method --- p.20 / Chapter 3.2.2 --- Cutting-Plane Method --- p.23 / Chapter 3.2.3 --- Duality in Integer Programming --- p.26 / Chapter 3.2.4 --- Heuristic Algorithm --- p.28 / Chapter 3.3 --- Zero-one Optimization and Continuous Relaxation --- p.29 / Chapter 3.3.1 --- Introduction --- p.29 / Chapter 3.3.2 --- The Roof Dual expressed in terms of Lagrangian Relaxation --- p.30 / Chapter 3.3.3 --- Determining the Existence of a Duality Gap --- p.31 / Chapter 3.4 --- Software for solving Integer Programs --- p.33 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.35 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.35 / Chapter 4.2 --- From m-Constrained IP Problem to Singly-Constrained IP Problem --- p.38 / Chapter 4.2.1 --- Example --- p.39 / Chapter 5 --- A Basic Branch-and-Bound Algorithm for the Zero-One Polynomial Maximization Problem --- p.42 / Chapter 5.1 --- Reason for choosing Branch-and-Bound Method --- p.42 / Chapter 5.2 --- Searching Algorithm --- p.43 / Chapter 5.2.1 --- Branch Rule --- p.44 / Chapter 5.2.2 --- Bounding Rule --- p.46 / Chapter 5.2.3 --- Fathoming Test --- p.46 / Chapter 5.2.4 --- Example --- p.47 / Chapter 6 --- Revised Bound Rule for Branch-and-Bound Algorithm --- p.55 / Chapter 6.1 --- Revised Bound Rule --- p.55 / Chapter 6.1.1 --- CPLEX --- p.57 / Chapter 6.2 --- Example --- p.57 / Chapter 6.3 --- Conclusion --- p.65 / Chapter 7 --- Revised Branch Rule for Branch-and-Bound Algorithm --- p.67 / Chapter 7.1 --- Revised Branch Rule --- p.67 / Chapter 7.2 --- Comparison between Branch Rule and Revised Branch Rule --- p.69 / Chapter 7.3 --- Example --- p.72 / Chapter 7.4 --- Conclusion --- p.73 / Chapter 8 --- Experimental Results and Analysis --- p.80 / Chapter 8.1 --- Experimental Results --- p.80 / Chapter 8.2 --- Statistical Analysis --- p.33 / Chapter 8.2.1 --- Analysis of Search Techniques --- p.83 / Chapter 8.2.2 --- Discussion of the Performance of SATZ --- p.85 / Chapter 9 --- Concluding Remarks --- p.87 / Chapter 9.1 --- Conclusion --- p.87 / Chapter 9.2 --- Suggestions for Future Research --- p.88 / Chapter A --- Searching Procedures for Solving Constraint Satisfaction Problem (CSP) --- p.91 / Chapter A.1 --- Notation --- p.91 / Chapter A.2 --- Procedures for Solving CSP --- p.92 / Chapter A.2.1 --- Generate and Test --- p.92 / Chapter A.2.2 --- Standard Backtracking --- p.93 / Chapter A.2.3 --- Forward Checking --- p.94 / Chapter A.2.4 --- Looking Ahead --- p.95 / Chapter B --- Complete Results for Experiments --- p.96 / Chapter B.1 --- Complete Result for SATZ --- p.96 / Chapter B.1.1 --- n =5 --- p.95 / Chapter B.1.2 --- n = 10 --- p.98 / Chapter B.1.3 --- n = 30 --- p.99 / Chapter B.2 --- Complete Result for Basic Branch-and-Bound Algorithm --- p.101 / Chapter B.2.1 --- n二5 --- p.101 / Chapter B.2.2 --- n = 10 --- p.104 / Chapter B.2.3 --- n = 30 --- p.107 / Chapter B.3 --- Complete Result for Revised Bound Rule --- p.109 / Chapter B.3.1 --- n = 5 --- p.109 / Chapter B.3.2 --- n = 10 --- p.112 / Chapter B.3.3 --- n = 30 --- p.115 / Chapter B.4 --- Complete Result for Revised Branch-and-Bound Algorithm --- p.118 / Chapter B.4.1 --- n = 5 --- p.118 / Chapter B.4.2 --- n = 10 --- p.121 / Chapter B.4.3 --- n = 30 --- p.124 / Bibliography --- p.128
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_323436 |
| Date | January 2001 |
| Contributors | Lui, Oi Lun Irene., Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | print, viii, 132 leaves : ill. ; 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.0022 seconds