如何限制LP求解器Xij最大值为1以获取每行每列3个1的最优连接方案？

我有一个存储地点间的距离权重矩阵，希望找到每个地点连接3个其他地点、总距离最小的最优解。最初使用运输问题LP求解器的代码如下：

costs6 <- matrix(c(0,399671,1525211,990914,1689886,1536081,399671,0,1802419,1128519,1964930,1603803,1525211,1802419,0,814942,164677,943489,990914,1128519.4,814942.7,0,953202,565712,1689886,1964930,164677,953202,0, 1004916,1536081,1603803,943489,565712,1004916,0),ncol=6,byrow=TRUE)
plantcap <- rep(3,6)
citydemand <- rep(3,6)
plant.signs <- rep("=",6)
city.signs <- rep("=",6)
lptrans <- lp.transport(costs6,"min",plant.signs,plantcap,city.signs,citydemand)
lptrans$solution
lptrans

求解器返回的结果是对角线上全为3的矩阵，显然不符合每个地点连接不同其他地点的需求：

[,1] [,2] [,3] [,4] [,5] [,6]
[1,]    3    0    0    0    0    0
[2,]    0    3    0    0    0    0
[3,]    0    0    3    0    0    0
[4,]    0    0    0    3    0    0
[5,]    0    0    0    0    3    0
[6,]    0    0    0    0    0    3

我想知道是否可以限制任意Xij的最大值为1，让求解器返回每行每列各3个1的结果？如果不行，是否有其他求解器可以用来找到该方案？

1. 修改约束：使用整数规划实现需求 #

你需要的是0-1整数规划而非普通线性规划：强制每个Xij只能取0或1，同时保持每行、每列的和为3。原运输问题求解器默认变量为连续型，因此会选择将所有流量集中在成本最低的对角线位置（距离为0），添加整数约束和变量上限即可解决问题。

使用lpSolve包的lp函数直接构建整数规划模型，代码如下：

library(lpSolve)

# 目标函数：将距离矩阵展开为一维系数向量
obj_coeffs <- as.vector(costs6)

# 构建约束矩阵：
# 前6行约束：每行的变量和为3
row_constraints <- diag(6) %x% rep(1, 6)
# 后6行约束：每列的变量和为3
col_constraints <- rep(1, 6) %x% diag(6)
constraint_matrix <- rbind(row_constraints, col_constraints)

# 约束方向与右侧值：所有约束均为等于3
constraint_dir <- rep("=", 12)
constraint_rhs <- c(rep(3, 6), rep(3, 6))

# 求解整数规划：变量为0-1整数
lp_result <- lp(
  direction = "min",
  objective.in = obj_coeffs,
  const.mat = constraint_matrix,
  const.dir = constraint_dir,
  const.rhs = constraint_rhs,
  all.int = TRUE,  # 强制所有变量为整数
  upper.tri = rep(1, length(obj_coeffs))  # 每个变量上限为1
)

# 将结果转换为6x6矩阵
solution_matrix <- matrix(lp_result$solution, nrow = 6, byrow = TRUE)
print("最优连接矩阵：")
print(solution_matrix)
print("最小总距离：")
print(lp_result$objval)

2. 为什么原lp.transport不适用？ #

lp.transport是专门为连续变量的运输问题设计的，虽然可以通过int.vec参数指定整数变量，但还需要额外添加每个变量≤1的约束，操作起来不如直接用lp函数构建整数规划直观。上述代码直接针对你的需求建模，能准确返回每行每列各3个1的0-1矩阵，满足每个地点连接3个不同地点的要求。

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