Computing and Information Systems - Research Publications

Permanent URI for this collection

http://hdl.handle.net/11343/350

Filters

2007 10
Reset filters

Settings
Statistics
Citations
Start date: 2007 × End date: 2007 × Author: Stuckey, Peter ×

Search Results

Now showing 1 - 10 of 10
  • Item
    Thumbnail Image
    Observable confluence for constraint handling rules
    Duck, GJ ; Stuckey, PJ ; Sulzmann, M ; Dahl, V ; Niemela, I (SPRINGER-VERLAG BERLIN, 2007)
  • Item
    Thumbnail Image
    Propagating Dense Systems of Integer Linear Equations
    Feydy, T ; Stuckey, PJ (ASSOC COMPUTING MACHINERY, 2007)
  • Item
    Thumbnail Image
    Propagation = Lazy Clause Generation
    OHRIMENKO, O. ; STUCKEY, P. ; CODISH, M. (Springer Verlag, 2007)
  • Item
    Thumbnail Image
    Practical preference relations for large data sets
    Ross, KA ; Stuckey, PJ ; Marian, A (IEEE, 2007)
  • Item
    Thumbnail Image
    MiniZinc: Towards a Standard CP Modelling Language
    NETHERCOTE, N. ; STUCKEY, P. ; BECKET, R. ; BRAND, S. ; DUCK, G. ; TACK, G. (Springer Verlag, 2007)
  • Item
    Thumbnail Image
    Minimum cardinality matrix decomposition into consecutive-ones matrices: CP and IP approaches
    Baatar, D ; Boland, N ; Brand, S ; Stuckey, PJ ; VanHentenryck, P ; Wolsey, L (SPRINGER-VERLAG BERLIN, 2007)
  • Item
    Thumbnail Image
    Understanding functional dependencies via constraint handling rules
    Sulzmann, M ; Duck, GJ ; Peyton-Jones, S ; Stuckey, PJ (CAMBRIDGE UNIV PRESS, 2007-01)
    Abstract Functional dependencies are a popular and useful extension to Haskell style type classes. We give a reformulation of functional dependencies in terms of Constraint Handling Rules (CHRs). In previous work, CHRs have been employed for describing user-programmable type extensions in the context of Haskell style type classes. Here, we make use of CHRs to provide for the first time a concise result that under some sufficient conditions, functional dependencies allow for sound, complete and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions and suggest several sound extensions of functional dependencies. Our results allow for a better understanding of functional dependencies and open up the opportunity for new applications.
  • Item
    Thumbnail Image
    The island confinement method for reducing search space in local search methods
    Fang, H ; Kilani, Y ; Lee, JHM ; Stuckey, PJ (SPRINGER, 2007-12)
  • Item
    Thumbnail Image
    Dynamic programming to minimize the maximum number of open stacks
    de la Banda, MG ; Stuckey, PJ (INFORMS, 2007-01-01)
    We give a dynamic-programming solution to the problem of minimizing the maximum number of open stacks. Starting from a call-based dynamic program, we show a number of ways to improve the dynamic-programming search, preprocess the problem to simplify it, and determine lower and upper bounds. We then explore a number of search strategies for reducing the search space. The final dynamic-programming solution is, we believe, highly effective.
  • Item
    Thumbnail Image
    Removing propagation redundant constraints in redundant modeling
    Choi, CW ; Lee, JHM ; Stuckey, PJ (ASSOC COMPUTING MACHINERY, 2007)
    A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are propagation redundant and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http://www.csplib.org), how detecting and removing propagation redundant constraints in redundant modeling can speed up search by several order of magnitudes.