Meta-Analytics web site quickstart for Alpha-QUBO

to solve problems with up to 3,000 variables

 

(Click here to request access to Advanced Alpha-QUBO to solve larger problems.)

 

Go to the web address: http://meta-analytics.com

Create an account.

 

a) Click on Login, Upload, or QUBO Models

b) Click on Sign up (at upper right of login dialog)

c) Sign up using email and password, or using your Google account. After signing up you may receive an email email from 'meta-analytics' using the email address no-reply@auth0user.net. Click on the 'verify link' in the email to complete the account creation.

 

Upload a QUBO model

 

a) The QUBO model file format is a text file with information on the first line that describes the size of the q(i,j) matrix.

 

Line1: p variableCount non-zeroElementCount (for upper triangular Q Matrix)

(The letter p here is invariant, and verifies that this is Line 1.)

Line2: I J q(i,j) this is also q(j,i) since the matrix is symmetric

(Only non-zero elements need be added. The indexes I and J satisfy I J since the

matrix is input in upper triangular form, and I = J identifies a diagonal element.)

..

LineN: I J (qi,j)

 

 

For example, the file bqp100.txt starts with the following lines:

 

p 100 475

1 35 -19

1 44 -22

1 47 27

1 49 -66

1 58 -69

1 64 63

1 72 -89

1 73 -19

1 74 -69

1 76 -12

1 84 40

1 98 33

2 2 52

 

Comment: The number of spaces between numbers entered on a line is irrelevant. For instance, the last line above could also be 2 2 52.

b) File Compression

The QUBO text file can be compressed to a .7z (7-Zip) https://7-zip.org/ , (or .zip) file to reduce the file size for upload. When uploading compressed files check the 'Compressed File format check box' before uploading

 

To upload the file, click on 'Upload', enter a QUBO model name, click choose file and finally click 'Upload QUBO Model' after selecting the file. Upload progress is shown in the lower left hand corner of the webpage. Wait until the upload completes. After a successful upload the website will display the table of QUBO models. The web page may need to be refreshed at this point to show the new model. Click the reload icon on your web browser, or enter return next to the web address.

 

 

Create a QUBO Solution.

a) Click on QUBO Models

b) Click on 'Create Solution' for the selected model

c) Enter the 'Time Limit'.

d) Uncheck 'Maximize' if the objective is to Minimize.

 

Click Submit. The website will go to the job queue to show the job status. The web page will need to be refreshed to update the status of the job solution process. The job will have a status of 'FinishedSuccess' when it has completed successfully.

 

Download the QUBO solution. The solution download is available from the Job Queue.

 

 

EXAMPLE:

 

Consider the problem:

Minimize

where the variables, , are binary. Observations:

1.     The function to be minimized is a quadratic function in binary variables with a linear part and a quadratic part .

 

2.     Since binary variables satisfy , the linear part can be written as

3.     Then we can re-write the model in the following matrix form:

Minimize

4.     In turn, this can be written in the matrix notation introduced in Section 1 as

QUBO: Minimize

where x is a column vector of binary variables and Q is the symmetric matrix

Note on input Format: The Alpha-Qubo code assumes the Q matrix is in symmetric form. Preparing this QUBO model for solution via the Alpha-QUBO system involves presenting the non-zero diagonal and upper triangular elements of Q in an input file as shown below. Due to symmetry, the bottom triangular elements are automatically picked up by the code and do not have to be entered.

 

p 4 8

1 1 -5

1 2 2

1 3 4

2 2 -3

2 3 1

3 3 -8

3 4 5

4 4 -6

 

 

As shown above, there are 8 non-zero elements that need to be specified. Symmetry, together with the fact that any unspecified element is assumed to be zero, assures this input file completely specifies the full Q matrix and the QUBO instance to be solved.

 

 

 

 

Solving via Alpha-QUBO gives:

seed = 783458 f_best = -11 t_best = 0.01

Best Solution :

1 0 0 1

5.     As shown by f_best and the Best Solution, the solution to the model in (3) above is:

 

 

Note on Alternative Representations: Some QUBO formulations assume the matrix is represented in compact upper triangular form instead of using the symmetric form shown in the preceding example. The compact upper triangular form doubles the size of the off-diagonal coefficients and consequently all such coefficients not on the main diagonal of the compact form should be halved to give the coefficients of our symmetric form although we only require the upper triangular half of these coefficients to be input, as also shown in the example.

 

We welcome your suggestions for how we can make the Alpha-QUBO software easier to use. Send us an email at support@meta-analytics.com