dwavesystems / qbsolv Goto Github PK

• Null input can cause a segfault
• single/small sets of independent variables can result in getting stuck in a loop forever

At: https://github.com/dwavesystems/qbsolv/blob/master/src/solver.c#L277

    //  clean out the subMatrix
    for (i=0; j < subMatrix; j++) { //for each column
        for (j=0; j < subMatrix; j++) val_s[i][j]=0.0; //for each row
    }
    //  fill the subMatrix
    for (i=0; i < subMatrix;i++) { //for each column
        Q_s[i]=Q[Icompress[i]];
        for (j=i; j < subMatrix;j++) { //copy row
            val_s[i][j]=val[Icompress[i]][Icompress[j]];
        }
    } 

In the first loop above there is a typo with the indexing variables, j is used where i should be. However the loop following this should be setting all values of val _s anyway, so the clean out pass could maybe be removed altogether?

Get testing, package build, pypi deployment on current 2, 3, and nightly python running.

Hi Guys,

Got qbsolv to build on windows just like the ree bsdbuild.

I'm facing a problem with qbsolv. qbsolv on windows command line doesn't converge when given the same input file as on free bsd on the mac.

Source is the same for both file streams and the only difference is the compiler, one is g++ and the other is Visual Studio 14 2015. Wanted to know why this is the case, I'm trying the command line version of the tool.

Best regards,
Cartik

Make sure errors in callbacks cause qbsolv to halt, and ideally reraise the exception.

read_qubo() allocates a buffer of size 50 for the 2nd token of a program (p) line and uses sscanf() to copy the token to the buffer. If the token is too long for the buffer, memory will be corrupted and a segmentation fault may ensue.

Also see pull request #83 comments about this issue.

Test 1. The 2nd token of the p line is too big for the buffer allocated for it. Memory is corrupted, but the program appears to work.

$ cat ittybitty1.qubo
c any thing
p qubo+extra-garbage-that-will-overrun-the-buffer-allocated-for-this-token 0 4 4 6
0 0 3.4
1 1 4.5
2 2 2.1
3 3 -2.4
0 1 2.2
0 2 -3.4
1 2 4.5
0 3 -3.2
1 3 4.5678
2 3 1

$ ./qbsolv -i ittybitty1.qubo
4 bits,  find Min, SubMatrix= 47, -a o, timeout=2592000.0 sec
1011
-2.50000 Energy of solution
0 Number of Partitioned calls, 1 output sample 
 0.00125 seconds of classic cpu time

Test 2. In this case, with a very long rogue token, a segmentation fault occurs.

$ cat ittybitty2.qubo
c any thing
p qubo+extra-garbage-that-will-overrun-the-buffer-allocated-for-this-token-and-cause-a-segmentation-fault-or-even-worse-corrupt-memory-silently-either-way-leading-to-wailing-tearing-of-hair-and-gnashing-of-teeth-such-drama-better-than-a-soap-opera-but-just-think-what-the-dentist-will-say-about-those-poor-teeth 0 4 4 6
0 0 3.4
1 1 4.5
2 2 2.1
3 3 -2.4
0 1 2.2
0 2 -3.4
1 2 4.5
0 3 -3.2
1 3 4.5678
2 3 1

$ ./qbsolv -i ittybitty2.qubo
Segmentation fault: 11

Hello.

The function evaluate() in solver.c calculates row_sum and col_sum; row_sum affects result, the return value of the function, and both row_sum and col_sum affect flip_cost, an output parameter.

The function Simple_evaluate() appears to be a simplified version of evaluate(). It also calculates row_sum and col_sum, and row_sum affects result, the return value. But in this function, col_sum is not used. Calculating it appears to be unnecessary. Would it make sense to eliminate col_sum from Simple_evaluate() for clarity, to save a few lines of code, and to save a few CPU cycles?

The only call to Simple_evaluate(), from near the end of solve(), is commented out. But presumably Simple_evaluate() might be pressed into service again.

Thank you.

S.D.

The shell scripts under tests/ are not run as part of continuous integration, and therefore performance degradation isn't tracked. What constitutes "good performance" isn't well-defined.

