问题标签 [branch-and-bound]

对于 0-1 背包问题，使用分支定界剪枝代码进行广度优先搜索，
我键入代码的方式与伪代码几乎相同。
但它会发生错误。

正如我认为的那样，原因在于 v.level
所以当我从一个索引为 v.level 的数组中调用一些值时，
它会给我带来关于索引

后的错误

当我运行我的代码时，我收到了这个 IndexError：

这是我的代码示例：

编辑：单纯形数学优化算法，不要与单纯形噪声或三角测量相混淆。

我正在实现自己的线性规划求解器，我想使用 32 位浮点数来实现。我知道 Simplex 对数字的精度非常敏感，因为它执行大量计算，如果使用的精度太低，可能会出现舍入误差。但是，我仍然想使用 32 位浮点数来实现它，这样我就可以将指令设为 4 宽，也就是说，我可以使用 SIMD 一次执行 4 次计算。我知道我可以使用双打并制作 2 宽的指令，但 4 大于 2 :)

我的浮点实现遇到了问题，其中解决方案不是最理想的，或者问题被认为是不可行的。这尤其发生在混合整数线性程序中，我用分支定界法解决了这个问题。

所以我的问题是：如何尽可能防止舍入错误导致不可行、无界或次优的解决方案？

我知道我可以做的一件事是缩放输入值，使它们接近一（http://lpsolve.sourceforge.net/5.5/scaling.htm）。还有什么我可以做的吗？

我是二次规划优化问题的新手。在以下论文的等式 8 中：这里，有一个等式：

作者说这是一个'Integer Quadratic Programming (IQP)'公式。

或者，在另一个网站：here中，有以下等式被描述为“ Mixed Integer Quadratic Programming（MIQP）”公式：

从我的角度来看，上面显示的两个等式都是相似的，唯一的区别是MIQP公式中包含“1/2”。

1）我正在寻找关于IQP和之间差异的解释MIQP

2）此外，我有兴趣将二次规划应用于分配问题，因此，寻找关于应该使用哪个（即IQPvs. MIQP）以及何时使用的任何见解。

问题

我正在使用 PySCIPOpt 在 SCIP 中实现分支和价格算法。我想为pyscipopt.scip.Variable对象添加额外的属性（这是 PySCIPOpt 用来处理模型变量的类），以便存储关于变量的额外信息。

但是，以经典的 Python 方式向对象添加属性，这样做会给我一个AttributeError.

我的怀疑 - 在没有真正理解发生了什么的情况下 - 虽然这可以通过“经典”python 类实现，但Variable对象是由 PySCIPOpt 的底层 Cython 代码创建的，因此不支持动态添加属性。

对于我的 Branch 和 Price 代码的列生成部分，我需要以某种方式存储，每当 Pricer 创建一个新变量时，我的变量代表什么类型的解决方案组件（例如，对于切割库存实现，这将是切割模式变量对应）。我相信通过添加一个属性来存储关于变量的额外信息——如果它有效的话——是实现这一点的最优雅的方式。

这是一个MWE：

返回

而不是添加一个名为foo.

问题

• 有没有办法为变量动态添加属性？
• 是否有不同/更好的方式来存储有关变量的信息，以便可以在我的整个 SCIP 例程中访问它（例如，它也应该可以被 Pricers 和 Branchrules 访问）？

基本上，我想重新创建 Khalil 等人的论文“Learning to Branch in Mixed Integer Programming”中的概念结果，同时尽可能避免：

1）获得CPLEX（在论文中使用）或类似的严重商业求解器的学术许可证的必要性

2）使用基于C的API的必要性。这不是一个严格的要求，但 Python 具有良好且易于访问的 ML 库的好处，这对于这个特定目标来说似乎是一个很大的优势

我知道，有大量基于 Python 的开源 MILP 求解器，但其中很多都专注于在他们的演示中相对简单问题的端到端解决方案，如果我们也考虑到，很多它们（如果不是全部）连接到其他基于 C 的求解器，很难判断哪些实际上需要定制潜力。

因此，如果有人在尝试定制 Python 求解器以满足其高度特定的需求方面有更深入的经验，我将不胜感激。

我正在尝试使用 python 来调整模型，并尝试通过停用和激活 B&C 的一些启发式方法来改进它。为此，我正在寻求有关如何管理剪切启发式参数以及我在 Gurobi 中有哪些类型的帮助。

我正在尝试解决来自生物学领域的一个问题，在这个问题中，我必须结合每个大元素的局部次优解决方案，以便每个子粒子都是独一无二的。问题是可能性可以扩展到 +4.000 局部次优解决方案和 +30.000 元素。笛卡尔积不是一个选项，因为组合列表是一个n*m*p*......问题，如果没有超越itertools.

一般架构是：

[ [a,b,c],[d,e,a],[f],.....],-> 一组 elem 的次优解决方案。#1

我想尽快找到

• 第一：一个解决方案，这意味着每个元素的一个次优解决方案的组合（可能包括空白列表），这样就没有重复项。例如 [[a,b,c],[f,e,t][p]]。

• 第二：所有兼容的解决方案。

我知道这是一个悬而未决的问题，但是我需要一些指导或一般算法来解决这个问题，如果我有什么要开始的，我可以进一步调查。

我在其余的实验室工作中使用 python，但是我对其他语言持开放态度。

我们可以从一个基本的求解器开始，该求解器在总的次优和列表数量方面处理较少的可能性。

最好的。

编辑 1

一个非常简短的真实示例：

最佳解决方案（来自第 # 行）：

可以看这里https://pastebin.com/qq4k2FdW

三元语言的所有单词仅包含 3 个字母：a、b 和 c，并且都具有严格指定的长度 N。在一行中不包含两个相同字母子序列的单词被认为是正确的。例如，abcacb 是正确的词，而 ababc 不是正确的词，因为 ab 子序列到那里。

我试图通过完整枚举所有可能的组合和一个寻找重复序列的函数来解决这个问题。然而，事实证明这是一个错误的决定。需要使用分支定界方法以某种方式解决问题。我完全不知道如何通过这种方法解决这个问题。如果有人向我提供示例或解释，我会非常高兴。我已经花了六天时间来解决这个问题，而且很累。

我的错误解决方案：

示例：abca 是正确的词。abab 是错误的 (ab)。aaaa 也是错误的 (a)。abcabc 也不正确 (abc)。

链接中问题的简短版本-> https://codereview.stackexchange.com/q/227081/207512

这是该问题的简短代码片段

在 python 中使用 Branch and Bound为 0/1 背包编码时，我使用队列模块中的队列来存储所有节点....

检查队列不为空的代码片段，然后根据代码获取值并将其推送到队列中。

在这里，q = queue.Queue()用一个空节点u(-1,0,0, 0)初始化。u2 是一个空节点，开始在每次循环迭代中存储节点。

display_queue定义为：

问题：

如果 q 最初包含 [(0,0,35)]。添加(1,3,70)后，队列变为[(1,3,70),(1,3,70)]。注意：这些是随机值。请不要与输出中的数据混淆。

输出样本：假设由于某种原因队列正在增加，经过适当的计算。

我已经阅读了堆栈溢出中相关问题的答案，例如：为什么将新值添加到 list<> 会覆盖 list<> 中的先前值但无法实施建议的更正。

当我尝试实现代码的微型版本时，一切都正确。也就是说，相同的东西（几乎）但不同的输出！