algorithm - 二进制整数规划中的构造启发式

Question

我一直在努力寻找这个问题的答案，但找不到全面的答案。我正在寻找一种算法或启发式算法来构建二进制整数规划问题的初始可行解，更具体地说是集合打包、集合划分和集合覆盖问题。

如果有如下二元整数规划问题

Minimize      ax_1 + bx_2 + cx_3
Subject to    x_1 + x_2 <= 2
              3x_1 + 3x_2 >= 6
              x_2 + 2x_3 = 2

用解表示

[x_1, x_2, x_3]

其中 x_i = 0 或 1。

那么如何构建这个问题的初步可行解决方案。当问题包含数千个变量和约束时，遍历所有可能的解决方案显然行不通。

此处的目标是构建一个初始可行方案，以便可以执行局部搜索以获得局部最小值，然后对其应用元启发式算法。

Answer 1

为某些二进制整数规划问题寻找可行解的问题已经是NP-complete。这是 Karp 最受欢迎的 21 个 NP 完全问题之一 -> wiki : 0–1 整数规划!

在一般情况下，没有什么能击败以下完整方法(完整:如果在有限时间内存在或证明不存在，他们将找到可行的解决方案):

• 整数规划求解器(单纯形 + 分支定界 + 切割平面)
  • 例如Gurobi , CPLEX (商业)或 CBC/GLPK (开源)
• 约束规划求解器
  • 例如Gecode (开源)
• SAT 求解器
  • 例如MiniSat (开源)

这些也在内部使用启发式方法(事实上他们必须这样做:因为问题是 NP 完全的)。

如果您不想使用通用算法/软件，则必须针对某些问题专门调整您的启发式算法。但是您提到的这些问题有些不同，可能需要不同的启发式方法。分析实例中的特殊结构也很重要(随机实例的行为与大多数现实世界的问题非常不同)!在设计这些特殊用途的启发式方法时，您可能会实现一些不完整方法，这些方法可能更适合您的情况。

你面临的问题，寻找一个初始可行的解决方案在许多元启发式算法中也很常见!

这是一个复杂的话题!