Answered

ValueError("no embedding found")

I have a sudoku solver example I built based on the map coloring example.  Is it possible that the error I am getting:  ValueError("no embedding found") is because the CSP is to large or complex for the underlying solver?  I already had to increase the value of the max_graph_size parameter in the dwavebinarycsp.stitch() call in order to get a BQM out of it.

1

Comments

6 comments
  • Also note, it works successfully for a 4x4 puzzle, but the 9x9 fails.

    1
    Comment actions Permalink
  • Are you using dwavebinarycsp.stitch()? What did you set max_graph_size to?

    Can you inspect the binary quadratic model and describe its properties?

    Edit:

    Inspecting the code for dwave-system/dwave/system/composites/embedding.py, "no embedding found" comes up when minorminer fails.

    # get the embedding
    embedding = minorminer.find_embedding(source_edgelist, target_edgelist)

    if bqm and not embedding:
    raise ValueError("no embedding found")

    2
    Comment actions Permalink
  • Yes, using stitch() call, increased the max_graph_size to 10 in order to have the bqm returned.

    # Convert the binary constraint satisfaction problem to a binary quadratic model
    bqm = dwavebinarycsp.stitch(self.csp, max_graph_size=10)

    I scanned the bqm and it looks well constructed.  Where I have fixed variables indicating known values in positions in the puzzle I am trying to solve, the variable representing the position-value does not appear in the list, and all of the other position-value variables for that position are set to values in the range 18-22 (high penalty).  Where the value of an individual position is not known the position-value variables range from -0.56875 to 1.43125. The edge weights for variables all seem to be set in a way that makes sense as well.

    All of that said, I must admit the idea of hand verifying the entire bqm seems a bit daunting.

     

    0
    Comment actions Permalink
  • I would not try and verify the BQM by hand. The idea is to get a feel for the size and "shape" of the problem.

    Here is the general flow: Original problem --> Constraint problem --> BQM --> Physical model

    For example, when I run the map coloring example for Canadian provinces, I get a BQM with 52 biases (or 52 nodes) and 138 weights (or 138 edges). (Keep in mind that the Python data structure is a compact representation of a sparse matrix that is 52x52 in size.) The magic here is how to map those 52 nodes and 138 edges to the physical topology of the dwave Chimera architecture.

    The EmbeddingComposite class maps to the dwave at a high level, but there is a package called minorminer (https://github.com/dwavesystems/minorminer) that does the heavy lifting. Minorminer tries to find a map between two graphs. That is, if I have graph A (my binary quadratic model) and graph B (the dwave physical layout), can I create a mapping between these two graphs?

    In your case, it looks like minorminer is saying it cannot find a mapping. The size of the problem could be one explanation (your problem exceeds the size of the dwave chip), but the "shape" of the problem could be another explanation. The dwave is not a torus topology, so once something runs to the edge of the chip things can get tricky. Another obstacle to mapping is inactive qubits. These are qubits that, for whatever reason, cannot be used.

    All that said, I would eyeball the size and shape of the BQM that you are generating, and use that to make guesses about why the problem may not map to the dwave. Remember: Just because a mapping does not exist does not mean all is lost. You can probably partition the problem into smaller chucks and then map those smaller chunks individually, putting these pieces back together using classical computing.

    2
    Comment actions Permalink
  • A quick clarification about this statement: "That is, if I have graph A (my binary quadratic model) and graph B (the dwave physical layout), can I create a mapping between these two graphs?" I glossed over "stuff" because I didn't think it was relevant to troubleshooting. If you are interested in the details, check out these two links:

     

    1
    Comment actions Permalink
  • Thank you, Thomas! This is a great response.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post