问题标签 [integer-programming]

使用 java 和 OptimJ 插件，我正在编写一个 Cplex 模型并使用许多测试用例对其进行测试。但是当我执行它时，有些情况需要很长时间才能完成，这是不实用的。我想知道是否有办法在 java 中设置 Cplex 返回解决方案的最长时间，其中它可能不是最优的。

下面是我的代码。有什么建议么？

下面是我的 PeakDemand 课程，

我的二进制编程问题是：

受制于：

这是一个流程任务分配问题。就我而言，解决二进制/整数编程问题的开销需要非常小（< 1 毫秒）。当我使用 CBC 求解器/lpsolve 运行它时，它报告的时间为 2 毫秒 - 7 毫秒。我没有 SCIP/Gurobi。有没有办法在不到一毫秒的时间内解决这个问题？期望在不到一毫秒的时间内解决这个问题似乎是合理的吗？

（我确实禁用了 CBC 中的 printf。但我不确定它是否有任何其他系统操作被卡住......它正在写入的任何日志文件）

我正在使用 gurobi-python 界面。无论如何将连续变量转换为二进制变量。我只是不想转换

至

我必须以另一种方式来做，而不是使用

感谢您的可能反馈。

谢谢你。

我有一个优化问题，它在目标函数中包含 2 个乘法变量，使模型成为二次方。

我目前正在使用 zimpl 来解析模型，并使用 glpk 来解决它。由于它们不支持二次规划，我需要将其转换为 MILP。

. 第一个变量是实数，在 [0, 1] 范围内，第二个变量是实数，范围从 0 到 inf。这个可以毫无问题地是整数。

目标函数中的关键部分如下所示：

我在约束中遇到了类似的问题，但它们很容易解决。

我该如何解决目标函数中的这种问题？

这个问题出现在一个挑战中，但由于它现在已经关闭，所以应该可以询问它。

问题（不是这个问题本身，这只是背景信息）可以这样直观地描述，借用自己的形象：

我选择以最佳方式解决它。这可能（对于决策变体）是一个 NP 完全问题（它肯定在 NP 中，而且它闻起来像一个精确覆盖，尽管我还没有证明可以将一般精确覆盖问题简化为它），但这很好，它只需要在实践中快速，不一定在最坏的情况下。在这个问题的上下文中，我对任何近似算法都不感兴趣，除非它们提供削减。

有一个明显的 ILP 模型：生成所有可能的方格（如果方格仅覆盖存在的网格单元格，则方格是可能的），x_i为每个方格引入一个二进制变量，指示我们是否使用它，然后

约束 3 表示每个单元只被覆盖一次。约束 1 和 2 使 x_i 二进制。最小解给出了原始问题的最优解。

这个（即忽略约束 1）的线性松弛是半体面的，但它会做这样的事情（这是一个 6x6 网格，左上角缺失）：

这里选择了 13 个正方形的“一半”（客观值为 6.5），大小（这样你可以更容易地找到它们）

• 1 的 4x4
• 3 的 3 x 3
• 6 个 2x2
• 3 个 1x1

此实例的最佳解决方案的目标值为 8，例如：

线性放松是半体面的，但我并不完全满意。差距有时超过 10%，这有时会导致整数阶段非常缓慢。

这就是实际问题出现的地方，是否有额外的约束可以添加（懒惰地）作为削减，以改进分数解决方案？

我已经尝试了问题的替代公式来找到切割，例如，而不是选择正方形，如果我们选择“左上角”和“右下角”，然后将它们匹配以形成不重叠的正方形覆盖所有细胞？然后在每个“类似反斜杠的对角线”上，必须有匹配数量的左上角和右下角。但这无济于事，因为如果我们选择正方形，那么无论如何该条件总是正确的，在分数解决方案中也是如此。

我还尝试了一些关于重叠的推理，例如，如果两个正方形明显重叠，它们的总和不能大于 1，并且可以通过添加完全包含在重叠区域中的所有正方形来改进。但该约束不如所有单元格仅被覆盖一次的约束强大。

