问题标签 [integer-programming]

我正在解决 Gurobi 6.0 中的大型 MIP。我的顾问想为这个问题设定一个 12 小时的时间限制。我发现我可以设置 TimeLimit 参数，这将在分配的时间后杀死求解器，但我不知道当时如何检索最佳可行解决方案，只是目标值和最优性差距。有没有办法获得最佳可行的解决方案？

我使用 matlab GA 工具箱来解决整数规划问题。问题有一些二进制变量。我对二进制变量使用非线性约束x*(1-x) = 0，但 matlab 会为这些变量输出实数值。

另一个问题是最终解决方案不可行！我使用了这行代码：

但是matlab仍然没有产生可行的解决方案。

一位朋友建议使用不等式约束而不是等式约束，但失败了。

然后有两个问题。1）说关于二进制变量的matlab，2）生成可行的解决方案。

如何使用 matlab GA 解决我的问题？

我正在尝试解决数学优化模型。我想在我的模型中定义一个集合，比如说，我希望它是从 0 到 15。这可能吗？或者我必须定义从 1 到 16？我正在使用网站上提供的 GAMS（通用代数建模系统）演示版。

谢谢

PS：请有足够声誉的人创建一个GAMS标签！

我想使用 0-1 整数规划求解器作为 java 程序中的工具。我在网上找不到任何易于使用的东西。我尝试了 sat4j 的伪布尔库，但这没有很好的记录，有些类与 API 中的描述不一致（有些方法签名不同）。

你有什么建议吗？

我对（混合）整数编程比较陌生，并且被约束的公式所困扰。

在我的简化模型中，我有一个参数和两个变量，它们是正实数，其值为 321 作为上限。我想表达的逻辑在这里：

实际上是否可以使用线性（等式）来描述这一点？

如果有帮助：对于实现，我使用 Python、Pyomo 和最新的 gurobi 求解器。

谢谢你的帮助！

我有一个二进制整数编程问题，想用bintprog.

bintprog给我的解决方案是x={3}，但我希望解决方案x={1,2}是如果 1 和 2（连接到 3）都被选中，则意味着 4 是可达的。我该怎么做才能得到我想要的结果？

编辑：节点 3 就像一个开关，只有在连接到它的至少 2 个节点处于活动状态时才能启用。发生这种情况时，可以到达最后一个节点。例如，如果 1,2 处于活动状态，则可以达到 4。也可以这样说，如果 1,4 处于活动状态，则可以达到 2。3显然不应该是解决方案。

我对整数编程相对较新，并且（再次）陷入了约束的制定。

在我的简化模型中，我有一个（连续）变量，其下限 LB 低于零，上限 UB 高于零。现在我想根据变量所取的值将变量值分配给其他变量。

我想表达的逻辑如下：

我如何使用线性（不）等式来描述这一点？

估计吸收有点慢。。

提前致谢！

** 编辑：对于建模，我使用 Python、Pyomo 和最新的 Gurobi 求解器。

*** 编辑：我现在通过使用二进制变量以下列方式制定它。（我知道它是二次的，但以后可以线性化）：

但是现在我仍然必须确保如果 Variable2 > 0 则 Variable3 为 0，反之亦然。

有任何想法吗？

编写模式匹配游戏。

我们有 135 个符号。在这 135 个符号中，使用了 108 个符号的子集。从 108 个子集中，随机选择 18、21 或 24 个符号。为简单起见，让我们坚持使用 18。

选择符号后，将无法再次使用。

一次使用 27 个符号组，我们需要生成最少 27 个组，确保当从 108 个子集中随机选择 18 个符号时，我们保证其中 1 个将匹配至少 12 个其他符号来自 27 个组中至少 1 个的 18 个随机数的符号。

问题是，生成 27 组以确保满足符号匹配要求的编程逻辑（我们使用 C#）是什么？

如果我们不关心必须匹配的东西，那将是一个直接的组合/因子计算。

例如，沿线： (135 * 134 * 133 * ... * 27) / (27 * 26 * ... * 1)

但我完全不知道满足匹配要求的最佳方法。

伪逻辑和/或示例代码将不胜感激！

编辑：按要求尝试此示例。希望它可以解决问题。我将使用数字，因为尝试上传 135 个图像符号是不切实际的。

因此，假设我们的 135 个符号是数字 1-135（包括 1-135）。在这 135 个数字中，选择了 108 个子集。为简单起见，让我们使用数字 1-108。

从子集 1-108 中挑选 18 个随机数：让我们使用 1-18 （含）代替符号。

我们需要找出 27 个符号的最小组数（本例中的数字），以便至少一组 27 个（从我们所有的 27 个组中）将具有 18 个随机数中的至少 12 个（符号）。

也就是说，一组可能看起来像：1,2,3,5,6,7,77,9,10,13,15,30,40,50,60,70,56,43,100,4,103,99, 66,8,78,44,55，因为它匹配 18 个随机符号（数字）中的 12 个。

请注意，在选择 27 个组之后选择 18 个随机符号。根据需要可以有任意多的 27 组。

鉴于 MIP 求解器即将选择要分支的变量的节点，我想建议一小部分变量可供选择，但与求解器的启发式方法有很大的关系。我有充分的理由相信这可以显着减少解决整数规划问题所需的时间。我更喜欢 Gurobi（Python API），但如果有必要，我愿意切换到另一个求解器（SCIP、CPLEX）。

问题：

1. 我无法弄清楚哪个Gurobi 回调代码告诉我求解器即将分支。 至于CPLEX，我找到了BranchCallback一个详细的例子；相应的 SCIP 文档是：如何添加分支规则。

2. 考虑到节点松弛的解，我想向求解器建议的变量子集是动态计算的。换句话说，分支优先级会因节点而异，具体取决于松弛问题的解决方案。我不清楚是否允许在回调中重置分支优先级并按预期工作。Gurobi 的文档BranchPriority没有说，在问题 #1 没有解决之前，我不能自己“逆向工程”它。

3. 如有必要，我也可以自己打破束缚，编写自己的完整分支规则，而不仅仅是建议变量的子集；然而，这在 5 年前在 Gurobi 是不可能的，并且doc ofCallback建议情况仍然相同。由于实现我自己的分支规则似乎比更改我的代码以使用 SCIP 或 CPLEX 更容易，因此我将给出Google Groups 帖子中提到的“通过回调的自定义分数削减” 。不幸的是，我不清楚如何做到这一点。如果这有帮助：我所有的系数都是整数，我所有的变量都是二进制变量。

我正在尝试解决一个相当常见的 MIP。以下是问题特征。

1. 多产品、多站点（站点同时用作生产、需求和库存存储位置）。每周时间段
2. 产品（单位：箱）只能以离散的批量生产，每周在每个站点使用有限数量的班次/批次。
3. 允许跨站点运输以满足任何站点的需求
4. 此外，必须满足每个地点的最低周末库存水平。

求解器（gurobi）的当前解决方案从未达到最佳界限的 15% 以上的 MIP 差距。

如果这个问题没有固定的批量大小（可以在一个班次期间生产任何数量），这很简单。但如果没有，有人可以提出简单的启发式技术来解决这种 MIP 吗？