问题标签 [branch-and-bound]

我正在闪烁一块板，我需要使用一种算法来最大化像 s = c1*x1 + c2*x2 + c3*x3 + c4*x4 这样的表达式，但要受到一些约束。

例如最大化 p = x+y 服从 x+y <= 2, 3x+y >= 4 最优解： p = 2; x = 1, y = 1

有免费的代码可以在某处使用吗？

谢谢

我有一个问题，我找不到答案。我正在使用 Perl。我的输入是一个对称的成本矩阵，有点像 TSP。

我想知道位于我的边界（即 10）之下的所有解决方案。

这是我的矩阵：

有人知道如何实现分支定界算法来解决这个问题吗？现在，我确实用“-”替换了矩阵中的每 10 个。

到目前为止我做了什么：

基本上只是改变矩阵，每10个被替换为“-”。现在我想找到所有低于 10 的解决方案，并且包含 4 个总是两个城市连接在一起的地区。但不幸的是，我不知道如何继续/开始......

我不确定如何组合两个整数列表中的项目，以便保留项目的顺序，并且结果列表（如果连接成一个整数）尽可能小。

可能类似于这个问题，尽管给出的答案没有解决我的大小限制： Interleave different length lists, elimating duplicates and preserve order in Python

例如，给定：

这两个列表的最短可能组合是：

连接整数值为 34574928

在某些情况下，数字的顺序不会影响列表长度，但会影响连接整数的大小。在给出的示例中，可以交换 4 和 9，同时仍保持项目的顺序，但最终数字会比必要的大。

进一步澄清：

最终列表必须包含两个原始列表中每个数字的每个实例。为了更好地表示上述示例中两者的组合：

当然，它不会总是那么干净。在这种情况下，两个列表（3、5、7 和 2）中的四个数字可以完全合并。如果不创建更大的列表，则无法组合其中的四个数字（4、4、9 和 8）。例如：

在这种情况下，我只组合了 3 和 4 之一。当连接这两个示例结果中的项目时，我们得到：

它们都满足排序要求，但是因为有一个不同的结果满足排序要求但在连接成整数时小于 bad_c，所以 bad_c 是不正确的结果。

我已经实现了分支定界算法，算法如下：

1. 找到放宽整数限制的线性规划模型的最优解。
2. 在节点 1 处，放宽解为上限，向下取整的整数解为下限
3. 选择具有最大小数部分的变量进行分支为此变量创建两个新约束，反映分区整数值。结果将是一个新的 <= 约束和一个新的 >= 约束。
4. 创建两个新节点，一个用于 >= 约束，一个用于 <= 约束。
5. 在每个节点处添加新约束来求解松弛线性规划。
6. 松弛解是每个节点的上限，现有的最大整数解（在任何节点）是下限。
7. 如果任何结束节点的最大上限值
8. 返回步骤 3。

实现如下：

现在我必须在实施中做出一些改变。在步骤 3 中，如果正常分支定界方法中唯一的其他变化是在步骤 3，则一旦确定了具有最大小数部分的 xj 的变量，则从该变量开发的两个新约束是 xj=0 和 xj= 1. 这两个新约束将在每个节点处形成两个分支。

问题：

我有一个图，其中每个顶点的布尔状态受给定连接顶点状态的逻辑关系的约束。边缘描述了反应，其中每个反应都有一组激活剂（促进它）、阻遏剂（抑制反应）和产物（可以在反应发生时打开）。对于某些顶点，有一个已知的布尔赋值，它们应该处于哪个状态。我的目标是找到图中所有布尔值的赋值，在遵守图的逻辑约束的同时最大化与已知赋值的一致性。

编辑：这是 ILP 目标和我建议使用的约束：

基本上，我的目标是找到图中所有物种的状态分配，该分配与从数据中已知的状态（M）的“真实”分配最接近。并非图中的所有物种都具有已知状态。

第一个约束规定只有当所有激活物质和抑制物质都不为真时才会发生反应。

第二个约束表示，如果产生物种的反应之一为真，或者如果它被指定为输入节点，则物种可以为真。

从我目前所读到的内容来看，这个问题是 B&B 方法的一个很好的候选者。但是，我无法估计 B&B 和蛮力搜索的时间复杂度。我的猜测是蛮力搜索将是 2^n，其中 n=顶点数，因为这是在最坏情况下由 B&B 树生成的节点总数。但似乎必须评估的约束数量也应该考虑到 B&B 和蛮力的复杂性，但我不确定如何。

