如何在CPLEX线性规划中实现基于二进制变量激活的成本函数调整？

核心思路 #

线性规划（LP）不支持动态修改成本系数，必须通过引入辅助变量+线性化逻辑约束的方式，把需求转化为等价的线性模型，兼容CPLEX求解。

具体实现步骤 #

1. 引入辅助二进制变量y #

定义二进制变量y：

• y=1：当且仅当efficiency_set中至少有一个变量x_i取值为1
• y=0：当efficiency_set中所有变量取值为0

2. 关联y与efficiency_set的变量约束 #

有两种方式实现该关联，任选其一即可：

方式一：CPLEX原生逻辑约束（更简洁）

直接用CPLEX的indicator约束定义y的取值逻辑：

// 伪代码：假设model为CPLEX模型对象，x是二进制变量数组，S为efficiency_set的索引集合
IloExpr sumS(model);
for (auto i : S) sumS += x[i];
// 当y=1时，sumS >=1；当y=0时，sumS=0
model.add(sumS >= 1).setIndicator(y, 1);
model.add(sumS == 0).setIndicator(y, 0);
sumS.end();

方式二：手动线性约束

添加两个线性约束实现等价逻辑：

• sum(x_i for i in S) >= y：确保只要有一个x_i=1，y必须为1
• sum(x_i for i in S) <= 5*y：确保当y=0时，所有x_i必须为0（因efficiency_set共5个变量，最大和为5）

3. 重构目标函数 #

原目标函数为minimize sum(c_i * x_i for all i)，需根据y的取值调整efficiency_set内变量的成本：

• 当y=0：成本保持原系数c_i
• 当y=1：efficiency_set内变量成本变为0.9*c_i

将目标函数改写为线性形式：

minimize sum(c_i * x_i for all i) - 0.1*sum(c_i * w_i for i in S)

其中w_i是为线性化x_i*y引入的连续变量（取值0~1），需添加以下约束确保w_i等价于x_i*y：

• w_i <= x_i
• w_i <= y
• w_i >= x_i + y - 1
• w_i >= 0

4. 完整模型整合 #

将上述约束和目标函数加入原CPLEX模型，所有变量仍保持二进制特性（w_i为连续变量但取值0~1，不影响求解效率）。

CPLEX代码示例（伪代码） #

IloEnv env;
IloModel model(env);

// 原二进制变量（100个）
IloNumVarArray x(env, 100, 0, 1, ILOINT);
// 辅助二进制变量y
IloNumVar y(env, 0, 1, ILOINT);
// 线性化乘积的辅助变量（5个对应efficiency_set）
IloNumVarArray w(env, 5, 0, 1);

// 添加原模型约束Ax <= b
// ...（此处插入原模型的约束代码）

// 关联y与efficiency_set的约束
IloExpr sumS(env);
for (int i=0; i<5; i++) sumS += x[i];
model.add(sumS >= y);
model.add(sumS <= 5*y);
sumS.end();

// 添加w_i的线性化约束
for (int i=0; i<5; i++) {
    model.add(w[i] <= x[i]);
    model.add(w[i] <= y);
    model.add(w[i] >= x[i] + y - 1);
    model.add(w[i] >= 0);
}

// 构建重构后的目标函数
IloExpr obj(env);
for (int i=0; i<100; i++) obj += c[i] * x[i];
for (int i=0; i<5; i++) obj -= 0.1 * c[i] * w[i];
model.add(IloMinimize(env, obj));
obj.end();

// 求解模型
IloCplex cplex(model);
cplex.solve();

// 获取结果（示例）
if (cplex.getStatus() == IloAlgorithm::Optimal) {
    // 输出x的取值、目标值等
}

env.end();

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