@adam-douglass To get the matlab bindings installed on my machine, I needed

• to update cython (not sure exactly what version is required)
• to add the "-std=c99" flag on line 11 of setup.py

Two issues:

One:

Installation was failing;
and an error message was printing about some clashing of versions:

I have a problem with the new code:

mport numpy as np
from dwave_sapi_dimod import SAPISampler
from dwave_sapi_dimod import EmbeddingComposite
from dwave_qbsolv import QBSolv

Traceback (most recent call last):
File "customer.py", line 2, in
from dwave_sapi_dimod import SAPISampler
File "//anaconda/lib/python2.7/site-packages/dwave_sapi_dimod/init.py", line 9, in
from dwave_sapi_dimod.samplers import *
File "//anaconda/lib/python2.7/site-packages/dwave_sapi_dimod/samplers.py", line 26, in
class SAPILocalSampler(dimod.TemplateSampler):
AttributeError: 'module' object has no attribute 'TemplateSampler'

Two:

Exception TypeError: TypeError("expected 'num_occurences' to be a positive int",) in 'dwave_qbsolv.qbsolv_binding.solver_callback' ignored​

On this second one, the code didn't throw this message when running on a local machine, but when the code was running on the D-Wave QPU, this message was thrown. The runs would proceed; but this message was generated.

Hello,

I have been thinking a little bit about qbsolv and I came up with a reasoning which might interest this community. As far as I understood, qbsolv is concerned with problems which unknown is defined over the discrete space {0,1}^N, where N is an integer. In other words the values of a N-dimensional unknown X can have only components which are either 0 or 1.

Now, could we use it qbsolv to deal with problems which are defined over the space R^N? (i.e. defined over the space of N-dimensional real vectors) Personally, I think the answer must be positive, at least for a certain class of problems. In fact, one can always write a real number in base 2. Therefore, there must be a class of optimization problems in R^N which, once rewritten in base 2, coincides with a quadratic (unconstrained) binary optimization problem.

I think it would be interesting to understand what classes of continuum optimization problems could eventually be transformed in a binary problem and, thus, be solved by qbsolv. At that point, one could think of a simple extra layer to add to qbsolv which could automatically transform a continuum problem into a binary problem.

As I find this reasoning quite interesting and, most of all useful, it would be great to hear about your opinion. I hope this, somehow, contribute to this exciting project.

Thanks!

Hello,

I downloaded the latest version of the code (updated in the weekend) and when trying to compile from the directory "tests" I got the following error:

cd ../src && make util.o
make[1]: Entering directory '/home/sellier/qbsolv-master/src'
make[1]: 'util.o' is up to date.
make[1]: Leaving directory '/home/sellier/qbsolv-master/src'
cd ../src && make solver.o
make[1]: Entering directory '/home/sellier/qbsolv-master/src'
make[1]: 'solver.o' is up to date.
make[1]: Leaving directory '/home/sellier/qbsolv-master/src'
cd ../src && make dwsolv.o
make[1]: Entering directory '/home/sellier/qbsolv-master/src'
make[1]: 'dwsolv.o' is up to date.
make[1]: Leaving directory '/home/sellier/qbsolv-master/src'
g++ solver_reduce.cpp ../src/util.o ../src/solver.o ../src/dwsolv.o -o solver_reduce -g -lgtest
solver_reduce.cpp:1:25: fatal error: gtest/gtest.h: No such file or directory
compilation terminated.
make: *** [Makefile:10: solver_reduce] Error 1

This used to work a few days ago. Did somebody change something?

I hope this helps,

JM Sellier

Hi Dwave team,
Thank you for this exciting initiative to produce qbsolv. I am getting to work trying it out. My aim is to contribute some examples with clear explanations from the field of economics.

I've cloned from GitHub and compiled the code successfully:

$ gcc -v
Thread model: posix
gcc version 4.9.2 20150212 (Red Hat 4.9.2-6) (GCC)

