{"action":"opened","issue":{"url":"https://api.github.com/repos/dwavesystems/dwavebinarycsp/issues/57","repository_url":"https://api.github.com/repos/dwavesystems/dwavebinarycsp","labels_url":"https://api.github.com/repos/dwavesystems/dwavebinarycsp/issues/57/labels{/name}","comments_url":"https://api.github.com/repos/dwavesystems/dwavebinarycsp/issues/57/comments","events_url":"https://api.github.com/repos/dwavesystems/dwavebinarycsp/issues/57/events","html_url":"https://github.com/dwavesystems/dwavebinarycsp/issues/57","id":362349043,"node_id":"MDU6SXNzdWUzNjIzNDkwNDM=","number":57,"title":"small example requires many many samples for valid solution","user":{"login":"spreinhardt","id":22921589,"node_id":"MDQ6VXNlcjIyOTIxNTg5","avatar_url":"https://avatars3.githubusercontent.com/u/22921589?v=4","gravatar_id":"","url":"https://api.github.com/users/spreinhardt","html_url":"https://github.com/spreinhardt","followers_url":"https://api.github.com/users/spreinhardt/followers","following_url":"https://api.github.com/users/spreinhardt/following{/other_user}","gists_url":"https://api.github.com/users/spreinhardt/gists{/gist_id}","starred_url":"https://api.github.com/users/spreinhardt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spreinhardt/subscriptions","organizations_url":"https://api.github.com/users/spreinhardt/orgs","repos_url":"https://api.github.com/users/spreinhardt/repos","events_url":"https://api.github.com/users/spreinhardt/events{/privacy}","received_events_url":"https://api.github.com/users/spreinhardt/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-09-20T20:17:47Z","updated_at":"2018-09-20T20:17:47Z","closed_at":null,"author_association":"NONE","body":"The attached program solves the max-cut graph problem by creating a circuit of 14 variables (3 full adders and 1 half adder) to see if a cut of size k exists.  For cutSize=2, it takes anywhere from 817K samples to 17M samples to find a valid answer.  Given that solving it randomly would require on average only 2^14 ~= 16K samples, this seems excessive. \r\n\r\n\r\n**Expected Behavior**\r\nWhen run as\r\n    $ python maxCut_csp.py\r\nyou will see output like\r\n    cutSize=0\r\n    cutSize=1\r\n    cutSize=2\r\n    nSamples=0, gathering 10000 more\r\n    nSamples=10000, gathering 10000 more\r\n    nSamples=20000, gathering 10000 more\r\n    [...]\r\n    nSamples=16990000, gathering 10000 more\r\n    nSamples=17000000, gathering 10000 more\r\n     valid sample=[('A', 0), ('AB', 1), ('AC', 1), ('B', 1), ('BC', 0), ('BD', 0), ('C', 1), ('C0', 1), ('C1', 0), ('C2', 0), ('CE', 0), ('D', 1), ('DE', 0), ('E', 1), ('S0', 0), ('S1', 0), ('aux0', 1), ('aux1', 1), ('aux10', 1), ('aux11', 1), ('aux12', 1), ('aux13', 1), ('aux2', 0), ('aux3', 0), ('aux4', 1), ('aux5', 1), ('aux6', 1), ('aux7', 1), ('aux8', 1), ('aux9', 0)]\r\n     result=[('A', 0), ('AB', 1), ('AC', 1), ('B', 1), ('BC', 0), ('BD', 0), ('C', 1), ('C0', 1), ('C1', 0), ('C2', 0), ('CE', 0), ('D', 1), ('DE', 0), ('E', 1), ('S0', 0), ('S1', 0), ('aux0', 1), ('aux1', 1), ('aux10', 1), ('aux11', 1), ('aux12', 1), ('aux13', 1), ('aux2', 0), ('aux3', 0), ('aux4', 1), ('aux5', 1), ('aux6', 1), ('aux7', 1), ('aux8', 1), ('aux9', 0)]\r\n     cutSize=3\r\n     nSamples=0, gathering 10000 more\r\n     nSamples=10000, gathering 10000 more\r\n\r\n**Source file**\r\n[maxCut_csp.py.gz](https://github.com/dwavesystems/dwavebinarycsp/files/2402932/maxCut_csp.py.gz)\r\n\r\n**Environment**\r\n - OS: [macOS HighSierra / Darwin Kernel 17.7.0]\r\n - Python version: [Anaconda 2.7.14]\r\n\r\n\r\n"}}
{"actor":{"display_login":"spreinhardt"}}