logo

Monday 20th of November 2017

Latest Version

Feed Icon Sudoku Generator 0.10 stable
Release Date: 2010-04-16

Home Theses

Theses

  • Max-SAT Formalisms with Hard and Soft Constraints
     
    Research Area: Satisfiability
     
  • Design and Implementation of Exact MAX-SAT Solvers
     
    Research Area: Satisfiability
     
  • CSP problems as algorithmic benchmarks: measures, methods and models.
     
    Research Area: Constraint Programming
     

    On Computer Science research, traditionally, most efforts have been devoted

    to research hardness for the worst case of problems (proving NP completeness

    and comparing and reducing problems between them are the two

    most known). Artifcial Intelligence research, recently, has focused also on

    how some characteristics of concrete instances have dramatic effects on complexity

    and hardness while worst-case complexity remains the same. This

    has lead to focus research efforts on understanding which aspects and properties

    of problems or instances affect hardness, why very similar problems

    can require very diferent times to be solved.

    Research search based problems has been a substantial part of artificial

    intelligence research since its beginning. Big part of this research has been

    focused on developing faster and faster algorithms, better heuristics, new

    pruning techniques to solve ever harder problems. One aspect of this effort

    to create better solvers consists on benchmarking solver performance

    on selected problem sets, and, an, obviously, important part of that benchmarking

    is creating and defining new sets of hard problems.

    This two folded effort, on one hand to have at our disposal new problems,

    harder than previous ones, to test our solvers, and on the other hand, to

    obtain a deeper understanding on why such new problems are so hard, thus

    making easier to understand why some solvers outperform others, knowledge

    that can contribute towards designing and building better and faster

    algorithms and solvers.

    This work deals with designing better, that is harder and easy to generate,

    problems for CSP solvers, also usable for SAT solvers. In the first

    half of the work general concepts on hardness and CSP are introduced, including

    a complete description of the chosen problems for our study. This

    chosen problems are, Random Binary CSP Problems (BCSP), Quasi-group

    Completion Problems (QCP), Generalised Sudoku Problems (GSP), and a

    newly defined problem, Edge-Matching Puzzles (GEMP). Although BCSP

    and QCP are already well studied problems, that is not the case with GSP

    and GEMP. For GSP we will define new creation methods that ensure higher

    hardness than standard random methods. GEMP on the other hand is a

    newly formalised problem, we will define it, will provide also algorithms

    to build easily problems of tunable hardness and study its complexity and

    hardness.

    On the second part of the work we will propose and study new methods

    to increase the hardness of such problems. Providing both, algorithms to

    build harder problems and an in-depth study of the effect of such methods

    on hardness, specially on resolution time.

  • Systematic and Local Search Algorithms for Regular-SAT
     
    Research Area: Many-valued logics
     
Results 1 - 4 of 4

Joomla Template Download From Joomlatp.com Designed by: Free Joomla 1.5 Theme, ftp account. Valid XHTML and CSS.