| 1. |
- Bohlin, Markus
(author)
-
Constraint satisfaction by local search
- 2002. - 1
-
Reports (other academic/artistic)abstract
- The constraint satisfaction problem and its derivate, the propositional satisfiability problem (SAT), are fundamental problems in computing theory and mathematical logic. SAT was the first proved NP-complete problem, and although complete algorithms have been dominating the constraint satisfaction field, incomplete approaches based on local search has been successful the last ten years. In this report we give a general framework for constraint satisfaction using local search as well as an different techniques to improve this basic local search framework. We also give an overview of algorithms for problems of constraint satisfaction and optimization using heuristics, and discuss hybrid methods that combine complete methods for constraint satisfaction with local search techniques.
|
|
| 2. |
|
|
| 3. |
- Bohlin, Markus, et al.
(author)
-
Designing Global Scheduling Constraints for Local Search: A Generic Approach
- 2002. - 1
-
Reports (other academic/artistic)abstract
- In this work we present a novel method to automate the computation of global constraints cost for local search. The method is based on the representation of a global constraints as graph properties on a binary constraint network. This formulation simplifies the implementation of global constraints in local search, and provides a cost that can be readily compared to one obtained for subproblems using binary constraints exclusively. The cost obtained can be efficiently updated during the search using incremental methods. The representation of a global constraint as outlined above can also be used for generation of suitable neighborhoods for the constraint. This is done using simple repair functions applied on the elementary constraints in the global constraint graph. We show the usability of our approach by presenting formulations of global constraints in non-overlapping and cumulative scheduling.
|
|
| 4. |
- Bohlin, Markus, et al.
(author)
-
Redesign of the Oz Compiler
- 2002. - 1
-
Reports (other academic/artistic)abstract
- This master of science thesis describes a new design and its implementation for an Oz compiler. The project is based on the existing Oz compiler. The new compiler is designed more modular, with separate software components that can be replaced and modified locally. A prototype has been implemented, but further development is necessary. We give an overview of the language Oz, its features and the underlying calculus. The features of Oz regarding object orientation, functional programming, logic and constraint programming are also discussed. The liveness analysis and register allocation problems in general and regarding Oz specific compilers are analyzed, together with current and future optimizations suitable for the Mozart platform. The design of the new compiler and information about the old one is presented, and future work regarding the compiler, optimizations, and analysis phases is discussed. Appendices describing the interfaces between the phases of the compiler is included, together with documentation regarding the internal code formats used.
|
|
| 5. |
|
|
| 6. |
|
|
