我试图找出最好的技术或资源来帮助我解决优化问题。问题在于将会议参与者与预定义角色进行最佳匹配。在会议之前，与会人员为每个角色决定他或她是否：

• 如果可能的话，积极寻求填补这个角色（“A”）
• 愿意担任该角色，但对此感觉不强烈（“W”）
• 不愿意担任这个角色（“U”）。

例如，一个可能的输入矩阵是：

目标是在以下限制条件下，最大限度地增加角色标记为“A”的与会者的匹配次数：

• 所有角色仅由一名与会者担任
• 禁止参加者标记为“U”的比赛

对于此示例，最佳解决方案如下，其中 4/5 角色使用“A”匹配填充。

有谁知道是否有比蛮力更好的方法来解决这类问题（对于较大的矩阵来说，这很快变得不可行）？我愿意接受我自己实现的优化算法的一般建议（即禁忌搜索、遗传算法、分支定界等），甚至是指向现有包（如OptaPlanner ）中的功能的指针。

谢谢！

有没有办法使用分支定界技术解决最长公共子序列（ LCS ）问题。我了解分支定界，但我无法应用该技术来解决 LCS。只是希望论坛意见指向正确的方向以找到解决方案。

I am kind of new to the SCIP. I want to use SCIP as a branch and price framework. I have coded the problem in C++ already and also have implemented the pricer or column generation as a function. In fact I have implemented the BP algorithm for the root node by linking Cplex.dll to the project and now need to code the branching tree and decided to use SCIP for this purpose. I want to know what is the fastest way I can solve my problem using SCIP and the old codes which I have? Or maybe using GCG is a better and faster way? I have read the GCG documentation but doesn't understand if I should implement the pricer myself again or not? In fact I don't understand the difference between these two (SCIP and GCG). Thanks.

我的代码在前几次迭代中有效，但经过几次 while 循环后，似乎我的数组元素被删除了。

我从输入参数构造的数组中取出数字，我只能说，当我得到一个传入两次的数字时，我得到一个错误。

我这样称呼我的脚本

我应该把它作为输出

这是我的脚本

这就是输出

我开始为 C++ 中的分配问题做分支定界算法，但我找不到正确的解决方案。首先是赋值问题示例： 赋值问题

好的，所以每个人都可以分配到一项工作，我们的想法是将每项工作分配给一个人，以便所有工作都以最快的方式完成。

到目前为止，这是我的代码：

我知道我可能跑题了。我一开始没有使用下限，实际上我有点困惑这个算法是如何工作的。因此，即使通过算法逐步演练也会有所帮助。

我最近对分支定界方法感到困惑。分支定界法有三种搜索策略：深度优先搜索、广度优先搜索和最佳优先搜索。所有书籍和文献都指出，广度优先和最佳优先将占用所用计算机的更多内存。这个怎么理解？以二叉树为例，当从活节点列表中取出一个节点（父节点）进行处理时，会生成两个子节点（或子节点）并插入活节点列表中，但是父节点应该被删除，因此，只有一个节点的内存增加。从这个角度来看，这三种搜索策略都占用了计算机的相同内存。我对吗？这让我困惑了很久。谁能给我一些建议？

FIFO、LIFO和LC Branch and Bound有什么区别？

使用分支定界法的 0/1 背包的以下代码显示了错误：

第 15 行：“项目”无法启动参数声明。第 15 行：) 预期。对于函数绑定也观察到相同的情况。

我已经获得了一个证据，该证据会诋毁关于 0/1 背包问题的普遍看法，我真的很难说服自己我是对的，因为我找不到任何可以支持我的主张的东西，所以我将首先陈述我的主张，然后证明它们，我将感谢任何人试图进一步证实我的主张或反驳它们。任何合作表示赞赏。

断言：

1. 用于解决背包问题的 bnb（分支定界）算法的大小与K（背包容量）无关。
2. bnb 树完整空间的大小始终为 O(NK)，其中 N 是项目数，而不是O(2^N)
3. bnb 算法在时间和空间上总是优于标准的动态规划方法。

前提假设：bnb算法容易出现无效节点（如果剩余容量小于当前item的权重，我们不打算对其进行扩展。另外，bnb算法以深度优先的方式完成。

马虎证明：

这是解决背包问题的递归公式：

值（i，k）=最大值（值（i-1，k），值（n-1，k-weight（i））+值（i）

但是如果 k < weight(i): Value(i,k) = Value(i-1,k)

现在想象这个例子：

现在这里是这个问题的动态解决方案和表格：

现在想象一下，不管这是否是一个好主意，我们只想通过记忆而不是表格使用递归公式来执行此操作，例如使用地图/字典或简单数组来存储访问的单元格。为了使用记忆化解决这个问题，我们应该解决表示的单元格：

现在这与我们使用 bnb 方法获得的树完全一样：

现在是草率的证明：

1. Memoization 和 bnb 树的节点数相同
2. 记忆节点取决于表大小
3. 表大小取决于 N 和 K
4. 因此bnb 不独立于 K
5. 记忆空间以 NK 为界，即 O(NK)
6. 因此bnb 树的完整空间（或者如果我们以广度优先的方式进行 bnb 的空间）总是 O(NK) 而不是 O(N^2) 因为整棵树不会被构建，它会是喜欢妈妈化。
7. 记忆化比标准的动态规划有更好的空间。
8. bnb 比动态规划有更好的空间（即使在广度上先做）
9. 没有松弛（并且只是消除不可行节点）的简单 bnb 将比 memoization 有更好的时间（memoization 必须在查找表中搜索，即使查找可以忽略不计，它们仍然是相同的。）
10. 如果我们忽略 memoization 的查找搜索，它比动态的要好。
11. 因此，bnb 算法在时间和空间上总是优于动态算法。

问题：

如果无论如何我的证明是正确的，就会出现一些有趣的问题：

1. 为什么要为动态规划而烦恼？根据我的经验，你可以在 dp knapsack 中做的最好的事情是拥有最后两列，如果你从下到上填充它，你可以将它进一步改进为一列，它会有 O(K) 空间但仍然不能（如果上述断言是正确的）击败 bnb 方法。
2. 如果我们将它与松弛修剪（关于时间）相结合，我们还能说 bnb 更好吗？

ps：对不起，长篇大论！

编辑：

由于其中两个答案都集中在记忆上，我只想澄清一下我根本不关注这个！我只是使用记忆作为一种技术来证明我的断言。我的主要关注点是分支定界技术与动态编程，这是另一个问题的完整示例，由 bnb + 松弛解决（来源：Coursera - 离散优化）：

所以我遇到的问题是：有一组 N 个类别的对象，每个类别中有 M 个对象，每个对象都有一个指定的值和权重。我们必须从每个类别中选择一个对象，以便权重 <= 某个给定的容量 W，并且值是最大值。该任务必须使用分支和边界方法来解决。我很难理解这种方法在这种情况下应该如何工作。你能给我解释一下吗？