[sityin@helios4 src]$ make clean && make
rm -f debugs.o dwsolv.o main.o readqubo.o solver.o util.o qbsolv
gcc -Ofast -c -o debugs.o debugs.c
gcc -Ofast -c -o dwsolv.o dwsolv.c
gcc -Ofast -c -o main.o main.c
gcc -Ofast -c -o readqubo.o readqubo.c
gcc -Ofast -c -o solver.o solver.c
gcc -Ofast -c -o util.o util.c
gcc -Ofast -o qbsolv debugs.o dwsolv.o main.o readqubo.o solver.o util.o

$ which qbsolv
~/qbsolv/src/qbsolv

Running the tests showed things are working....

$ cd ../tests
$ ./qbsTest_bqp_Target.sh
-v0
Version open source 2.3 Jan 18 2017,16:06:09
Wed Jan 18 16:17:39 AEDT 2017

Test bqp50 with Target set 

Test name CPU sec W/C Parts Energy qbsolv version
bqp50_1.qubo 0.00000 0 0 2098.00000 Jan 18 2017,16:06:09
bqp50_1.qubo 0.00000 0 0 2098.00000 Version open source 2.3
bqp50_2.qubo 0.00000 0 0 3702.00000 Jan 18 2017,16:06:09
bqp50_2.qubo 0.00000 0 0 3702.00000 Version open source 2.3
bqp50_3.qubo 0.00000 0 0 4626.00000 Jan 18 2017,16:06:09
bqp50_3.qubo 0.00000 0 0 4626.00000 Version open source 2.3
bqp50_4.qubo 0.00000 0 1 3544.00000 Jan 18 2017,16:06:09
bqp50_4.qubo 0.00000 0 1 3544.00000 Version open source 2.3
.
.
.
Total cpu time 0.02 Jan 18 2017,16:06:09
Total cpu time 0.01 Version open source 2.3
Elapsed time 2 seconds

Test non target mode bqp50
Test name CPU sec W/C Parts Energy Delta Energy qbsolv version
bqp50_1.qubo 0.51000 0 50 2098.00000 0.0 Jan 18 2017,16:06:09

Now however I create the example QUBO file that was described in the technical document 'Partitioning Optimization Problems for Hybrid Classical/Quantum Execution'

$ cat debugOC.qubo
c any thing
p qubo 0 4 4 6
0 0 3.4
1 1 4.5
2 2 2.1
3 3 -2.4
0 1 2.2
0 2 -3.4
1 2 4.5
0 3 -3.2
1 3 4.5678
2 3 1

And when I try running qbsolv with this input, I get a segfault:

$ qbsolv -i debugOC.qubo -v 2
Segmentation fault (core dumped)

While simplifying code trying to understand a different issue, I tried to run the trivial example here:

https://github.com/dwavesystems/qbsolv/blob/0.2.9/python/dwave_qbsolv/dimod_wrapper.py#L75-L81

However, the response has no energies attribute.

I don't actually use this code in my project, but I would like to understand what I've done wrong; or, perhaps the example is incorrect.

(If it helps, looking at the history, the example went in at 11745cd back when the response was a dimod BinaryResponse. It is now a Response. I'm using qbsolv 0.2.9, but I don't see any thing since then on master which might be related.)

Including the qbsolv import, my entire code is:

from dwave_qbsolv import QBSolv

Q = {(0, 0): 1, (1, 1): 1, (0, 1): 1}
r = QBSolv().sample_qubo(Q)

s = list(r.samples())
print(s)

e = list(r.energies()) # ==> AttributeError
print(e)

Apologies for by-passing your issues template. :) If I should ask about this elsewhere, please let me know.

I've tried the classic MapColoring sample but got a seemingly incorrect output SVG.

Environment: Cygwin64_2.873, GNU make 4.2.1, Python 2.7.9.
Intermediate Files: usa.qubo, usa.qbout(i.e. "xaa")

Does it means, currently qbsolv is still in its simulated annealing version, so cannot solve a N=51 NPC problem?

Current Problem
There is undocumented behavior, that QBSolv doesn't use provided sampler if the size of the problem is smaller than 20. This is misleading since people usually start with small problems.

Also, it's not obvious why one should
sampler = EmbeddingComposite(DWaveSampler(token=sapi_token, endpoint=endpoint))
instead of sampler = DWaveSampler(token=sapi_token, endpoint=endpoint).

