如何在CPLEX中借助OPL实现Epsilon约束法求解双/多目标优化问题

1. CPLEX 中Epsilon约束法的通用实现 #

Epsilon约束法核心逻辑为：选择一个目标作为主优化目标，其余全部目标转化为约束，将约束阈值设为可调参数ε，通过调整ε的取值遍历整个帕累托前沿。
以下为Python调用CPLEX API的实现示例（双目标最大化场景）：

import cplex
from cplex.exceptions import CplexError

# 替换为你的问题变量数、原有约束、f1和f2的线性系数
VAR_NUM = 2
f1_coeff = [3, 2]
f2_coeff = [1, 4]

# 单目标求解工具函数，用于计算目标的取值范围
def solve_single_obj(target_coeff, is_max=True):
    prob = cplex.Cplex()
    prob.set_results_stream(None) # 关闭求解日志，需要可注释此行
    prob.variables.add(names=[f"x{i}" for i in range(VAR_NUM)], lb=[0]*VAR_NUM)
    prob.objective.set_sense(prob.objective.sense.maximize if is_max else prob.objective.sense.minimize)
    # 添加原有问题的约束，示例：x+y<=10，2x+3y<=25，替换为你的实际约束
    prob.linear_constraints.add(
        lin_expr=[[[0,1], [1,1]], [[0,1], [2,3]]],
        senses=["L", "L"],
        rhs=[10, 25]
    )
    prob.objective.set_linear([(i, coeff) for i, coeff in enumerate(target_coeff)])
    prob.solve()
    return prob.solution.get_objective_value(), prob.solution.get_values()

# 第一步：计算f1的取值区间，确定ε的步进范围
f1_max, _ = solve_single_obj(f1_coeff, is_max=True)
f1_min, _ = solve_single_obj(f1_coeff, is_max=False)
step = (f1_max - f1_min)/10 # 拆分为10个ε点，可根据需求调整密度
pareto_solutions = []

# 第二步：迭代调整ε，求解所有帕累托解
for eps in [f1_min + i*step for i in range(11)]:
    prob = cplex.Cplex()
    prob.set_results_stream(None)
    prob.variables.add(names=[f"x{i}" for i in range(VAR_NUM)], lb=[0]*VAR_NUM)
    # 主目标设置为f2最大化
    prob.objective.set_sense(prob.objective.sense.maximize)
    prob.objective.set_linear([(i, coeff) for i, coeff in enumerate(f2_coeff)])
    # 添加原有约束 + epsilon约束：f1 >= eps
    prob.linear_constraints.add(
        lin_expr=[[[0,1], [1,1]], [[0,1], [2,3]], [list(range(VAR_NUM)), f1_coeff]],
        senses=["L", "L", "G"],
        rhs=[10, 25, eps]
    )
    try:
        prob.solve()
        if prob.solution.get_status() == prob.solution.status.optimal:
            f1_val = sum([f1_coeff[i]*prob.solution.get_values(i) for i in range(VAR_NUM)])
            f2_val = prob.solution.get_objective_value()
            pareto_solutions.append({
                "f1": round(f1_val,4),
                "f2": round(f2_val,4),
                "x": prob.solution.get_values()
            })
    except CplexError:
        continue

# 输出结果
print("帕累托前沿：")
for sol in pareto_solutions:
    print(f"f1={sol['f1']}, f2={sol['f2']}, x={sol['x']}")

2. OPL工具中使用Epsilon约束法求解多目标问题 #

OPL可通过内置脚本块直接实现迭代逻辑，无需调用外部API，实现流程如下：

步骤1：编写模型文件（.mod） #

// 定义变量
dvar float+ x;
dvar float+ y;

// 定义两个目标函数
float f1 = 3*x + 2*y;
float f2 = x + 4*y;

// 定义epsilon参数，迭代过程中自动更新
float eps;

// 原有约束 + epsilon约束
subject to {
    x + y <= 10;
    2*x + 3*y <=25;
    f1 >= eps;
}

// 主目标默认设为最大化f2
maximize f2;

步骤2：编写运行脚本（.run） #

var f1_max, f1_min;
var pareto_front = new Array();

// 先求解f1的取值范围
thisOplModel.generate();
// 求f1最大值
thisOplModel.objective = thisOplModel.f1;
cplex.solve();
f1_max = thisOplModel.f1;
// 求f1最小值
thisOplModel.maximize = false;
cplex.solve();
f1_min = thisOplModel.f1;

// 定义步长
var step = (f1_max - f1_min)/10;

// 迭代求解所有帕累托解
for(var i=0; i<=10; i++){
    thisOplModel.eps = f1_min + i*step;
    // 恢复主目标为最大化f2
    thisOplModel.maximize = true;
    thisOplModel.objective = thisOplModel.f2;
    thisOplModel.generate();
    if(cplex.solve()){
        pareto_front.add({
            f1: thisOplModel.f1,
            f2: thisOplModel.f2,
            x: thisOplModel.x,
            y: thisOplModel.y
        });
    }
}

// 输出结果
writeln("共得到", pareto_front.length, "个帕累托解：");
for(var s in pareto_front){
    writeln("f1=", s.f1, " | f2=", s.f2, " | x=", s.x, " | y=", s.y);
}

扩展说明 #

• 若为最小化场景，仅需调整目标求解方向、将epsilon约束的>=改为<=即可
• 若为3个及以上目标，新增对应epsilon参数，嵌套循环遍历各目标的epsilon取值即可
• 步长可根据所需帕累托解的密度调整，步长越小解数量越多，求解耗时越长

内容的提问来源于stack exchange，提问作者FF-the learner