如何基于CPLEX(DOCPLEX)批量优化求解多组参数LP问题

问题背景 #

我使用Python的CPLEX（DOCPLEX）求解基础线性规划问题：min c*x，约束条件为A*x = b。需要针对1万至10万组不同的b和c组合（A固定）重复求解该LP问题，以找出最优解。当前每次迭代都需重新创建目标函数和约束条件，初始化步骤占总处理时间的75%，实际求解仅占25%，因此需要优化速度。希望通过“模板”方式创建问题，仅在每组(b,c)组合时传入参数求解，类似CVXPY的机制，但未在CPLEX/DOCPLEX文档中找到对应方法。

原实现代码 #

初始化代码：

self._a = <GENERATE FIXED A>
        self._model = _model.Model()
        self._x = self._model.integer_var_list(self._a.shape[1])

求解函数：

def _solve(self, coeffs: np.array, b: np.array) -> float:
        self._model.minimize(self._model.sum(self._model.dot(self._x, coeffs)))
        self._model.clear_constraints()
        self._model.add_constraints(
            self._model.dotf(self._x, lambda j: self._a[i][j]) == b[i]
            for i in range(self._num_colours)
        )
        sol = self._model.solve()
        return sol.get_objective_value()

优化方案 #

核心思路：复用约束与目标结构，仅更新系数 #

避免每次迭代重建约束和目标，而是一次性创建结构，仅修改可变的c（目标系数）和b（约束右侧值）。

1. 预创建约束并存储，仅更新RHS值

在初始化阶段就创建所有约束，后续迭代只修改约束的右侧值，无需清空重建：

self._a = <GENERATE FIXED A>
        self._model = _model.Model()
        self._x = self._model.integer_var_list(self._a.shape[1])
        
        # 预创建所有等式约束，初始RHS设为0（后续会覆盖）
        self._constraints = []
        for i in range(self._num_colours):
            # 构建A*x的表达式（A固定，无需重复创建）
            expr = self._model.dotf(self._x, lambda j: self._a[i][j])
            constr = self._model.add_constraint(expr == 0)
            self._constraints.append(constr)

2. 预定义目标表达式，仅更新系数

提前定义目标表达式的结构，每次迭代只更新变量的系数：

# 初始化时预定义目标表达式，初始系数为0
        self._objective_expr = self._model.sum(self._x[j] * 0 for j in range(len(self._x)))
        self._model.minimize(self._objective_expr)

3. 修改后的求解函数

def _solve(self, coeffs: np.array, b: np.array) -> float:
        # 更新目标函数的系数（对应c向量）
        for j in range(len(self._x)):
            self._objective_expr.set_coefficient(self._x[j], coeffs[j])
        
        # 更新所有约束的右侧值（对应b向量）
        for i in range(self._num_colours):
            self._constraints[i].rhs = b[i]
        
        # 求解并返回结果
        sol = self._model.solve()
        return sol.get_objective_value()

额外性能优化建议 #

• 关闭日志输出：初始化模型时添加self._model.parameters.output.clonelog.set(0)，减少不必要的IO开销
• 批量操作优化：如果coeffs和b是numpy数组，可尽量减少循环内的冗余操作（比如提前将数组转为Python列表，减少numpy与DOCPLEX的类型转换开销）
• 尝试低级API：若DOCPLEX的封装仍有性能瓶颈，可直接使用CPLEX的cplex核心API，通过修改问题的目标系数矩阵和RHS向量实现更高效的重复求解

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