Furthermore, it's hard to distinguish if QBSolv is using QPU or not. The easiest way to do that is through Leap dashboard and there is no easy way to do that programmatically.

Proposed Solution
This behavior should be clearly described in the documentation or some information for the user should be printed.

Also, it would be nice if there was a way to get data about QPU runtimes directly from QBSolv.

Additional context
For more details see #134

Create the option to set the initial state of the tabu search.

• C library, add parameter and change library operation
• Command line argument
• Python argument
• Test: give initial solution that matches target energy, should immediately stop
• Test: argument passing with library mocked

when I try to run the example(about the four-color-map problem),I got a trouble follows :
./demoStates.sh:line35: ../../src/qbsolv: Cannot execute binary file: Exec format error
My use.qubo's format follows like:
c
c this qubo was created by adj2qubo.py for 4 color uninary encoding
c
p qubo 0 204 204 742
c AK
0 0 -1
1 1 -1
2 2 -1
3 3 -1
c HI
4 4 -1
5 5 -1
6 6 -1
7 7 -1
and so on
what can I do to solve the problem?

Currently the matlab bindings in matlab/QBSolv.m (eg. sampleQubo) only pass in the QUBO and the number of iterations - it would be nice to have the rest of the options available here.

At: https://github.com/dwavesystems/qbsolv/blob/master/examples/mapColoringUSStates/adj2qubo.py#L51

for i in range ( num_states ):
        state_str="".join(map(str,states[i]))
        states_num[i]=i
        for k in range ( num_states ):
            states_records[k]=[ it if it != state_str else i for it in states_records[k] ]
            states_records[k]=[ it for it in states_records[k] if it > k ]

In the last statement we are comparing the string elements of states_records, i.e. MS, TN, to k, which is the index of the second for loop.

Exception:

{TypeError}'>' not supported between instances of 'str' and 'int'

Script hasn't been updated along with CMakeLists.txt to reflect restructuring of code. Should either be fixed or removed.

At: https://github.com/dwavesystems/qbsolv/blob/master/src/solver.c#L496

            if ( UseDwave_ ) {
                dw_solver ( val_s,subMatrix,Q_s );
            } else {
                solv_submatrix (Q_s,Qt_s, subMatrix,val_s,Qval_s,Row_s,Col_s,&t,TabuK_s,index_s);
            }
            if (Verbose_>3){
                 printf("Bits set after solver     ");
                 for (i=0;i < subMatrix;i++) printf("%d",Q[index[i+l]]);
                 printf("\n");
            }
            numPartCalls++;
            for (j=0;j < subMatrix;j++) {
                i=Icompress[j];
                Q[i]=Q_s[j];
            }
            DwaveQubo++;

The values from Q are printed with the label "Bits set after solver", before copying value from Q_s to Q.

Should the debug statement be after the copy or be reading from Q_s?

Description
When I pass sampler to QBSolv, it still uses classical solver instead of running code on QPU.

To Reproduce

from dwave.system.samplers import DWaveSampler
from dwave_qbsolv import QBSolv
from dwave.system.composites import EmbeddingComposite

Q = {(0, 0): 1, (1, 1): 1, (0, 1): 1}

sapi_token = 'my_token'

endpoint = 'https://cloud.dwavesys.com/sapi'
sampler = DWaveSampler(token=sapi_token, endpoint= endpoint)

# Not sure which version is correct, both solve clasically
response = QBSolv().sample_qubo(Q, solver=sampler)
response = QBSolv().sample_qubo(Q, solver=EmbeddingComposite(sampler))

# This works on QPU, but I wanted to use QBSolv
response = EmbeddingComposite(sampler).sample_qubo(Q)

Expected behavior
I expect that my code will be executed on QPU when I pass a sampler, especially that I tested that this sampler executes code on QPU without QBSolv.
It should at least print a warning since this behavior is not what I expected.

Environment:

• OS: 10.13.6
• Python version: 3.6.4
• dwave-qbsolv==0.2.9
• dwave-system==0.5.3

