Constraint Satisfaction Problem formulation











up vote
2
down vote

favorite
1












I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.



Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var is the variable and A1, A2, A3 is an ordered sequence of valid assignments.



Requirements:




  • Each variable is assigned a value in problem.valid_assignments()

  • Each variable's first assignment is in problem.first_assignments()

  • Each variable's assignment sequence is in problem.valid_pairs() (Some assignments can't follow others)

  • Given an integer K, there can be no more than K continuous assignments where at least one is not in problem.k_assignment()

  • Every value in the given assignments list: problem.assignment must be used.


Available Constraints:





  • NValues constraint: Given a list of required_values, an upper bound and lower bound, makes sure that the number of variables whose value is in required_values is between the bounds.


  • AllDifferent constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.


  • NotEqual constraints: Given Var1, Var2, enforces: Var1 != Var2


So Far:




  • A Variable for each Var whose domain is problem.valid_assignments()

  • A Variable for each Var whose domain is problem.first_assignments()

  • A NValues constraint for each Var whose scope is [Var], required values problem.valid_assignments(Var), lower bound 0, upper bound len(domain).


Additional info:




  • The solution is a "list of assignments" as in for each Var we return [Var, A1, A2, A3] where Var is the variable assigned and A1 through A3 are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. Additionally A1, A2, A3 (aka all assignments for a Var) must obviously be in the domain of that variable. (Domains can overlap between variables).


  • valid_pairs() returns a list of tuples [(A1, A2), (A2,A3)]. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is [Var, A1, A2, A4, A3] and the valid pairs are [(A1, A2), (A2,A3)] then the solution is incorrect as (A2, A4) (A4, A3) is not in the list ((A1, A2) however is a valid pair).


  • Essentially we're looking for arc-consistency.











share|improve this question
























  • Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
    – Michael Veksler
    Nov 11 at 12:46










  • Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
    – Michael Veksler
    Nov 11 at 12:49










  • Please seed my latest edit for clarifications. @MichaelVeksler
    – Ge0rges
    Nov 11 at 20:57










  • If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
    – Michael Veksler
    Nov 11 at 21:05










  • No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
    – Ge0rges
    Nov 11 at 21:12

















up vote
2
down vote

favorite
1












I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.



Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var is the variable and A1, A2, A3 is an ordered sequence of valid assignments.



Requirements:




  • Each variable is assigned a value in problem.valid_assignments()

  • Each variable's first assignment is in problem.first_assignments()

  • Each variable's assignment sequence is in problem.valid_pairs() (Some assignments can't follow others)

  • Given an integer K, there can be no more than K continuous assignments where at least one is not in problem.k_assignment()

  • Every value in the given assignments list: problem.assignment must be used.


Available Constraints:





  • NValues constraint: Given a list of required_values, an upper bound and lower bound, makes sure that the number of variables whose value is in required_values is between the bounds.


  • AllDifferent constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.


  • NotEqual constraints: Given Var1, Var2, enforces: Var1 != Var2


So Far:




  • A Variable for each Var whose domain is problem.valid_assignments()

  • A Variable for each Var whose domain is problem.first_assignments()

  • A NValues constraint for each Var whose scope is [Var], required values problem.valid_assignments(Var), lower bound 0, upper bound len(domain).


Additional info:




  • The solution is a "list of assignments" as in for each Var we return [Var, A1, A2, A3] where Var is the variable assigned and A1 through A3 are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. Additionally A1, A2, A3 (aka all assignments for a Var) must obviously be in the domain of that variable. (Domains can overlap between variables).


  • valid_pairs() returns a list of tuples [(A1, A2), (A2,A3)]. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is [Var, A1, A2, A4, A3] and the valid pairs are [(A1, A2), (A2,A3)] then the solution is incorrect as (A2, A4) (A4, A3) is not in the list ((A1, A2) however is a valid pair).


  • Essentially we're looking for arc-consistency.











