tamuhey/qubogen

QUBO matrix generator for major combinatorial optimization problems written in Python

QUBOgen

• QUBO matrix generator on major combinatorial optimization problems written in Python

Installation

$ pip install qubogen

Examples

Number Partitioning

How to partition a given multiset of numbers into two subsets S1, S2 such that |sum(S1) - sum(S2)| is as small as possible?

import qubogen

sample multiset

s = np.array([3,1,1,2,2,1])

create qubo matrix with qubogen.qubo_number_partition

qubogen.qubo_number_partition(s)

array([[-21,   3,   3,   6,   6,   3],
       [  3,  -9,   1,   2,   2,   1],
       [  3,   1,  -9,   2,   2,   1],
       [  6,   2,   2, -16,   4,   2],
       [  6,   2,   2,   4, -16,   2],
       [  3,   1,   1,   2,   2,  -9]])

Graph Coloring

• For a given graph, how to color the vertices such that no two adjacent vertices are of same color?

sample graph: builtin data structure qubogen.Graph

edges = [[0,1],[0,4],[1,2],[1,3],[1,4],[2,3],[3,4]]
n_nodes
g = qubogen.Graph(edges=edges, n_nodes=n_nodes)

create qubo matrix with qubogen.qubo_graph_coloring

q=qubogen.qubo_graph_coloring(g, n_color=3)

Other combinatorial optimization problems

qubogen is also available for the below problems:

problem	method
Max-Cut Problem	qubogen.qubo_max_cut
Minimum Vertex Cover Problem (MVC)	qubogen.qubo_mvc
Weighted Minimum Vertex Cover Problem (WMVC)	qubogen.qubo_wmvc
Set Packing Problem	qubogen.qubo_set_pack
Max 2-Sat Problem	qubogen.qubo_max2sat
Set Partitioning Problem (SPP)	qubogen.qubo_spp
General 0/1 Programming	qubogen.qubo_general01
Quadratic Assignment Problem (QAP)	qubogen.qubo_qap
Quadratic Knapsack Problem (QKP)	qubogen.qubo_qkp

Refs

• A Tutorial on Formulating and Using QUBO Models

qubogen's Issues

Quadratic Assignment matrix is different from paper

For the QAP example in the paper I get the following matrix using your code:

[[-400.  200.  200.  200.   40.   75.  200.   16.   30.]
 [ 200.  400.  200.   40.  200.   65.   16.  200.   26.]
 [ 200.  200.  400.   75.   65.  200.   30.   26.  200.]
 [ 200.   40.   75.  400.  200.  200.  200.   24.   45.]
 [  40.  200.   65.  200. -400.  200.   24.  200.   39.]
 [  75.   65.  200.  200.  200.  400.   45.   39.  200.]
 [ 200.   16.   30.  200.   24.   45.  400.  200.  200.]
 [  16.  200.   26.   24.  200.   39.  200.  400.  200.]
 [  30.   26.  200.   45.   39.  200.  200.  200. -400.]]

Whereas the paper has -400 across the whole diagonal. Judging from your unittests this doesn't seem to make a difference though because qbsolv apparently gets the correct solution, but I still find that weird.. Any idea what could be wrong here?

Here's the code I tested with:

import numpy as np


def qubo_qap(flow: np.ndarray, distance: np.ndarray, penalty=10.):
    """Quadratic Assignment Problem (QAP)"""
    n = len(flow)
    q = np.einsum("ij,kl->ikjl", flow, distance).astype(np.float)

    i = range(len(q))
    q[i, :, i, :] += penalty
    q[:, i, :, i] += penalty
    q[i, i, i, i] -= 4 * penalty
    return q.reshape(n ** 2, n ** 2)


X = np.array([
    [0, 5, 2],
    [5, 0, 3],
    [2, 3, 0]
])

Y = np.array([
    [0, 8, 15],
    [8, 0, 13],
    [15, 13, 0]
])

print(qubo_qap(X, Y, 200))

Python code

Hi yohei,
Is there a separate python code to subtract 1 from constraints , Square them and then add them to the mini function to obtain the Q matrix.
Thanks