我尝试过对总面积进行推理（例如，总覆盖面积必须等于单元格的数量），但这已经通过每个单元格必须被覆盖一次的约束来保证，并根据总面积来说明只允许更多的自由。

我也尝试过用平方数（每个平方的面积是，嗯，一个平方）和平方数的差异做一些事情，但这也没有任何有用的结果。

我已经使用 GLPK 在八度音程中解决了线性规划问题，我相应地构造了 C、A、b、lb、ub。我的问题是最小化问题。所以对于ctype我使用的价值L和vartype价值是C。

现在我想解决整数规划问题。如果我只是更改vartypetoI并保持其他参数不变，那么我会得到积分结果吗？任何帮助将不胜感激。

我想用以下目标函数求解一个混合整数线性程序：

J = 最大化 (f1(x) + f2(x)) 受约束：成本(x) <= 阈值

其中 x 是选定变量的集合，f1 和 f2 是两个评分函数，成本是成本函数。

f2 是基于所选变量之间相似性的函数。我不知道如何在纸浆中制定此功能。

这是我的最小工作示例，其中函数 f2 是两种成分之间的相似性，如果已经在选定的变量中，我想添加similarity[i][j]到目标函数j中，但不知道该怎么做。

此代码基本上只考虑静态成本（以成本变量编码）。如何动态添加作为similarity变量的相似性成本？

考虑一个固定的 m × n 矩阵 M，其所有元素为 0 或 1。问题是是否存在一个非零向量 v，其所有元素为 -1、0 或 1，其中 Mv = 0。例如，

在这个例子中，没有这样的向量 v。

在此示例中，向量 (0,0,0,1) 给出 M_2v = 0。

我目前正在通过尝试所有不同的向量 v 来解决这个问题。

但是，是否可以将问题表示为整数规划问题或约束规划问题，以便我可以使用现有的软件包，例如 SCIP，这可能更有效。

考虑 m × n 个矩阵 M，其所有条目都是 0 或 1。对于给定的 M，问题是是否存在一个非零向量 v，其所有条目都是 -1、0 或 1，其中 Mv = 0。例如，

在这个例子中，没有这样的向量 v。

在此示例中，向量 (0,0,0,1) 给出 M_2v = 0。

给定一个 m 和 n，我想知道是否存在这样的 M 使得不存在非零 v 使得 Mv = 0。

如果m = 3然后n = 4答案是肯定的，我们可以在上面看到。

我目前正在通过尝试所有不同的 M 和 v 来解决这个问题，这非常昂贵。

但是，是否可以将问题表示为整数规划问题或约束规划问题，以便我可以使用现有的软件包，例如 SCIP，这可能更有效。

我想逐步解决线性规划问题，添加新约束并使用对偶单纯形法将其求解至最优。虽然它是在求解器内部完成的，但我无法在 GLPK、Clp 或 LPsolve 的 API 中找到它。

我正在解决一个带有矩形包装约束的 NP 完全问题。我使用具有线性松弛的自定义分支定界算法。混合整数编程是毫无疑问的：它添加了太多的变量 (n^2)，不够紧凑，并且通常会做出错误的分支决策。我通过对添加的约束而不是布尔变量进行分支来解决问题。

我目前有一个手写求解器，它只处理有限的 LP 子集，并且想加强放松：我想使用一个真正的（开放的）LP 求解器。例如，GLPK 允许惰性约束，但似乎不允许分支，为每个问题添加不同的约束并在不破坏之前的基分解的情况下解决它们。

您将如何使用这些求解器中的任何一个正确地做到这一点？

谢谢

编辑 - 背景：

我解决了硬运行时限制的问题，其中包括矩形包装约束。对于任何一对矩形，有四个析取约束，即 R2 的上/下/右/左 R1。
使用布尔变量（使用 big-M）对其进行建模，速度太慢（错误的分支选择 + 即使使用自定义分支也放慢速度较慢 + 可行解决方案之间存在大量冗余）：我需要直接在析取约束上分支，这很好，但是我现在需要使用通用 LP 求解器，而不是我的自定义流求解器。

即在我想要的回调中

1. 生成新节点而不在整数变量上分支
2. 每个节点都有不同的新约束