代码之家 › 专栏 › 技术社区 › user308225

二元整数规划中的构造启发式

integer-programming mathematical-optimization computer-science optimization algorithm

user308225 · 技术社区 · 8 年前

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

如果有以下二进制整数规划问题:

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。

那么,如何着手构建这个问题的初始可行解决方案呢。当问题由数千个变量和约束组成时,遍历所有可能的解决方案显然是行不通的。

这里的目标是构造一个初始可行值,以便可以执行局部搜索以获得局部极小值,然后对此应用元启发式。

1 回复 | 直到 8 年前

sascha 8 年前

为一些二元整数规划问题找到可行解的问题已经存在 NP完全 这是Karp最流行的21个NP完全问题之一-> wiki : 01整数规划 !

在一般情况下,没有什么比以下情况更好完成方法(完整:如果在有限时间内存在一个可行的解决方案或证明不存在,则他们将找到可行的解决方法):

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

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

您面临的问题是,在许多元启发式中,找到初始可行的解决方案也是非常常见的!

这是一个复杂的话题!

推荐文章

Hatsune Miku · 比较或if语句是否更快[已关闭]

1 年前

Sky Full Of Stars · 最小化工作流程以及部门和工作站之间的距离

1 年前

Black Swan · 无法解压缩的值太多(应为2)错误

1 年前

Kai · 有什么方法可以轻松优化VSCode中的锈迹?

2 年前

Balfar · 处理NumPy阵列上的循环最有效的方法是什么?

2 年前

santobedi · 使用内部支持的优化器优化scikit learn中用于探地雷达的RBF核的核参数

6 年前

Daniel · C#轻松存储快速访问的大型位矩阵

6 年前

halbe · 优化音频DSP程序的numpy计算

6 年前

Afsara · 是否有任何方法不能优化我们的应用程序?

6 年前

user7353167 · R中预算分配的优化(以前叫Excel Solver)

6 年前