多目标优化

在现实应用与决策系统中，需要优化的目标往往不只有一个。例如在供应链管理中，既希望最小化库存成本， 又希望最大化订单满足率，COPT提供多目标优化功能，合理权衡各个目标的优先级或权重，采用分层法和加权组合法， 以实现多目标场景下综合的最优决策。

多目标函数建模

在多目标优化中，目前支持线性的目标函数，通过调用API方法 Model.setObjectiveN() 设置。

在构建多目标函数时，需要设置以下几个关键参数。

  • MultiObjPriority

    多目标优化中，目标函数的优先级，取值越大表示优先级越高。 对应分层法中指定目标的求解顺序。

    默认值 0.0

  • MultiObjWeight

    多目标优化中，目标函数的权重。 对应加权组合法中指定目标线性加权的系数。

    默认值 1.0

  • MultiObjAbsTol

    多目标优化中，目标函数的绝对偏离容差。

    COPT按优先级依次优化各目标： 在多目标混合整数规划中，若当前目标的最优目标值为 z ，则后续优化阶段中， 允许在不超过 MultiObjAbsTol 的范围内偏离其目标函数最优值； 在多目标（连续型）线性规划中，该参数作用于变量。为了保证高优先级目标解的质量，COPT 依据递减成本（reduced cost）固定部分变量的最优解值， 这些固定变量的递减成本允许在不超过 MultiObjAbsTol 的范围内偏离对偶可行性（dual feasibility）条件。

    默认值 1e-6

  • MultiObjRelTol

    多目标优化中，目标函数的相对偏离容差。

    COPT按优先级依次优化各目标： 在多目标混合整数规划中，若当前目标的最优目标值为 z ，则后续优化阶段中， 允许其最优目标值的偏离范围为 MultiObjRelTol * |z| ； 在多目标（连续型）线性规划中，目标偏离程度通过 MultiObjAbsTol 控制， MultiObjRelTol 将被忽略。

    默认值 0.0

注意：

  • 以上四个参数仅适用于多目标函数；

  • 在向模型中添加多目标函数 setObjectiveN 时，除了指定以上四个参数之外，还需指定目标函数的编号、目标表达式和优化方向。

多目标函数参数的相关操作如下（以COPT Python接口为例）：

  1. 通过调用 Model.setObjParamN(idx, paramname, newval) 设置指定编号的目标函数参数；

  2. 通过调用 Model.getObjParamN(idx, paramname) 获取指定编号的目标函数参数取值；

  3. 通过调用 Model.resetObjParamN(idx) 重置指定编号的目标函数参数为默认值。

多目标函数求解

在求解多目标模型时，COPT采用分层法（hierarchy method）和加权组合法（weighted-sum method）。

分层法

分层法基于每个目标函数的优先级，按照优先级从高到低依次进行优化。 COPT会在不影响高优先级目标的结果质量的前提下，寻找当前目标函数的最优解。 用户可以在设置多目标函数 Model.setObjectiveN() 时指定优先级； 也可以调用 Model.setObjParamN() 设置指定编号目标函数的优先级。每个目标函数的默认优先级为0.0。

假设多目标模型中，目标函数 \(obj_1\) 和 \(obj_1\) 拥有不同的优先级，分别为3和2， 那么COPT会先求解 \(obj_1\) 对应的优化模型，接着COPT会在满足 \(obj_1\) 的偏离容差范围内，求解 \(obj_2\) 对应的优化模型。

加权组合法

对于相同优先级下的多个目标函数，COPT采用加权组合法，基于权重对多个目标进行线性组合， 构建出一个加权合成的目标函数。用户可以在设置多目标函数 Model.setObjectiveN() 时指定权重； 也可以调用 Model.setObjParamN() 设置指定编号目标函数的权重参数。每个目标函数的默认权重为1.0。