share|improve this question
























  • Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
    – Michael Veksler
    Nov 11 at 12:46










  • Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
    – Michael Veksler
    Nov 11 at 12:49










  • Please seed my latest edit for clarifications. @MichaelVeksler
    – Ge0rges
    Nov 11 at 20:57










  • If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
    – Michael Veksler
    Nov 11 at 21:05










  • No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
    – Ge0rges
    Nov 11 at 21:12















up vote
2
down vote

favorite
1









up vote
2
down vote

favorite
1






1





I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.



Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var is the variable and A1, A2, A3 is an ordered sequence of valid assignments.



Requirements:




  • Each variable is assigned a value in problem.valid_assignments()

  • Each variable's first assignment is in problem.first_assignments()

  • Each variable's assignment sequence is in problem.valid_pairs() (Some assignments can't follow others)

  • Given an integer K, there can be no more than K continuous assignments where at least one is not in problem.k_assignment()

  • Every value in the given assignments list: problem.assignment must be used.


Available Constraints:





  • NValues constraint: Given a list of required_values, an upper bound and lower bound, makes sure that the number of variables whose value is in required_values is between the bounds.


  • AllDifferent constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.


  • NotEqual constraints: Given Var1, Var2, enforces: Var1 != Var2


So Far:




  • A Variable for each Var whose domain is problem.valid_assignments()

  • A Variable for each Var whose domain is problem.first_assignments()

  • A NValues constraint for each Var whose scope is [Var], required values problem.valid_assignments(Var), lower bound 0, upper bound len(domain).


Additional info:




  • The solution is a "list of assignments" as in for each Var we return [Var, A1, A2, A3] where Var is the variable assigned and A1 through A3 are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. Additionally A1, A2, A3 (aka all assignments for a Var) must obviously be in the domain of that variable. (Domains can overlap between variables).


  • valid_pairs() returns a list of tuples [(A1, A2), (A2,A3)]. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is [Var, A1, A2, A4, A3] and the valid pairs are [(A1, A2), (A2,A3)] then the solution is incorrect as (A2, A4) (A4, A3) is not in the list ((A1, A2) however is a valid pair).


  • Essentially we're looking for arc-consistency.











share|improve this question















I am given the following requirements which need to be formulated into a CSP problem by defining a set of variables, and a set of constraints over those variables. However I'm having trouble formulating the constraints and variables for my problem.



Some info:
The solution to the problem is a list of assignments: [Var, A1, A2, A3]
where Var is the variable and A1, A2, A3 is an ordered sequence of valid assignments.



Requirements:




  • Each variable is assigned a value in problem.valid_assignments()

  • Each variable's first assignment is in problem.first_assignments()

  • Each variable's assignment sequence is in problem.valid_pairs() (Some assignments can't follow others)

  • Given an integer K, there can be no more than K continuous assignments where at least one is not in problem.k_assignment()

  • Every value in the given assignments list: problem.assignment must be used.


Available Constraints:





  • NValues constraint: Given a list of required_values, an upper bound and lower bound, makes sure that the number of variables whose value is in required_values is between the bounds.


  • AllDifferent constraint: Given a set of variables, enforces their inequality. That is no two variables in the set are equal.


  • NotEqual constraints: Given Var1, Var2, enforces: Var1 != Var2


So Far:




  • A Variable for each Var whose domain is problem.valid_assignments()

  • A Variable for each Var whose domain is problem.first_assignments()

  • A NValues constraint for each Var whose scope is [Var], required values problem.valid_assignments(Var), lower bound 0, upper bound len(domain).


