Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 2 of 2
-
ItemImproving scheduling by learning( 2011)Scheduling problems appear in many industrial problems with different facets and requirements of a solution. A solution is a schedule of a set of activities subject to constraints such as precedence relations and resource restrictions on the maximum number of concurrent activities. This dissertation presents new deductive techniques for precedence and cumulative resource constraints in constraint programming to improve solution processes of combinatorial scheduling problems, in particular, and combinatorial problems, in general. Due to their intractability, many schedulers either solve a simplified problem or are tailored to a specific problem, but are inflexible with respect to changes in the problem statement. Constraint Programming (CP) offers a powerful framework for combinatorial problems which also tackles the demand of flexibility of changes in the problem statement due to a strict separation of problem modelling, search algorithms, and high-specialised deduction techniques. Moreover, recent advanced CP solvers such as lazy clause generation (LCG) additionally include sophisticated conflict learning technologies. Their efficiency depends, amongst other things, on reusable explanations formulated by deductive algorithms. Unit two variable per inequality (UTVPI) constraints are one of the largest integer constraint class that is solvable in polynomial time. These constraints can model precedence relations between activities. A new theoretical result about reasoning of UTVPI systems is shown, based on that, new incremental deductive algorithms are created for manipulating UTVPI constraints including satisfiability, implication, and explanation. These algorithms are asymptotically faster on sparse UTVPI systems than current algorithms. Cumulative constraints enforce resource restrictions in scheduling problems. We show how, by adding explanation to the cumulative constraint in an LCG solver, we can solve resource-constrained project scheduling problems far faster than other comparable methods. Furthermore, a complete LCG-based approach including cumulative constraints is developed for an industrial carpet cutting problem. This approach outperforms the current incomplete method on all industrial instances provided.
-
ItemImproving combinatorial optimization( 2011)Combinatorial Optimization is an important area of computer science that has many theoretical and practical applications. In this 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 unlabeled variables. On appropriate problems, this nogood learning technique provides orders of magnitude speedup compared to a base solver which does not learn nogoods. We present a new symmetry breaking technique called SBDS-1UIP, which is an extension of Symmetry Breaking During Search (SBDS). SBDS-1UIP uses symmetric versions of the 1UIP nogoods derived by Lazy Clause Generation solvers to prune symmetric parts of the search space. We show that SBDS-1UIP can exploit at least as many symmetries as SBDS, and that it is strictly more powerful on some problems, allowing us to exploit types of symmetries that no previous general symmetry breaking technique is capable of exploiting. We present two new general methods for exploiting almost symmetries (symmetries which are broken by a small number of constraints). The first is to treat almost symmetries as conditional symmetries and exploit them via conditional symmetry breaking constraints. The second is to modify SDBS-1UIP to handle almost symmetries. Both techniques are capable of producing exponential speedups on appropriate problems. We examine three reasonably well known problems: the Minimization of Open Stacks Problem, the Talent Scheduling Problem (CSPLib prob039), and the Maximum Density Still Life Problem (CSPLib prob032). By applying various powerful techniques such as nogood learning, dynamic programming, dominance and relaxations, we are able to solve these problems many orders of magnitude faster than the previous state of the art. We identify cache contention as a serious bottleneck that severely limit the amount of speedup achievable when parallelizing SAT and LCG solvers on multi-core systems. We alter the data structures used in the state of the art SAT solver MiniSat to be more cache aware, leading to a sequential SAT solver that is some 80% faster on average and a parallel SAT solver that is some 140% faster on average. We examine an important issue in parallel search that has not been properly addressed in the literature. Many work stealing schemes used for load balancing completely ignore the branching heuristic, and instead try to maximize the granularity of the work stolen. This can result in many of the processors searching in unfruitful parts of the search tree. We analyze this problem and develop a new work stealing scheme called confidence based work stealing, which partitions the work based on how strong the branching heuristic is at each node. The new parallel algorithm produced near linear or super linear speedup on all the problems we tested.