Hi
After reading some articles & understanding some basics ,got interest in quantum mechanics & its based computing. I went through map coloring problem which has search space of 4^13 with 4 colors ,13 states (with 2413 physical quibits) . Is current quantum computer is feasible to solve problems which has a bigger search space of let's say 100^100 by using may be in hierarchical way (if such hierarchical methods exist , how accurate would the solutions w.r.to global minima) ? Thanks in advance for your reply.

Sub problems may be coming from a minimization or maximization context, make sure they are aligned consistently to minimize before calling solver callback.

Recently I upgraded my local servers of windows and linux.
The problem is non of D-wave tools are installing "dwave-neal, qbsolv"
Error " Could not find a version that satisfies the requirement qbsolv (from versions: )
No matching distribution found for qbsolv".
I have tried both version of python3 and 2 could you please enlighten me a bit.
Thanks in advance.

The documentation of the QUBO file format of the "p" line says that the third token may be either "0" or "unconstrained" to represent a QUBO. The current version does not accept "unconstrained".

From QUBO.pdf, which is not on the Github//qbsolv site but probably should be, with emphasis added
"
One program line, which starts with “p” in the first column. The program line must be the first non-comment line in the file. The program line has six required fields (separated by space(s)), as follows:
p qubo target maxDiagonals nDiagonals nElements
where
p the problem line sentinel qubo the file type
target the topology of the problem and the specific problem type, identified by a string. For an unconstrained problem, target may be “0” or “unconstrained.” For constrained problems, valid strings could include “chimera128” or “chimera512” (among others).
maxDiagonals number of diagonals in the topology.

[...]
"
QUBO.pdf

I'm trying to build qbsolv on windows using MS Visual Studio 14, 2015 using CMake

I'm getting errors in header files such as vadefs.h, vcruntime.h, attached error list.

Please advise on how to fix these build errors so I can proceed with qbsolv.
qbsolv_error.txt

For the QA system the marginal cost of additional samples is very small, it would make sense to try to process multiple states returned for a sub-problem. This probably won't do much without #61.

When following the C install instructions, the following error

