Trying to build a penalty function for a XOR table

In trying to learn how to formulate a problem to fit a D-Wave system, I am following the steps in the example that uses the AND truth table.  Instead of just repeating the steps (which I did) for the AND table, I'm gonna try a XOR table.  The XOR's table looks like this --

X1   X2   Z  VALID?   PENALTY

  0     0    0      Yes           0

  0     0    1      No            1+

  0     1    0      No            1+

  0     1    1      Yes           0

  1     0    0      No            1+

  1     0    1      Yes           0

  1     1    0      Yes           0

  1     1    1      No            1+

 

From this I have attempted to develop several penalty functions.  For example, the following gets close...

    (X1+X2+Z)(2-X1-X2-Z).

The first set of parentheses makes sure that when everything is zero the penalty is zero.  The second parentheses makes sure that when there are two zeroes and a single 1 in the row that the penalty is one or more and when there are two 1s the penalty is zero.  All good except for the last row in the table.  When everything is 1, the penalty becomes -3.  One solution is to square the term inside the second parentheses.  However, this produces a term where X1, X2, and Z are multiplied together.  It leads to...

    X1+X2+Z-2(X1)(X2)-2(X1)(Z)-2(X2)(Z)+12(X1)(X2)(Z).

The problem here is what do I do with the last term, +12(X1)(X2)(Z)?  How does it fit into a quadratic? 

I've tried different formulas.  And, calculating determinants to solve this, and other equations, down to a quadratic. I also tried Specification from the penaltymodel.core package.  Got the error code back that it was impossible.  That actually made me feel a little better.  

Again, just trying to learn Ocean and how D-Wave machines can solve problems. That's my goal.  It could be that my approach is all wrong from the beginning, but that's OK as long as I exhausted all potential solutions in trying to learn.  

Any suggestions or hints or criticisms are welcome!  :)

 

-Steve

 

0

Comments

3 comments
  • Hello,

    It looks like you need some auxiliary variables.

    The implementation in the documentation here uses one auxiliary variable for the XOR implementation:
    https://docs.dwavesys.com/docs/latest/handbook_reformulating.html#elementary-boolean-operations

    It was recommended to me to have the dwavebinarycsp talk to penaltymodels on your behalf, because it will make multiple calls to penaltymodels until a solution is found during the dwavebinarycsp.stitch(...) function call.

    They had also mentioned that the direct call to penaltymodels might not have succeeded if not enough auxiliary variables are provided.

    Not having to worry about explicitly including the auxiliary variables is another nice feature of using the dwavebinarycsp.

    Here is a code example using dwavebinarycsp:

    In [1]: import dwavebinarycsp as dbc
    In [2]: csp = dbc.ConstraintSatisfactionProblem(dbc.BINARY)
    In [3]: valid_config = {(0, 0, 0),
    ...: (0, 1, 1),
    ...: (1, 0, 1),
    ...: (1, 1, 0)}
    In [4]: csp.add_constraint(valid_config, ('a', 'b', 'out'))
    In [5]: bqm = dbc.stitch(csp)
    In [6]: bqm
    Out[6]: BinaryQuadraticModel({a: -2.0, b: -2.0, out: -2.0, aux0: -4.0, aux1: 4.0}, {('a', 'b'): 0.0, ('a', 'out'): 0.0, ('a', 'aux0'): 4.0, ('a', 'aux1'): 4.0, ('b', 'out'): 4.0, ('b', 'aux0'): 4.0, ('b', 'aux1'): -4.0, ('out', 'aux0'): 4.0, ('out', 'aux1'): -4.0, ('aux0', 'aux1'): 0.0}, 4.0, 'BINARY')


    I hope this was helpful!


    Please let us know if you have any further questions or need clarification.

    1
    Comment actions Permalink
  • Thank you.  Very helpful.  Auxiliary Variable is exactly the kind of help I was looking for.  I was trying a lot of things and was worried I might not even have a decent grip on the problem, but auxiliary variables make a lot of sense.  Thanks again.   

    1
    Comment actions Permalink
  • Glad we could help!
    Feel free to reach out to us with any questions you might have.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post