能否在IBM CPLEX等求解器中编写路径唯一节点数≤K的约束？

当然可以实现这个约束，核心思路是引入节点层面的辅助变量追踪被选中路径覆盖的节点，再通过线性约束关联路径变量与辅助变量，最后限制被覆盖节点的总数。具体步骤如下：

1. 定义辅助变量 #

对图中的每个节点i，引入二元决策变量y_i：

• y_i = 1：节点i被至少一条选中的路径包含
• y_i = 0：节点i未被任何选中的路径包含

2. 添加路径与节点的关联约束 #

为确保选中路径的所有节点都被标记为“已覆盖”，添加如下约束：

对每个节点i，以及每个包含i的路径p，满足：y_i ≥ x_p

这个约束逻辑直接：若路径p被选中（x_p=1），则路径上所有节点i的y_i必须为1；若路径p未被选中（x_p=0），则对y_i无强制要求。

3. 添加节点总数限制约束 #

最后直接限制被覆盖节点的总数不超过K：
sum_{i=1}^N y_i ≤ K

CPLEX OPL 示例代码 #

用CPLEX的OPL语言实现的代码示例如下：

// 假设Paths是所有源到目标的路径集合，Nodes是所有节点集合
dvar boolean x[p in Paths];
dvar boolean y[i in Nodes];

// 关联路径与节点的约束
forall(i in Nodes, p in Paths : i in p)
  y[i] >= x[p];

// 限制唯一节点总数不超过K
sum(i in Nodes) y[i] <= K;

// 此处添加你的目标函数
maximize ...; // 或 minimize ...;

适用范围 #

这种方法适用于所有支持整数线性规划（ILP）的求解器（如CPLEX、Gurobi、SCIP等），所有约束均为线性，变量为二元整数变量，求解器可直接处理。

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