iterative-forward-search: An IFS constraint solver

[ constraints, library, mit ] [ Propose Tags ]

An implementation of the IFS contraint satisfaction algorithm


[Skip to Readme]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log Changelog.md
Dependencies base (>=4.7 && <5), containers (<0.7), deepseq (<1.5), fingertree (<0.2), hashable (<1.4), random (<1.2), time (<1.10), transformers (<0.6), unordered-containers (<0.3) [details]
License MIT
Copyright Copyright (c) Michael B. Gale and Oscar Harris
Author Michael B. Gale and Oscar Harris
Maintainer m.gale@warwick.ac.uk
Category Constraints, Library
Home page https://github.com/fpclass/iterative-forward-search#readme
Bug tracker https://github.com/fpclass/iterative-forward-search/issues
Source repo head: git clone https://github.com/fpclass/iterative-forward-search
Uploaded by OscarH at 2021-07-29T10:01:52Z
Distributions NixOS:0.1.0.0
Downloads 57 total (1 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2021-07-29 [all 1 reports]

Readme for iterative-forward-search-0.1.0.0

[back to package description]

Iterative Forward Search

MIT CI stackage-nightly iterative-forward-search

This library implements a contraint solver via the iterative forward search algorithm. It also includes a helper module specifically for using the algorithm to timetable events.

Usage

To use the CSP solver first create a CSP value which describes your CSP, for example

csp :: CSP Solution
csp = MkCSP {
    cspVariables = IS.fromList [1,2,3],
    cspDomains = IM.fromList [(1, [1, 2, 3]), (2, [1, 2, 4]), (3, [4, 5, 6])],
    cspConstraints = [ (IS.fromList [1, 2], \a -> IM.lookup 1 a != IM.lookup 2 a)
                     , (IS.fromList [2, 3], \a -> IM.lookup 2 a >= IM.lookup 3 a)
                     ],
    cspRandomCap = 30, -- 10 * (# of variables) is a reasonable default
    cspTermination = defaultTermination
}

This example represents a CSP with 3 variables, 1, 2 and 3, where variable 1 has domain [1, 2, 3], variable 2 has domain [1, 2, 4], and variable 3 has domain [4, 5, 6]. The contraints are that variable 1 is not equal to variable 2, and variable 2 is at least as big as variable 3. It uses the default termination condition, and performs 30 iterations before we select variables randomly.

You can then find a solution simply by evaluating ifs csp, which will perform iterations till the given termination function returns a Just value.

Timetabling

The toCSP function in Data.IFS.Timetable takes a mapping from slot IDs to intervals, a hashmap of event IDs to the person IDs involved, and a map of person IDs to the slots where they are unavailable and generates a CSP which can then be solved with ifs. For example:

slotMap :: IntMap (Interval UTCTime)
slotMap = IM.fromList [(1, eventTime1), (2, eventTime2), (3, eventTime3)]

events :: HashMap Int [person]
events = HM.fromList [(1, [user1, user2]), (2, [user1])]

unavailability :: HashMap person (Set Int)
unavailability = HM.fromList [(user1, S.empty), (user2, S.fromList [1,3])]

csp :: CSP r
csp = toCSP slotMap events unavailability defaultTermination

This will generate a CSP that creates a mapping from the events 1 and 2 to the time slots 1, 2 and 3.

Limitations

  • Variables and values must be integers
  • Only hard constraints are supported