我想知道给定一组非常小的项目，一个中等项目和一个非常大的项目，最好的算法（动态编程、贪婪、分支和定界）是什么以及它们的效率。

我很确定如果我有四个项目（具有不同的权重）和 3000 的容量，考虑到复杂性 O(nW)，动态编程可能不是最佳解决方案，但即使贪婪也没有给出最佳解决方案，那么如何大小会影响算法在这三个之间进行选择吗？

I'm studying the behavior of the branch and bound algorithm in a integer 2-variable linear problem. I occasionally use Wolfram Alpha for plotting graphs, but now I need a more robust option, Mathematica. I need to plot the viable zone of a set of inequalities on the R2 space (with x and y greater than 0), inequalities such as:

2*x+4*y <= 12 // 6*x+2*y <= 27 // x <= 4 // x>=0 // y>=0

The graph must show all integer x,y points on the positive quadrant (I think a mesh function can do this) and a specific point (solution of the max/minimization problem) For example, the viable space in this case is: http://www.wolframalpha.com/input/?i=plot%282*x%2B4*y%3C%3D12%2C6*x%2B2*y%3C%3D27%2Cx%3C%3D4%2Cx%3E%3D0%2Cy%3E%3D0%29

thanks in advance.

我正在为旅行推销员问题寻找 B&B 算法的伪代码。我发现了这个： TSP - 分支和绑定 ，但是到目前为止有人作为答案给出的链接对我没有帮助。你有任何伪代码的例子吗？

先感谢您！

我在 23:14 通过http://youtu.be/gGQ-vAmdAOI?t=23m14s工作时，我觉得带有“扩展列表”的分支和绑定与 Dijkstra 的算法非常相似。稍后在讲座中，当算法再次用可接受的启发式扩展时，我们得到 A*。

这让我想到 Dijkstra 的算法就是这个分支与界限的子类。是对的吗？

总结讲座：

探索了搜索算法。特别是，它们从一个简单的分支定界解决方案开始：

直到目标节点被访问（扩展），访问距离源节点最近的节点，并将其后继节点加入优先访问节点队列（按最小距离排序）。这还没有检测到周期（例如多次访问节点）并且由于组合爆炸而效率很低。

一个简单的扩展使算法执行得更好：记住哪些节点已经被访问过（扩展，因此扩展列表）。现在没有节点被访问两次，并且算法的性能要好得多。

在最后一部分中，将一个可接受的启发式添加到混合中以获得 A*。

我希望这是足够的信息，并且我不必复制讲座中的示例。如果不是，请告诉我，我会做的！

我有两个十进制数变量 colSum 和 rowSum，使用我想基于这些总和构建二进制值矩阵的变量，rowSum 数组变量是每行添加所有 1 的结果，colSum 数组也是如此。

所以，如果你有

您将必须正确构建以下数组

我在 PHP 中使用这种方法，它适用于 3x3 矩阵，但不适用于更大的矩阵，例如 8x8。首先，使用 rowSum 值填充行中的所有 1。然后，尝试找到 2 列的错误总和值，并在同一行中将它们（1 与 cero 值）互换，直到我得到正确的 colSum 值。但这不起作用，因为我需要对标准进行一些控制来更改同一行中两列的 1 和 0 ......

这是我正在使用的方法。

假设我们有这个矩阵（N=3 -> NxN）：

那么我们有以下数组

步骤1

在每行中使用与 R0(i) 一样多的 1 创建并填充 NxN 数组：

现在计算这个新矩阵的总和：R1 = {0,1,2} C1 = {2,1,0}

第2步

检查创建的矩阵的列总和的所有元素是否与 C0 (origin) 具有相同的值

要替换列，我们必须深入研究条件。C0(0) = 1 != C1(0) = 2 第一列总和确实满足调用替换的条件，所以

第 3 步

选择应用分支和绑定方法的标准，并找到最佳行来更改满足全局条件的列（所有列总和）。

列总和之间差异的变化量为：

对于此示例，|C0(0)-C1(0)| = 1 变化。如果更改在列的总和之间产生更大的差异，则返回条件必须是。

那么，这种方法真的可行吗？