二进制整数规划中的构造启发式
Construction heuristics in binary integer programming
我一直在努力寻找这个问题的答案，但找不到全面的答案。我正在寻找一种算法或启发式算法来构建二进制整数规划问题的初始可行解，更具体地说是集合打包、集合划分和集合覆盖问题。
如果有如下二元整数规划问题
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。
那么如何构建一个初步可行的解决方案来解决这个问题。当问题包含数千个变量和约束时，遍历所有可能的解决方案显然行不通。
这里的目标是构建一个初始可行方案，以便可以执行局部搜索以获得局部最小值，然后对其应用元启发式算法。
为某些二进制整数规划问题寻找可行解的问题已经NP-complete。这是 Karp 最受欢迎的 21 个 NP 完全问题之一 -> wiki: 0–1 整数规划!
在一般情况下，没有什么比以下完整方法更好的了（完整：如果在有限时间内存在或证明存在[=55，他们将找到可行的解决方案=]):
这些也在内部使用启发式方法（事实上他们必须：因为问题是 NP 完全的）。
如果您不想使用一般 algorithms/software，您必须针对某些问题专门调整您的启发式算法。但是您提到的这些问题有些不同，可能需要不同的启发式方法。分析实例中的特殊结构也很重要（随机实例的行为与大多数现实世界的问题非常不同）！在设计这些特殊用途的启发式算法时，您可能会实施一些 不完整 方法，这可能更适合您的情况。
你面临的问题，寻找一个初始可行解在很多Meta-Heuristics中也很常见！
这是个复杂的话题！
我一直在努力寻找这个问题的答案，但找不到全面的答案。我正在寻找一种算法或启发式算法来构建二进制整数规划问题的初始可行解，更具体地说是集合打包、集合划分和集合覆盖问题。
如果有如下二元整数规划问题
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。
那么如何构建一个初步可行的解决方案来解决这个问题。当问题包含数千个变量和约束时，遍历所有可能的解决方案显然行不通。
这里的目标是构建一个初始可行方案，以便可以执行局部搜索以获得局部最小值，然后对其应用元启发式算法。
为某些二进制整数规划问题寻找可行解的问题已经NP-complete。这是 Karp 最受欢迎的 21 个 NP 完全问题之一 -> wiki: 0–1 整数规划!
在一般情况下，没有什么比以下完整方法更好的了（完整：如果在有限时间内存在或证明存在[=55，他们将找到可行的解决方案=]):
这些也在内部使用启发式方法（事实上他们必须：因为问题是 NP 完全的）。
如果您不想使用一般 algorithms/software，您必须针对某些问题专门调整您的启发式算法。但是您提到的这些问题有些不同，可能需要不同的启发式方法。分析实例中的特殊结构也很重要（随机实例的行为与大多数现实世界的问题非常不同）！在设计这些特殊用途的启发式算法时，您可能会实施一些 不完整 方法，这可能更适合您的情况。
你面临的问题，寻找一个初始可行解在很多Meta-Heuristics中也很常见！
这是个复杂的话题！