acondello:~/projects/misc/steve_mike_qbsolv_install/qbsolv/build$ make
Scanning dependencies of target libqbsolv
[  4%] Building CXX object CMakeFiles/libqbsolv.dir/src/solver.cc.o
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/src/solver.cc:547:81: warning: unused parameter ‘sub_sampler_data’ [-Wunused-parameter]
 void dw_sub_sample(double** sub_qubo, int subMatrix, int8_t* sub_solution, void*sub_sampler_data){
                                                                                 ^
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/src/solver.cc:555:82: warning: unused parameter ‘sub_sampler_data’ [-Wunused-parameter]
 void tabu_sub_sample(double** sub_qubo, int subMatrix, int8_t*sub_solution, void*sub_sampler_data){
                                                                                  ^
[  8%] Building CXX object CMakeFiles/libqbsolv.dir/src/util.cc.o
[ 12%] Building CXX object CMakeFiles/libqbsolv.dir/src/dwsolv.cc.o
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/src/dwsolv.cc:180:25: warning: unused parameter ‘val’ [-Wunused-parameter]
 void dw_solver(double **val, int maxNodes, int8_t *Q)
                         ^
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/src/dwsolv.cc:180:34: warning: unused parameter ‘maxNodes’ [-Wunused-parameter]
 void dw_solver(double **val, int maxNodes, int8_t *Q)
                                  ^
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/src/dwsolv.cc:180:52: warning: unused parameter ‘Q’ [-Wunused-parameter]
 void dw_solver(double **val, int maxNodes, int8_t *Q)
                                                    ^
[ 16%] Linking CXX static library libqbsolv.a
[ 16%] Built target libqbsolv
Scanning dependencies of target qbsolv
[ 20%] Building C object CMakeFiles/qbsolv.dir/cmd/main.c.o
[ 25%] Building C object CMakeFiles/qbsolv.dir/cmd/readqubo.c.o
[ 29%] Linking CXX executable qbsolv
[ 29%] Built target qbsolv
Scanning dependencies of target solver_reduce
[ 33%] Building CXX object tests/CMakeFiles/solver_reduce.dir/solver_reduce.o
/home/acondello/projects/misc/steve_mike_qbsolv_install/qbsolv/tests/solver_reduce.cpp:1:25: fatal error: gtest/gtest.h: No such file or directory
compilation terminated.

Many D-Wave users view the decomposition and subproblem-execution tasks that qbsolv undertakes as critical to gaining benefit from a D-Wave system. Given the intense interest in when and how D-Wave systems will deliver differentiated performance, the details of decomposition and QMI execution are important to engaged users who want to understand the steps being taken on their behalf. Some users have said they will not use tools whose operation (and sometimes code) they cannot see and understand. Thus debuggability (of the user's problem) and transparency of qbsolv execution are important.

In addition to the current info emitted by use of the 'verbosity' option, the ability to save to files (in the qbsolv input format) the subQUBOs that are executed would also be valuable.

Would you please look at the snippet from solver.c function local_search_1bit() below.

It appears that on the sweep from top to bottom, kk iterates through [qubo_size - 1, 1] inclusive.
On the sweep from bottom to top, kk iterates through [0, qubo_size - 1] inclusive.

Is it intentional that kk does not get to 0 on the sweep from top to bottom?

Thank you.

S.D.

double local_search_1bit(...)
{
    int kkstr = 0, kkend = qubo_size, kkinc;
    ...
        if (kkstr == 0) { // sweep top to bottom
            shuffle_index(index, qubo_size);
            kkstr = qubo_size - 1; kkinc = -1; kkend = 0;
        } else { // sweep bottom to top
            kkstr = 0; kkinc = 1; kkend = qubo_size; // got thru it backwards then reshuffle
        }

        for (int kk = kkstr; kk != kkend; kk = kk + kkinc) {
            ...
        }
    ...

In the reduce function in solver.c in the lines of the form: clamp += val[rc][j] * Q[j] * Q[rc]; the rc value used to index into val is defined in a loop from zero to subMatrix. In the initialization of val_s indexes used to read into val are passed through Icompress. Such as: val_s[i][j] = val[Icompress[i]][Icompress[j]];.

Should the lines around 308 and 317 be using rc_s as the index into val, rather than rc.

Hello,

I found in "main.c" the declaration of many global variables. This is usually considered as a "bad practice". I would suggest to create a global structure where these variables are all embedded. What do you guys think?

JM Sellier

Hello,

I am an Associate Professor at the Bulgarian Academy of Sciences and the creator/developer/maintainer of several GNU packages which can be found here:
https://www.gnu.org/software/archimedes/
http://www.nano-archimedes.com/
https://www.gnu.org/software/gneuralnetwork/

In particular, nano-archimedes is a simulator for the quantum transport of electrons based on the signed particle formulation of quantum mechanics (which I came up with a few years ago). A paper on this formulation can be found here:
http://www.sciencedirect.com/science/article/pii/S0021999115003708

It turned out that this formulation is computationally very advantageous (compared to other formulations). As a matter of fact I have been able, for example, to use it to simulate systems of indistinguishable Fermions on relatively small computing systems (actually a single-CPU computer):
http://www.sciencedirect.com/science/article/pii/S0021999114006627

I also used this formulation to depict a quantum system exploiting interacting electrons which can solve a system of linear equations reformulated in terms of an optimization problem:
http://link.springer.com/chapter/10.1007/978-3-319-21133-6_3

Many other papers can be found here:
http://www.nano-archimedes.com/publications.php

Since, as far as I understood, the flux qbits used on D-WAVE systems can be considered as one-dimensional devices, it would be useful/interesting to solve the sub-QUBO problems by means of a simulated system by means of the signed particle formulation. For example, for relatively small sub-QUBO problems, one could embed nano-archimedes into qbsolv and solve these problems by means of a simulated set of one-dimensional electrons. This could bring to a more realistic simulation of the whole optimiziation process. What do you guys think?

I hope, somehow, this suggestion helps. I look forward to hear your opinion.

Thanks,

JM Sellier

Hello,

I downloaded the last version of qbsolv and compiled it on Xubuntu. When compiling, I get the following warning:

main.c: In function 'main':
main.c:65:20: warning: overflow in implicit constant conversion [-Woverflow]
long seed = 17932241798878;

Is there a way to avoid it? Warnings are usually not a big concern but it's always good to avoid them..

I hope this helps,

JM

It would be great to have some README file in the "tests" directory which explains what to run and what to expect (in order to understand if the locally compiled binary is providing the right numbers).

Thanks,

JM Sellier

qbsolv's decision about when to use the classical tabu solver and when to use the QPU can be opaque, and the algorithm has changed and probably will change again. Sometimes users want to know that they're using the QPU, to ensure their permissions/token/etc. are all set up properly, or to compare classical/quantum performance. Having a parameter that forces qbsolv to use the QPU will clear up any such confusion.

This program seems to run forever, on the D-Wave QPU.
It is a customer's program. For I = 1 to I = 7, it runs locally, but once I = 8, it goes to the D-Wave QPU.
For the customer, it ran so long that he got a "502 Bad server response" error.

cust.txt

Add a method for extracting sub problems from the complete problem that is less sensitive to the current global state. In cases where the sub problem size is much smaller that the full problem the number of incoming edges can overwhelm the sub problem itself.

CodeAI, the first non-human contributor to your software project, found and fixed 3 defects in qbsolv. It wants to merge 3 pull requests (#101, #103, #105) fixing these issues- 1 Memory Leak and 2 Dead Code. To claim your free open source account visit mycode.ai.
A screenshot of the results as well as the Dockerfile used to build and run your project in CodeAI can be found here- https://drive.google.com/drive/folders/112m4R_SvpqynmrYk2gdaUBd8a5Cjt2PH?usp=sharing.

If you have any questions about these results or have general inquiries about CodeAI, please send an email to [email protected].

Thank you for accepting recent pull requests #63 and #64. #63 is a safety measure, using const with function parameters. #64 boosts performance by substituting cheaper equivalent operations for more expensive ones in evaluate().

In an attempt to quantify the impact of #64 and to examine the impact of pseudo-random number generator (PRNG) seed on qbsolv performance, I ran hundreds of tests as follows.

From random.org I obtained 800 random bytes generated by atmospheric noise and assembled them into 200 random unsigned 32-bit integers for use as PRNG seeds.

On Amazon Web Services, I used Sun Grid Engine to distribute jobs to c4.4xlarge nodes with hyperthreading turned off and 1 SGE slot per core.

for each test in qbsTestcounties, qbsTest2500, do:
    for each qbsolv version in PR63, PR64, do:
        for each seed in a set of 200 random seeds, do:
            run test
        done
    done
done

Please look at the tables and graphs of results attached below. In the graphs, tests are plotted by speed rank from no. 1, fastest, to no. 200, slowest, on the x axis, with CPU time on the y axis. Note that the y axis is logarithmic.

As you can see, in target mode the PRNG seed has a huge impact on performance. For example, in the counties tests, CPU time ranges from 84 to 4070 sec for the PR #63 version and from 68 to 3081 sec for the PR #64 version. I think I see two or possibly three inflection points in the curve, one at about speed rank 18, another at about speed rank 167, and possibly a third where the extreme outliers shoot up. What do you think might account for the shape of the curve?

In issue #62, Adam Douglass remarks that "For the QA system the marginal cost of additional samples is very small, [so] it would make sense to try to process multiple states returned for a sub-problem."

In a similar spirit, I wonder whether it would make sense to run multiple qbsolv processes concurrently with different random seeds. In target mode, a result might be found more quickly. In non-target mode, giving up before finding an optimal result might be avoided. The Python front-end could fire up and manage multiple qbsolv processes pretty easily, couldn't it?

Perf_counties_200_seeds_graph.pdf
Perf_orlib2500_200_seeds_graph.pdf
Perf_counties_200_seeds_summary_table.pdf
Perf_orlib2500_200_seeds_summary_table.pdf

Hello,

It's very exciting that DWAVE is sharing qbsolv! I managed to compile it on a Windows machine by using the Cygwin terminal. I used gcc 4.9.2 and got the following error:

gcc -Ofast -c -o dwsolv.o dwsolv.c
gcc -Ofast -c -o util.o util.c
gcc -Ofast -c -o solver.o solver.c
solver.c: In function ‘solve’:
solver.c:400:17: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘attribute’ before numeric constant
const int QLEN 20;
^
solver.c:405:38: error: ‘QLEN’ undeclared (first use in this function)
Qlist = (short**)malloc2D(maxNodes, QLEN + 1, sizeof(short));
^
solver.c:405:38: note: each undeclared identifier is reported only once for each function it appears in
: recipe for target 'solver.o' failed
make: *** [solver.o] Error 1

This was solved by modifying line 400 of solver.c from:
const int QLEN 20;
to:
const int QLEN=20;

I hope this helps,

JM Sellier

I just noticed that compilation of tests fail unless -lpthread is provided as compilation option: Here are the errors I am getting from make:

g++ solver_reduce.cpp ../src/util.o ../src/solver.o ../src/dwsolv.o -o solver_reduce -g -lgtest
//usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocal<testing::TestPartResultReporterInterface*>::~ThreadLocal()': gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEED2Ev[_ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEED5Ev]+0x25): undefined reference to pthread_getspecific'
gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEED2Ev[_ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEED5Ev]+0x3a): undefined reference to pthread_key_delete' //usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocal<std::vector<testing::internal::TraceInfo, std::allocatortesting::internal::TraceInfo > >::~ThreadLocal()':
gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEED2Ev[_ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEED5Ev]+0x25): undefined reference to pthread_getspecific' gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEED2Ev[_ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEED5Ev]+0x3a): undefined reference to pthread_key_delete'
//usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocal<std::vector<testing::internal::TraceInfo, std::allocator<testing::internal::TraceInfo> > >::GetOrCreateValue() const': gtest-all.cc:(.text._ZNK7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE16GetOrCreateValueEv[_ZNK7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE16GetOrCreateValueEv]+0x25): undefined reference to pthread_getspecific'
gtest-all.cc:(.text._ZNK7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE16GetOrCreateValueEv[_ZNK7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE16GetOrCreateValueEv]+0x88): undefined reference to pthread_setspecific' //usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocaltesting::TestPartResultReporterInterface*::CreateKey()':
gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE9CreateKeyEv[_ZN7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE9CreateKeyEv]+0x25): undefined reference to pthread_key_create' //usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocal<std::vector<testing::internal::TraceInfo, std::allocatortesting::internal::TraceInfo > >::CreateKey()':
gtest-all.cc:(.text._ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE9CreateKeyEv[_ZN7testing8internal11ThreadLocalISt6vectorINS0_9TraceInfoESaIS3_EEE9CreateKeyEv]+0x25): undefined reference to pthread_key_create' //usr/local/lib/libgtest.a(gtest-all.cc.o): In function testing::internal::ThreadLocaltesting::TestPartResultReporterInterface*::GetOrCreateValue() const':
gtest-all.cc:(.text._ZNK7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE16GetOrCreateValueEv[_ZNK7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE16GetOrCreateValueEv]+0x25): undefined reference to pthread_getspecific' gtest-all.cc:(.text._ZNK7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE16GetOrCreateValueEv[_ZNK7testing8internal11ThreadLocalIPNS_31TestPartResultReporterInterfaceEE16GetOrCreateValueEv]+0x88): undefined reference to pthread_setspecific'
collect2: error: ld returned 1 exit status
Makefile:10: recipe for target 'solver_reduce' failed
make: *** [solver_reduce] Error 1

Since qbsolv is performing a minimisation of x'Qx, a trivial solution is one with all elements of x=0 .

Is it feasible for there to be a command-line option that forces the algorithm to avoid this trivial solution?

One way I suggest is to add a large penalty term to the objective function, eg for a 4 element x vector, add the term K*(1-x1)(1-x2)(1-x3)*(1-x4) to the objective function, and default K to 0 (the user overrides this from the command line to set K). I don't know whether this maps to the way D-wave hardware works though.