Edge Finding Algorithm

  • Frank Hanshar

    Frank Hanshar - 2012-03-15


    First, just wanted to say thanks to the developers of this software. I really enjoy working with the software, I think it is great!

    I just have a couple small questions.

    1. For your Cumulative constraint which paper did you base you edge finding algorithm on? I notice on the scheduling problems I am working on, the search is about 2x faster with edge finding disabled. There is a relatively recent algorithm by Petr Vilim that has O(knlogn) time complexity compared to older approaches with O(n^2).

    2. When imposing a constraint in the store with consistency is there anyway to get information on why a newly added constraint conflicts with existing constraints in the store? I searched thru the API and started examining the source code but haven't found a good way as yet.

    Thanks again,

    Frank Hanshar

  • kris

    kris - 2012-03-16


    1. Our cumulative constraint has been written many years ago as one of the first constraints. The short description is provided in my paper

    Krzysztof Kuchcinski: Constraints-driven scheduling and resource assignment. ACM Trans. Design Autom. Electr. Syst. 8(3): 355-383 (2003)

    Obviously it would be nice to write a new cumulative that implements newest algorithms.

    2. You can find out which constrain failed when making consistency but it does not say which constraint or constraints conflict with the newly added constraint. It is like debugging. You may see that your program crashes but you do not see why or even where is a bug.

    You may look at Store.consistency() method and try to print currentConstraint in the part which catches exception FailException. This will show which constraint fails. There is no big point to print it during search since there is many failed constraints that cause backtracking.


  • Frank Hanshar

    Frank Hanshar - 2012-03-16


    Thank you very much for your reply. I will check out your paper.

    I am mostly concerned with figuring out constraint conflicts before search begins, when I am adding constraints to the constraint store and using store.imposeWithConsistency(currentConstraint). Imagine I add a constraint called currentConstraint and get a FailException. At this point I know the currentConstraint conflicts with other constraints, but is it possible to find which other constraint it conflicts with?

    The motivation for this is I am prototyping a scheduling engine. Sometimes resources will be overconstrained and imposing constraints with consistency is useful to detect this before the search begins (and returns no solutions).  If it is possible to identify the two (or more) constraints which conflict this information can be used to modify existing constraints.

    I will investigate you suggestion on Store.consistency(). Thanks again for your feedback.



Log in to post a comment.