Additional info:




  • The solution is a "list of assignments" as in for each Var we return [Var, A1, A2, A3] where Var is the variable assigned and A1 through A3 are valid assignments that fulfil the given constraints. The exact format doesn't matter as I'm only looking for a conceptual solution. Additionally A1, A2, A3 (aka all assignments for a Var) must obviously be in the domain of that variable. (Domains can overlap between variables).


  • valid_pairs() returns a list of tuples [(A1, A2), (A2,A3)]. The constraint is such that the returned solution list (as detailed above) must have consecutive assignments that form valid pairs that are given by this function. For example if the solution is [Var, A1, A2, A4, A3] and the valid pairs are [(A1, A2), (A2,A3)] then the solution is incorrect as (A2, A4) (A4, A3) is not in the list ((A1, A2) however is a valid pair).


  • Essentially we're looking for arc-consistency.








python search constraints backtracking constraint-programming






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 12 at 21:42

























asked Nov 10 at 22:43









Ge0rges

1,0551025




1,0551025












  • Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
    – Michael Veksler
    Nov 11 at 12:46










  • Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
    – Michael Veksler
    Nov 11 at 12:49










  • Please seed my latest edit for clarifications. @MichaelVeksler
    – Ge0rges
    Nov 11 at 20:57










  • If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
    – Michael Veksler
    Nov 11 at 21:05










  • No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
    – Ge0rges
    Nov 11 at 21:12




















  • Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
    – Michael Veksler
    Nov 11 at 12:46










  • Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
    – Michael Veksler
    Nov 11 at 12:49










  • Please seed my latest edit for clarifications. @MichaelVeksler
    – Ge0rges
    Nov 11 at 20:57










  • If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
    – Michael Veksler
    Nov 11 at 21:05










  • No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
    – Ge0rges
    Nov 11 at 21:12


















Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46




Please elaborate on the "list of assignments", is it the same as the "domain"? en.wikipedia.org/wiki/…
– Michael Veksler
Nov 11 at 12:46












Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49




Also, I don't quite understand what "valid_pairs()" is. Can you give one positive and one negative example?
– Michael Veksler
Nov 11 at 12:49












Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57




Please seed my latest edit for clarifications. @MichaelVeksler
– Ge0rges
Nov 11 at 20:57












If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05




If for each variable I take a random value, one from its list of valid assignments, will this collection (of variables and their values) satisfy all the constraints?
– Michael Veksler
Nov 11 at 21:05












No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12






No. It will satisfy only the basic constraint that the variable is assigned to valid (ie possible) assignments. However it is not guaranteed that there order will satisfy the other constraints (such as each pair being valid). @MichaelVeksler
– Ge0rges
Nov 11 at 21:12














1 Answer
1






active

oldest

votes

















up vote
1
down vote



accepted











  • We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.


  • We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.


  • We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.


  • In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.







share|improve this answer





















    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244153%2fconstraint-satisfaction-problem-formulation%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    1
    down vote



    accepted











    • We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.


    • We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.


    • We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.


    • In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.







    share|improve this answer

























      up vote
      1
      down vote



      accepted











      • We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.


      • We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.


      • We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.


      • In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.







      share|improve this answer























        up vote
        1
        down vote



        accepted







        up vote
        1
        down vote



        accepted







        • We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.


        • We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.


        • We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.


        • In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.







        share|improve this answer













        • We can use an NValues constraint whose scope is all variables, and domain is each possible assignment (For each assignment create a constraint). This ensures that all values are assigned when set to have an upper and lower bound of 1.


        • We can use use Neq constraint with a bit of modification to ensure the correct sequencing by feeding it tuples of valid assignments.


        • We can again use NValues constraint to ensure the k_assignment requirement by passing a lower bound of 1, and upper bound of K with domain K_assignments.


        • In the same way we can use NValues constraint with domain problem.first_assignments() for the first assignment. And another with domain problem.valid_assignments() to fill in the blanks.








        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 16 at 19:20









        Ge0rges

        1,0551025




        1,0551025






























             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244153%2fconstraint-satisfaction-problem-formulation%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Full-time equivalent

            さくらももこ

            13 indicted, 8 arrested in Calif. drug cartel investigation