假设多目标模型中，相同优先级的一组目标函数为：\(\text{min}\ f_1(x)\) 和 \(\text{min}\ f_2(x)\) ， 并且它们的权重分别设置为 \(w_1\) 和 \(w_2\) ，那么COPT采用加权组合法构建的合成目标函数如下：

(44)\[\min\ w_1 \cdot f_1(x) + w_2 \cdot f_2(x)\]

注意：

  • 请谨慎设置权重为负数，因为相当于改变优化方向。

  • 避免为目标函数设置过大或过小的权重：若某个目标权重很大，会导致合成后的目标函数系数过大，可能会影响数值稳定性；若某个目标权重很小，可能导致对合成后目标函数的影响低于偏离容差，求解时会被忽略。

在多目标优化模型中，COPT支持结合分层法和加权组合法。每个目标函数可以同时拥有相同或不同的优先级与权重参数。 COPT首先会根据优先级顺序依次求解，对于相同优先级下的多个目标函数，COPT再加权组合为一个合成的目标函数进行求解。

我们结合如下具体示例来解释COPT的工作流程。假设多目标优化模型包含四个目标函数：

(45)\[\begin{split}\begin{aligned} &\min\ \text{obj}_1 = f_1(x) && \text{(priority = 2,\ weight = 1.0)} \\ &\max\ \text{obj}_2 = f_2(x) && \text{(priority = 1,\ weight = 2.5)} \\ &\max\ \text{obj}_3 = f_3(x) && \text{(priority = 1,\ weight = 1.5)} \\ &\min\ \text{obj}_4 = f_4(x) && \text{(priority = 0,\ weight = 1.0)} \\ \end{aligned}\end{split}\]

首先COPT采用分层法，根据优先级（2，1，0）划分为三组优化模型依次求解，针对priority = 1下的两个目标函数根据权重合成。

Priority = 2:

(46)\[\min\ f_1(x)\]

Priority = 1:

(47)\[\max\ 2.5 \cdot f_2(x) + 1.5 \cdot f_3(x)\]

Priority = 0:

(48)\[\min\ f_4(x)\]

目标函数的偏离程度

在使用分层法进行多目标优化时，可以通过 MultiObjRelTol （目标函数的相对偏离容差） 和 MultiObjAbsTol （目标函数的绝对偏离容差）来控制多目标函数对其前一优先级目标允许偏离的程度。

1.混合整数规划

对于整数规划模型来说，若某个目标函数 \(\min\ z_1\) 的最优值为 \(v\) ，且该目标对应的 MultiObjAbsTol=e ， 那么在求解其后一优先级的目标函数 \(\min\ z_2\) 时，COPT会在 \(z_2 \leq v + e\) 的可行解域中寻找 \(\min\ z_2\) 的最优解。

对于整数规划模型来说，若某个目标函数 \(\min\ z_1\) 的最优值为 \(v\) ，且该目标对应的 MultiObjRelTol=q ， 那么在求解其后一优先级的目标函数 \(\min\ z_2\) 时，COPT会在 \(z_2 \leq v + q*|v|\) 的可行解域中寻找 \(\min\ z_2\) 的最优解。

注意：如果同时设置了相对容差与绝对容差，COPT将使用两者中允许偏离程度较大的那个值。

2.线性规划

对于连续型线性规划模型来说，为了保证高优先级模型结果的质量，COPT会固定一些变量为前一优先级的最优解。 这些变量是否被固定，是通过其递减成本（reduced cost）是否在 MultiObjAbsTol 的范围内偏离 对偶可行性（dual feasibility）条件来判断的。

注意： MultiObjRelTol 在线性规划模型中将被忽略。

多目标函数优化结果

多目标函数优化的结果信息可以通过 Model.getAttrN(idx， attrname) （以面向对象接口Python为例，其他接口类似）获取。

  • idx ：多目标函数的编号

  • attrname ：多目标函数的属性

支持获取的多目标函数属性值包括： HasQObj ， HasNLObj ， LpObjval ， BestObj ， ObjSense ， ObjConst 。