0

我希望使用整数规划来枚举帕累托最优解。我想实现一个算法，使用 gurobi 或类似的单目标整数规划求解器来做到这一点，但我不知道任何这样的算法。有人可以提出一个枚举有效边界的算法吗？

4

2 回答 2

1

在这个答案中，我将讨论如何枚举形式为 2 目标纯整数优化问题的所有帕累托有效解决方案

min_x {g'x, h'x}
s.t.  Ax <= b
      x integer

算法

我们通过优化其中一个目标来启动算法（我们将g在此处使用）。由于这是一个标准的单目标整数优化问题，因此可以使用 gurobi 或任何其他 LP 求解器轻松求解：

min_x g'x
s.t.  Ax <= b
      x integer

我们初始化一个集合P，它最终将包含所有的帕累托有效解， 为P = {x*}，其中x*是该模型的最优解。为了得到有效边界上的下一个点，它具有第二小的g'x值和改进的h'x值，我们可以在我们的模型中添加以下约束：

  1. 从可行的解决方案集中删除x*（有关这些x != x*约束的详细信息将在答案后面提供）。
  2. 添加一个约束h'x <= h'x*

我们需要解决的新优化模型是：

min_x g'x
s.t.  Ax <= b
      x != x* for all x* in P
      h'x <= h'x* for all x* in P
      x integer

同样，这是一个单目标整数优化模型，可以使用 gurobi 或其他求解器求解（一旦您按照下面有关如何建模x != x*约束的详细信息进行操作）。当您反复求解此模型时，将最优解添加到 中P，解将获得逐渐变大（更差）的g'x值和逐渐变小（更好）h'x的值。最终，模型将变得不可行，这意味着帕累托边界上不再存在点，算法终止。

此时，可能存在一些解x, y对P其中g'x = g'y和h'x > h'y，在这种情况下，以 和x为主y，可以去除。以这种方式过滤后，该集合P代表了完整的帕累托有效边界。

x != x*约束

剩下的就是对形式的约束进行建模x != x*，其中x和x*是整数变量的 n 维向量。即使在一维上，这也是一个非凸约束（详见此处），因此我们需要添加辅助变量来帮助我们对约束进行建模。

将n存储在优化模型中的变量（统称为x）表示为x_1, x_2, ..., x_n，并且类似地将变量值表示x*为x*_1, x*_2, ..., x*_n。我们可以y_1, y_2, ..., y_n在模型中添加新的二元变量，其中y_i设置为 1 时x_i > x*_i。因为x_i和x*_i是整数值，这与 说 相同x_i >= x*_i + 1，这可以通过以下约束来实现（M是一个大常数）：

x_i - x*_i >= 1 - M(1-y_i) for all i = 1, ..., n

同样，我们可以在模型中添加新的二元变量z_1, z_2, ..., z_n，其中z_i设置为 1 时x_i < x*_i。因为x_i和x*_i是整数值，这与说 相同x_i <= x*_i - 1，这可以通过以下大M约束来实现：

x_i - x*_i <= -1 + M(1-z_i) for all i = 1, ..., n

y如果设置了或变量中的至少一个z，那么我们知道我们的x != x*约束得到了满足。因此，我们可以替换x != x*为：

y_1 + y_2 + ... + y_n + z_1 + z_2 + ... + z_n >= 1

简而言之，每个x != x*约束都可以通过在模型中添加2n二元变量和2n+1约束来处理，其中n是原始模型中的变量数。

于 2015-08-26T04:53:34.450 回答
1

PolySCIP是用于多目标混合整数线性规划的学术开源求解器。如果您不想实现自己的求解器或想将自己的求解器与另一个求解器进行比较。

于 2015-08-28T07:31:29.573 回答