如何在scipy.optimize.milp标准矩阵中集成布尔逻辑约束

变量定义 #

• 原始布尔变量：a, b, c, d, e, f, g, h, i, j, k, l（共12个，索引0到11）
• 辅助变量：本次示例无需额外辅助变量，所有约束可直接通过原始变量线性表示

目标函数 #

最小化所有原始变量的和，对应目标向量c：

import numpy as np
# 12个原始变量系数均为1
c = np.ones(12)

约束条件转换（标准矩阵形式） #

所有布尔约束需转换为线性不等式/等式，对应scipy.optimize.milp要求的A_ub, b_ub（上界约束，满足A_ub @ x ≤ b_ub）、A_eq, b_eq（等式约束，满足A_eq @ x = b_eq）：

1. a OR b 为真 #

等价于线性约束：a + b ≥ 1，转换为标准上界约束形式（两边乘-1）：
-a -b ≤ -1
对应A_ub行：[-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]，b_ub对应值：-1

2. c AND d 为真 #

等价于c=1且d=1，对应两个等式约束：
c = 1、d = 1
对应A_eq两行：[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]、[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]，b_eq对应值：[1, 1]

3. e XOR f 为真 #

异或表示两个变量一真一假，等价于线性约束：e + f = 1
对应A_eq行：[0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]，b_eq追加值：1

4. g NAND h 为真 #

NAND表示“不同时为真”，等价于线性约束：g + h ≤ 1
对应A_ub行：[0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]，b_ub对应值：1

5. i != j 为真 #

等价于两个变量一真一假，对应线性约束：i + j = 1
对应A_eq行：[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]，b_eq追加值：1

6. k == l 为真 #

等价于两个变量取值相同，对应线性约束：k - l = 0
对应A_eq行：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1]，b_eq追加值：0

完整矩阵构建代码 #

import numpy as np

# 变量总数：12个原始布尔变量
n_vars = 12

# 目标函数向量
c = np.ones(n_vars)

# 上界约束矩阵与向量
A_ub = np.array([
    [-1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # a OR b
    [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]     # g NAND h
])
b_ub = np.array([-1, 1])

# 等式约束矩阵与向量
A_eq = np.array([
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],    # c = 1
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],    # d = 1
    [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],    # e XOR f
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],    # i != j
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1]    # k == l
])
b_eq = np.array([1, 1, 1, 1, 0])

# 变量上下界：所有变量取值为0或1
bounds = [(0, 1)] * n_vars

# 整数性设置：所有变量为二进制类型（3对应scipy.milp的二进制变量标识）
integrality = np.repeat(3, n_vars)

通用布尔逻辑转MILP核心规则 #

针对任意布尔表达式，可通过以下规则线性化：

• OR（多变量）为真：x₁ + x₂ + ... + xₙ ≥ 1，转换为标准上界形式：-x₁ -x₂ -...-xₙ ≤ -1
• AND（多变量）为真：每个变量xᵢ = 1，对应n个等式约束；若AND结果需用辅助变量z表示，则添加约束z ≤ xᵢ（所有i）且z ≥ x₁+x₂+...+xₙ - (n-1)
• XOR（双变量）为真：x + y = 1；多变量XOR需拆分后引入辅助变量
• NAND（双变量）为真：x + y ≤ 1
• NOT x 为真：x = 0
• x == y：x - y = 0
• x != y：x + y = 1

复杂布尔表达式可拆分为原子逻辑逐步转换，必要时引入辅助变量实现非线性逻辑的线性化。

内容的提问来源于stack exchange，提问作者ABC