Writing a constraint that looks at all provinces in the 4-color problem

Hello, 

I'm trying to modify the 4-color problem using the provinces of Canada.  I would like to check that no color is used more than four times.  I'm actually trying to solve this in another problem of my own, but the provinces of Canada is a great example. 

I'm trying to write a constraint that looks at all nodes in the graph and see if any one color is used more than 5 times. However, I don't know how to references all the nodes in the graph.  Here is what I've come up so far that isn't working --

def max_5(ab0, ab1, ab2, ab3, bc0, bc1, bc2, bc3):  # eventually all variables will be added, but let's get this to work
     redcnt = 0
     yellowcnt = 0
     bluecnt = 0
     greencnt = 0
     if ab0 == (0,0,0,1):
          redcnt = redcnt + 1
     elif ab0 == (0,0,1,0):
          yellowcnt = yellowcnt + 1
     elif ab0 == (0,1,0,0):
          bluecnt = bluecnt + 1
     else:
          greencnt = greencnt + 1
     if ab1 == (0,0,0,1):
          redcnt = redcnt + 1
     elif ab1 == (0,0,1,0):
          yellowcnt = yellowcnt + 1
     elif ab1 == (0,1,0,0):
          bluecnt = bluecnt + 1
     else:
          greencnt = greencnt + 1
     if ab2 == (0,0,0,1):
          redcnt = redcnt + 1
     elif c == (0,0,1,0):
          yellowcnt = yellowcnt + 1
     elif c == (0,1,0,0):
          bluecnt = bluecnt + 1
     else:
          greencnt = greencnt + 1

...and so on for all 13 provinces, monotonous code...

     max_cnt_ok = True
     if (redcnt > 4) or (yellowcnt > 4) or (bluecnt > 4) or (greencnt > 4): 
         max_cnt_ok = False
     return max_cnt_ok

# Create a binary constraint satisfaction problem
csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)

variables = ['AB0','AB1','AB2','AB3','BC0','BC1','BC2',BC3'] # MB, NB, NL, NS, NT, NU, ON, PE, QC, SK, YT all provinces to add
csp.add_constraint(max_5, variables)

 

There are plenty of problems with the above code.  But my basic problem is that I want to iterate over the nodes of the graph and count the number of times each color is used.  And, I'm not sure how the variables are constructed, not am I sure how to pass a the nodes of a graph as an iterable list of variables. And, then loop through them within the constraint function.  

Would truly appreciate any help in pointing me in the direction of documentation that would explain this. 

Thank you. 

 

-Steve

 

0

Comments

3 comments
  • OK, I made some progress and removed some errors.  A better constraint function is  --

     

    def max_5(ab0, ab1, ab2, ab3, bc0, bc1, bc2, bc3):  # all variables will be added, but let's get this to work on 2 provinces
         redcnt = 0
         yellowcnt = 0
         bluecnt = 0
         greencnt = 0
         if (ab0 == 0) and (ab1 == 0) and (ab2 ==0) and (ab3 == 1):
              redcnt = redcnt + 1
         elif (ab0 == 0) and (ab1 == 0) and (ab2 ==1) and (ab3 == 0):
              yellowcnt = yellowcnt + 1
         elif (ab0 == 0) and (ab1 == 1) and (ab2 ==0) and (ab3 == 0):
              bluecnt = bluecnt + 1
         else:
              greencnt = greencnt + 1

              ....and so on....

     

    However, in order to look at all 13 provinces the above code would requires passing 52 variables to the constraint function. 13 provinces * 4 variables each = 52.  

    When I run code under this approach, it compiles but takes a very long time.  I let it run for a couple of hours and had to stop it. 

    All advice is appreciated. 

     

    -Steve

      

     

     

    0
    Comment actions Permalink
  • I'm continuing to work on this.  I tried running the function with multiple variables, and found out the max is 8.  Didn't see this at first because the code took a very long time to compile.  The only way I can think to do this now is divide Canada's provinces into groups of 8 or less provinces. And then check each group.  Maybe there is a way to do this multiple times in order to achieve something that gets close to the overall constraint of one color being used a maximum of 5 times.  With 13 provinces, maybe I could divide the provinces into 3 groups of 8 provinces each (reusing provinces).  And then set the max number of times one color is used to 3.  Might work in terms of being good enough for the original real-world problem I'm trying to solve.   

    0
    Comment actions Permalink
  • Hello,

    Sorry for the delay on reaching out to you!
    Glad to see that you are making progress!

    Have you had a chance to look at this implementation of the 4 colour map-colouring problem?:
    https://docs.ocean.dwavesys.com/en/stable/examples/map_coloring_full_code.html

    The idea of this one is to assign colours to the areas of a map using four colours without having the adjacent areas use the same colour.

    This looks like it is a slightly different problem.
    Maybe you are building on the 4 colour problem?

    We have to be a bit careful here, because we could get ourselves into a situation where we overconstrain and there are no possible solutions.
    So if you were to try to colour a map with 21 areas for example, you would not be able to fulfill the max 5 areas with the same colour with only 4 colours, as we would have maxed out at 5 instances of each colour and then asked to colour another area (we're out of colours!!).

    If we are building on the 4-colour map colouring problem, we can keep the problem as is, and then add some constraint that restricts the sum of all the reds, blues, greens, yellows, explicitly and add this constraint to our overall problem.

    So we would add a constraint like:

    provinces_red = ['AB0', 'BC0', 'MB0', 'NB0', 'NL0', 'NS0', 'NT0', 'NU0', 'ON0', 'PE0', 'QC0', 'SK0', 'YT0']

    def max_five(a,b,c,d,e,f,g,h,i,j,k,l,m):
    return sum([a,b,c,d,e,f,g,h,i,j,k,l,m])<=5

    csp.add_constraint(max_five, provinces_red)

    The above can be generated with a loop like in the 4-colour map colouring problem.

    Before the stitch function:

    bqm = dwavebinarycsp.stitch(csp)
    

    I hope this makes sense and is helpful!

    I have not tested this out.
    There might be some constraints on how big the problem can be, but if you do run into embedding issues or size constraints, you can always use the LeapHybridSampler to run it.
    (Also see this page for info on solvers/samplers).

    Please let us know if you have any questions.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post