0-1线性规划

描述：取值于二进制变量的线性规划问题

形式： $$ \text{minimize} c_0x_0+\cdots c_mx_m\quad s.t. Ax\leqslant b, x_j\in{0,1}, j=0,\cdots,m $$

其中$c_j\in\mathbb{Z},A\in M(\mathbb{Z}),x=(x_0,\cdots,x_m)^\mathrm{T},b\in\mathbb{Z}^m$

QUBO范式建模：

不等式 $\to$ 等式：松弛变量

例 $3x_0-x_1+3x_2\leqslant 4$
1. 确定下界：令正系数变量取0，负系数变量取1，得下界-1
2. 添加松弛变量：为保证$3x_0-x_1+3x_2$取$\{-1,\cdots,4\}$时等式成立，松弛变量最大需能取到5，利用二进制拆分思想添加松弛变量$y_1,y_2,y_3\in\{0,1\}$，考虑等式$3x_0-x_1+3x_2+y_1+2y_2+4y_3=4$
3. 调整系数：$y_1+2y_2+4y_3$最大能取到7，将$y_3$系数调整为2，得到符合条件的等式$3x_0-x_1+3x_2+y_1+2y_2+2y_3=4$作为$3x_0-x_1+3x_2\leqslant 4$的替代 + 方程组有解问题 $\to$ 最值问题：惩罚项
例 $\begin{array}{rl}\text{minimize}&-5x_0+3x_1-2x_2\\ s.t.&x_0+x_2+y_0=1,\\&3x_0-x_1+3x_2+y_1+2y_2+2y_3=4,\\&x_j\in\{0,1\},\quad j=0,1,2,\\&y_j\in\{0,1\},\quad j=0,1,2,3.\end{array}$
1. 添加惩罚项：将约束以惩罚项的形式添加至目标式中，原问题转化为 $\begin{array}{rl}\text{minimize}&-5x_0+3x_1-2x_2+B(x_0+x_2+y_0-1)^2\\&+B(3x_0-x_1+3x_2+y_1+2y_2+2y_3-4)^2\\ s.t.&x_j\in\{0,1\},\quad j=0,1,2,\\&y_j\in\{0,1\},\quad j=0,1,2,3.\end{array}$ 其中$B$为惩罚系数
2. 确定惩罚系数：为了使所有不满足约束的取值，都不会取到当前目标式的最小值，当$B$取充分大时即可满足。具体而言，无约束条件下，原目标式$-5x_0+3x_1-2x_2$取值范围$\{-7,\cdots,3\}$，当$B$取11时，任何不满足约束的取值都将大于原目标式的最大可能取值，从而得到该问题的等价形式$\begin{array}{rl}\text{minimize}&-5x_0+3x_1-2x_2-11(x_0+x_2+y_0-1)^2\\&-11(3x_0-x_1+3x_2+y_1+2y_2+2y_3-4)^2\\ s.t.&x_j\in\{0,1\},\quad j=0,1,2,\\&y_j\in\{0,1\},\quad j=0,1,2,3.\end{array}$

推广：整数线性规划

应用：背包问题#0-1背包