Search

Combinatorial problems are believed to be hard in general, most of them are at least NPcomplete. Constraint-based approaches employ some convenient and generic techniques to solve these problems. These approaches use basic de nitons to model and wellde ned constraints to represent a problem. Although these approaches produce good results for smaller instances, for large-sized problems these do not perform so well. In this case, problem speci c information can help to increase the scalability of these approaches. Thus in this research, our focus is to nd out theoretically proven and heuristically promising properties that goes beyond the basic de nition of a problem. These properties help to model the problem e ciently and to reduce the e ective search space of a problem. Also, during search these properties can be used as auxiliary or streamlined constraint to boost the e ciency of a search algorithm. These properties along with e cient data structures and modern constraint-based techniques can be used to handle challenging combinatorial problems. The e ectiveness of these techniques is shown throughout this thesis by solving several combinatorial problems, such as optimal Golomb rulers, all-interval series and propositional satis ability. Finding optimal Golomb rulers is an extremely challenging combinatorial problem. Different approaches have been used so far to handle this problem. In this thesis, we provide tight upper bounds for Golomb ruler marks and present symmetry-based domain reduction technique. Using these along with tabu and con guration checking meta-heuristics, we then develop a constraint-based multi-point local search algorithm to perform a satisfaction search for optimal Golomb rulers of speci ed length. We then present an algorithm to perform an optimisation search that minimises the length of a Golomb ruler using the satisfaction search repeatedly. Experimental results demonstrate that our algorithms perform signi cantly better than the existing state-of-the-art algorithms. All-interval series is a standard benchmark problem for constraint satisfaction search. Di erent approaches have been used to date to generate all the solutions of this problem but the search space that must be explored still remains huge. In this thesis, we present a constraint-directed backtracking-based tree search algorithm that performs e cient lazy checking rather than immediate constraint propagation. Moreover, we prove several key properties of all-interval series that help to reduce the search space signi cantly. The reduced search space essentially results into fewer backtracking. We also present scalable parallel versions of our algorithm that can exploit the advantages of having multi-core processors and even multiple computer systems. Experimental results show that our new algorithm exhibits better performance than the satis ability-based state-of-the-art approach for this problem. The propositional satis ability (SAT) problem is one of the most studied combinatorial problems in computer science. In recent years, local search approaches have become one of the most e ective techniques in solving these SAT problems. In this research, our focus is to exploit the hidden structures of SAT problems in local search. These structures are generated in the form of logic gates. Due to the detection of gates, both the number of independent variables and external gates decreases. Thus the search space becomes narrower than before. But in some cases, the number of external gates or the number of independent variables may become too few to guide the search e ciently. In these cases, detecting only few but not all types of gates will actually perform better. Thus in this research, we investigate the e ect of detecting only the basic gates and also all types of gates. Then a dependency lattice is created to propagate the value of the independent variables. However, detection of gates may led to the problem of cycling in the dependency lattice. A new mechanism is proposed to remove those cycles as well. Moreover, we propose a new stagnation recovery technique to handle the cycling problem of local search. The experimental study on structured benchmarks shows that our new approach signi cantly outperforms the corresponding CNF-based implementations.