问题标签 [integer-programming]

简而言之，我们现在正在尝试将 IQP 更改为 ILP。旧的实现大约需要 2 天才能完成，现在使用线性工具——它应该会加快速度。基本上问题是最大化（大约 50 个二进制变量）：

$$\sum_{g=1}^{5}sum_{p=1}^{10} ( S[p]x[g][p]-疲倦[g][p]-睡眠[g][p ])$$

更新

我认为 David 走在正确的轨道上，但是当我尝试使用奖励变量最大化表达式时，它们每次都为零，为什么？在一些代码下面，分数可能像S[1..10]=[1,2,3,4,5,6,7,8,9,10];.

我正在用 C++ 编写代码并调用 CPLEX 来解决它。它可以快速找到一个非常好的解决方案，但需要很长时间才能尝试改进它。所以我想将间隙设置为更大的值来终止代码，这就是我使用的：

但是编译器给了我一个错误，说EpGap是一个未声明的标识符。相对间隙的默认名称是什么？

我找不到在 CPLEX java API 中有效使用 MIP 启动的方法。

我有一个线性问题，我需要通过仅更改一个约束或更改目标来解决多次，因此我认为从解决方案开始（使用 MIP 启动）可能是加快计算速度的好方法。

因此，为了做到这一点，在我第一次解决问题后，我将所有变量保存在一个 IloNumVar 数组中，并使用 cplex.addMIPStart 将其加倍传递给我的其他 cplex 对象。

问题是它并没有加快任何速度，而是让它变慢并给我这个消息：

警告：从 1 个 MIP 开始没有找到解决方案。

所以也许我不应该给 MIP 启动所有变量，但我怎么知道要给它什么变量？

我也试图改变 MIP 启动努力，但它似乎没有任何区别......

为什么它不能使计算更快？有没有更好的方法来解决只有一些差异的许多问题？

我正在尝试解决整数规划问题。我已经尝试过使用SCIP和LPSolve

例如，给定 A 和 B 的最终值，我想在以下 C# 代码中求解 valA：

我以 lp 格式将其实现为这个整数程序（截断除法会导致一些并发症）：

然后试图解决它：

但是，我知道有一个可行的解决方案，因为我知道一个有效的变量赋值。添加以下条件会导致找到解决方案：

两个不同的求解器声称这个可行的问题是不可行的。我是否违反了一些不成文的条件？这是怎么回事？有没有真正解决问题的解决方案？

优化工具箱中的bintprog命令解决了具有不等式约束和可选等式约束的 0-1 编程问题：Ax <= b 其中 A 是矩阵和 ba 列向量。

我有一个 |Ax| 形式的问题 <= b，或等效地，-b <= Ax <= b。有没有办法用Matlab解决这类问题？

我正在尝试在 MIP 中对以下约束进行建模：

这个想法是引入一个变量 z 是 1，如果 x_1 +x_2 + ... +x_n = d 并添加约束

但我不知道如何为约束建模

在整数程序中。

我一直在尝试使用 CPLEX Java 实现 ILP，并且长期以来一直被困在一个问题上。以下是 ILP 的几个变量：

numRect 的值为 1。在程序结束时，我输出这些值：

这是我得到的输出：

我不明白为什么我得到双值而不是布尔值。任何帮助，将不胜感激。谢谢。

我正在玩 GLPK 提供的旅行推销员示例，并试图了解我可以合理期望解决的问题规模。我已经设法解决了一个 50 个节点的图，但是 100 个节点似乎并没有在合理的时间范围内收敛（现代硬件上 30 分钟左右）。

GLPK 有很多 MIP 求解器的选项。我尝试了各种组合，但我完全不清楚哪些选项可能会有所帮助。此页面有一些讨论，但有些过时，建议相当笼统。

期望 GLPK 在实际时间范围内（例如，少于 4 小时）解决 100 个或更多节点的旅行是否合理？问题规模何时变得棘手？许多命令行选项中的任何一个都可能有帮助吗？

假设我们想从$A$ 走到$B$，但是它们之间有几条河流。为了从$A$ 走到$B$，我们需要为每条河流建造一座桥。

我们有几种类型的木板。不同类型的木板成本和长度不同，但相同类型的木板成本和长度相同。我们可以用木板搭桥。但是，可用木板的数量是有限的。我们的目标是为每条河流建造一座桥梁，同时最大限度地降低木板的总成本。

为了更好地描述问题，我们画了一个图来描述我们的问题。

有 3 条河流需要的桥梁长度分别为 $d_1$、$d_2$ 和 $d_3$。

我们有 4 美元的木板。令 $l_i$ 和 $c_i$ 表示第 $i$ 种木板的长度和成本。令$\delta_i$ 表示第$i$ 种木板的可用数量。令 $n_{ij}$ 表示用于建造桥梁 $j$ 的木板数量。

那么问题可以表述如下：

最小化 $\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$

英石

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

我认为这个问题应该是 NP-Hard，因为它是一个整数规划问题。这是真的？有谁知道如何解决这个问题？即使是不是最优的解决方案。

我试图了解 CPLEX 中指标约束的使用。我已指定要在 CPLEX Interactive Optimizer 中解决的简单整数规划问题。由于各种原因，我无法使用任何 CPLEX API 来完成此任务。

真正的问题是一个简单的最大覆盖集问题，但有大量变量。有许多类型的 THING，它们可以在一个或多个 BOXES 中找到。我想在我的解决方案中最大化 THING 类型的数量，同时将 BOXES 的数量保持在一个约束之下。所有变量都是二进制文件。

真正的问题显然要大得多。我在这里制作了一个简单的版本，限制为 3 BOXES。

我的第一个问题是：这种仅使用指标约束的问题表述是否有效？在我的真实示例中，它可以愉快地与 CPLEX 一起运行，我还没有发现它会产生意想不到的解决方案。回答这个问题是以下问题的先决条件。

我的第二个问题是：我想引入一个约束，我只想要对 THING1 进行两次采样的解决方案。我替换了指标约束

和

在我真正的问题中，这个约束的 RHS 似乎被忽略了。CPLEX 毫无怨言地读取和优化，返回的解决方案将 THING1 的值设为 1，但（例如）将具有 BOX1 = 1、BOX4 = 0、BOX5 = 0。

这让我担心要么我完全错过了在 LP 格式程序中使用指标约束的要点，要么是处理指标约束的优先级导致了这个问题。

我想到的另一件事是 CPLEX 的预求解例程可能会在某处删除约束，但我认为在深入研究预求解输出之前我会检查明显的情况。