组合优化问题

组合优化（CO）领域是优化领域最重要的领域之一，在各个行业（包括私营和公共部门）都有实际应用。一般地，这些问题涉及在必须大量做出是/否决策并且每组决策产生相应的目标函数值（例如成本或者利润值）的环境中做出明智的选择。在这些环境中找到好的解决方案是极其困难的。

QUBO（二次无约束二元优化问题的缩写）的数学公式可以涵盖工业、数学和政府中发现的各种组合优化问题。

QUBO模型在组合优化中包含许多模型能力的重要性得到增强，因为QUBO模型可以被证明与物理学中发挥着重要作用的Ising模型等效，通过最先进的QUBO求解方法有效解决广泛优化问题与物理应用中出现的重要问题领域相结合。

QUBO模型在以下重要的优化问题领域适用： - 二次分配问题 - 资金预算问题 - 多背包问题 - 任务分配问题 - 最大多样性问题 - 不对称分配问题 - 对称分配问题 - 约束满足问题 - ........

基本的QUBO公式

QUBO公式： $$ QUBO:minimize/maximize\quad y=x^tQx $$

• x：二元决策变量的向量（一个元素只包含0和1的向量
• Q：一个常数矩阵。通常Q可以被认为是一个对称或者上三角矩阵，一般将Q作为对称矩阵

一个例子

对于一个优化问题： $$ Minimize\quad y=-5x_1 -3x_2-8x_3-6x_4+4x_1x_2+8x_1x_3+2x_2x_3+10x_3x_4 $$ 变量\(x_j\)是二进制的，我们可以看出：

• 要最小化的函数是二元变量的二次函数，线性部分是\(-5x_1 -3x_2-8x_3-6x_4\)，和二次部分\(4x_1x_2+8x_1x_3+2x_2x_3+10x_3x_4\)
• 由于二进制变量满足\(x_j=x_{j}^{2}\)，线性部分可以写作：\(-5x_1^2 -3x_2^2-8x_3^2-6x_4^2\)
• 我们可以将函数写成下面的矩阵形式： $$ Minimize\quad y=(x_1,x_2,x_3,x_4) \begin{bmatrix}-5&2&4&0\ 2&-3&1&0\ 4&1&-8&5\ 0&0&5&6\end{bmatrix} \begin{bmatrix}x_1 \ x_2 \ x_3\ x_4 \end{bmatrix} $$
• 这样可以得到一个矩阵\(Q\)，以前的线性项在主对称轴上

加入惩罚项

在实际情况中，其实很多问题是带有约束条件的。许多这些约束模型可以有效地重新表述为 QUBO 模型。选择引入的惩罚，以便在优化器寻找避免产生惩罚的解决方案时，可以通过优化器的自然功能来替代原始约束对解决方案过程的影响。也就是说，惩罚被制定为使得对于可行的解决方案它们等于零并且对于不可行的解决方案等于一些正的惩罚金额。对于最小化问题，添加这些惩罚以创建要最小化的增强目标函数。如果可以将惩罚项驱至零，则增强目标函数将成为要最小化的原始函数。

常见的一些惩罚项如下：

经典约束	等价惩罚
\(x+y<=1\)	\(P(xy)\)
\(x+y>=1\)	\(P(1-x-y+xy)\)
\(x+y=1\)	\(P(1-x-y+2xy)\)
\(x<=y\)	\(P(x-xy)\)
\(x_1+x_2+x_3<=1\)	\(P(x_1x_2+x_1+x_3+x_2+x_3)\)
x=y	\(P(x+y-2xy)\)