如何用Python混合整数线性规划获取区间内所有可行解？

我需要求解一个整数线性问题，目标是找到整数向量x，使得权重向量w与x的点积落在指定区间内，对应数学模型为最小化|w^T @ x - target|。我已通过scipy新推出的milp工具，将问题改写为最大化w^T @ x并添加约束target - error <= w^T @ x <= target + error的形式实现。但当前场景下存在多个满足约束的x向量，请问如何无需借助暴力网格算法（如scipy.brute）获取该区间内的所有可行解？

我的milp实现代码 #

import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds

# 输入参数
ratio_l, ratio_u = 0.2, 3.0
max_bounds = [100, 200, 2, 20, 2]
target = 380.2772 # 338.34175
lambda_parameter = 2
error = lambda_parameter * 1e-6 * target

# 线性目标函数系数
w = np.array([12.0, 1.007825, 14.003074, 15.994915, 22.989769], dtype=np.float64)

# 原目标是最小化 |w^T x - target_mass|
# 改为在约束域内最大化 w^T x
# 约束域：target - error <= w^T x <= target + error

# 变量0和1的约束：ratio_l <= x[1]/x[0] <= ratio_u
# 转换为线性约束：-ratio_u * x[0] + x[1] <= 0，且 -ratio_l * x[0] + x[1] >= 0（此处代码中用了等价的转换方式）

# 线性目标函数
c = w

# 决策变量的整数性：3表示半整数（要么为0，要么在边界范围内）
integrality = 3 * np.ones_like(w)  

# 约束矩阵A
A = np.array([
    # 质量范围约束
    w,
    # x[1]/x[0]的上限约束
    [-ratio_u, 1.0, 0., 0., 0.],
])

# 约束的上下界向量：b_low <= A @ x <= b_up
n_max_C = max_bounds[0]
b_up = [
    target + error,  # 质量上限
    0.,   # x[1]/x[0]上限约束
]
b_low = [
    target - error,  # 质量下限
    (ratio_l - ratio_u) * max_bounds[0],  # x[1]/x[0]下限约束
]

# 构建线性约束
constraints = LinearConstraint(A, b_low, b_up)

# 变量边界
bounds = Bounds(
    lb=[0, 0, 0, 0, 0],
    ub=max_bounds,
)

# 求解MILP
results = milp(
    c=c,
    constraints=constraints,
    integrality=integrality,
    bounds=bounds,
    options=dict(),
)

print(results)

运行结果 #

fun: 380.277405
        message: 'Optimization terminated successfully. (HiGHS Status 7: Optimal)'
 mip_dual_bound: 380.27643944560145
        mip_gap: 2.5390790665913637e-06
 mip_node_count: 55
         status: 0
        success: True
              x: array([19., 40.,  0.,  7.,  0.])

解的验证 #

经计算验证，上述解满足约束：

m = np.dot(w, [19., 40.,  0.,  7.,  0.])
print(f"{'target':>10s} {'calc m':>27s} {'deviation':>27s} {'error':>12s}      match?")
print(f"{target:10.6f} {target - error:14.6f} <= {m:10.6f} <= {target + error:10.6f}"
      f" {m - target:12.6f} {error:12.6f}   -> {target - error <= m <= target + error}")

输出：

target                      calc m                   deviation        error      match?
380.277200     380.276439 <= 380.277405 <= 380.277961     0.000205     0.000761   -> True

其他可行解验证 #

此外，以下两组x向量同样满足约束条件：

第一组：

m = np.dot(w, [20., 39.,  1.,  4.,  1.])
print(f"{'target':>10s} {'calc m':>27s} {'deviation':>27s} {'error':>12s}      match?")
print(f"{target:10.6f} {target - error:14.6f} <= {m:10.6f} <= {target + error:10.6f}"
      f" {m - target:12.6f} {error:12.6f}   -> {target - error <= m <= target + error}")

输出：

target                      calc m                   deviation        error      match?
380.277200     380.276439 <= 380.277678 <= 380.277961     0.000478     0.000761   -> True

第二组：

m = np.dot(w, [21., 38.,  2.,  1.,  2.])
print(f"{'target':>10s} {'calc m':>27s} {'deviation':>27s} {'error':>12s}      match?")
print(f"{target:10.6f} {target - error:14.6f} <= {m:10.6f} <= {target + error:10.6f}"
      f" {m - target:12.6f} {error:12.6f}   -> {target - error <= m <= target + error}")

输出：

target                      calc m                   deviation        error      match?
380.277200     380.276439 <= 380.277951 <= 380.277961     0.000751     0.000761   -> True

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