Improving Combinatorial Optimization: Extended Abstract / 3116
Geoffrey Chu

Combinatorial Optimization is an important area of computer science that has many theoretical and practical applications. In the thesis, we present important contributions to several different areas of combinatorial optimization, including nogood learning, symmetry breaking, dominance, relaxations and parallelization. We develop a new nogood learning technique based on constraint projection that allows us to exploit subproblem dominances that arise when two different search paths lead to subproblems which are identical on the remaining unfixed variables. We present a new symmetry breaking technique called SBDS-1UIP, which extends Symmetry Breaking During Search (SBDS) by using the more powerful 1UIP nogoods generated by Lazy Clause Generation (LCG) solvers. We present two new general methods for exploiting almost symmetries by modifying SBDS-1UIP and by using conditional symmetry breaking constraints. We solve the Minimization of Open Stacks Problem, the Talent Scheduling Problem (CSPLib prob039), and the Maximum Density Still Life Problem (CSPLib prob032) many orders of magnitude faster than the previous state of the art by applying various powerful techniques such as nogood learning, dynamic programming, dominance and relaxations. We present cache aware data structures for SAT solvers which allows sequential and parallel versions of SAT solvers to run more quickly. And we present a new load balancing scheme for parallel search called confidence based work stealing, which allows the parallel search to make use of the information contained in the branching heuristic.