新手教程1-如何生成QUBO矩阵

目录

新手教程1-如何生成QUBO矩阵#

引言#

最大割问题是图论中经典的组合优化问题，在实际应用中有着广泛的应用。它的核心思想是将一个图的节点划分成两个集合，使得划分后两个集合之间的边的权重之和最大化。在本文中，我们将以最大割问题为例，介绍如何使用 Kaiwu SDK 来建立对应的 QUBO（ Quadratic Unconstrained Binary Optimization，二次无约束二值优化）模型，并将其转化为 QUBO 矩阵。

QUBO 建模#

给定一张图，求一种分割方法，将所有顶点分割成两部分，目标是使得被切断的边的数量最大，或边的总权重最大。以无向无权图为例。在图 $G(V,E)$ 中， $V$ 为图的顶点集合， $E$ 为图的边集， $w$ 为图的邻接矩阵。对于 $i,j \in V$ ， $w_{ij}$ 表示顶点 $i$ 到顶点 $j$ 是否有边，有连边关系则取 $1$ , 无连边关系则取 $0$ 。以决策变量 $x_i$ 表示顶点 $i$ 的分类，其可能的取值为 $\{0,1\}$ ，分别表示将顶点 $i$ 分为A类或B类。

则在给定的无向图中，将所有顶点分割成两群的分割方法所对应割取的边的个数为：

$\max Z= \sum_{(i,j)\in E}{(x_{i}+x_{j}-2x_{i}x_{j})}$

建模代码#

输入矩阵#

import numpy as np
import kaiwu as kw
import pandas as pd

# Define the input adjacency matrix for the graph
adj_matrix = np.array([
                [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 0 ,1, 0],
                [1, 0, 1, 0, 0, 1, 0, 1, 0, 1],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 1],
                [0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                [1, 1, 0, 0, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 1, 0, 1, 0, 1, 0, 1],
                [0, 0, 0, 0, 1, 1, 1, 0, 1, 0]])

# Get the number of nodes in the graph
num_nodes = len(adj_matrix)

# Create a QUBO variable array 'x' with 'num_nodes' variables
# each representing a node in the graph
x = kw.qubo.ndarray(num_nodes,'x',kw.qubo.Binary)

# Define the objective function for the QUBO model of Max cut problem
obj = -x.T @ adj_matrix @ (1-x)

# parse QUBO
obj = kw.qubo.make(obj)

# Extract the QUBO matrix and store it in a pandas DataFrame
qubo_matrix = kw.qubo.qubo_model_to_qubo_matrix(obj)['qubo_matrix']

# Check whether the QUBO matrix satisfy the precision requirement
kw.qubo.check_qubo_matrix_bit_width(qubo_matrix)

# Save the QUBO matrix to a CSV file without including index or header
df = pd.DataFrame(qubo_matrix)
csv_file_path = 'qubo_matrix.csv'
df.to_csv(csv_file_path,index=False,header=False)