问题标签 [integer-programming]

我有一个（可满足的）（线性）整数可满足性问题。除其他外，该问题包含一堆布尔值变量，称它们为 x ₁ ...x _n，其中一个约束是 sum(x ₁ ...x _n ) = C。我希望确定哪个这些变量中的一些是固定的，并且所述变量的固定值（如：在所有可能的解决方案中，这些变量中的哪些取特定值（0 或 1，因为它们又是布尔值））。

我有一个可行的解决方案，只是很慢（委婉地说）：

1. _{添加 x 1} == 0的约束
2. 检查问题是否可以解决
3. 删除在步骤 1 中添加的约束。
4. _{添加 x 1} == 1的约束
5. 检查问题是否可以解决
6. 移除第 4 步中添加的约束
7. 断言至少 2 和 5 之一成功。
8. 如果两者都成功，则变量不固定。否则，该变量将固定为问题仍然可以满足的任何约束。
9. _{对 x 2} ...x _n重复 1...8

这样做的问题是它很慢。特别是，它需要解决问题 O(n)，或者更确切地说是 2*n 次。（我传递了以前的解决方案来热启动求解器，但只是启动求解器几乎需要所有时间。）

有没有更快的方法？特别是，需要更少调用求解器的次数？

我正在考虑的事情，不幸的是不能按原样工作，是将它变成一个 ILP 问题并解决它两次，一次以最大化 sum(x 1 ...x n) 为目标，一次以最大化 sum(x ₁ ...x _n ) 为目标最小化相同，并检查哪些变量发生变化。不幸的是，这通常不起作用。对于（反）示例：布尔变量x和y，其中x+y=1。即使两个变量都不是固定的，最大化和最小化也可以产生相同的结果。

我有 N（例如 30）个整数V[i]和 M（例如 8）个包，每个包都有一个期望值P[j]。

我想将每个整数分配给一个包，以下表达式计算 pack 中的总和与V[k]packj的期望值之间的差j。

目标是找到最小化的最佳解决方案sum(diff[j])。

我不知道这种问题的类型是什么。这可以通过线性规划解决，还是 NP 完全问题？

我正在使用 SCIPAMPL 来解决混合整数非线性规划问题 (MINLP)。在大多数情况下，它运行良好，但我发现了一个求解器错误地检测到不可行性的实例。

求解器在预求解阶段检测到不可行性。但是，如果取消注释将 x 和 y 固定为 4 和 12 的两个约束，求解器将工作并输出正确的 v 和 z 值。

我很好奇为什么会发生这种情况，以及我是否可以用不同的方式来解决这个问题来避免它。我得到的一个建议是，对于非凸问题，不可行性检测通常不是很好。

编辑：我应该提到这不仅仅是一个 SCIP 问题。SCIP 只是解决了这个特定集合 K 的问题。例如，如果我使用另一个全局 MINLP 求解器 bonmin，我可以解决这个特定 K 的问题，但是如果你将 K 扩展到 15，那么当问题仍然可行。对于那个 K，我还没有找到一个真正有效的求解器。我还尝试过基于 FILTER 的 minlp 求解器。我还没有尝试 BARON，因为它只需要 GAMS 输入。

我有一个 MIP，我几乎可以肯定地知道解决方案。我想用 gurobi 来证明真正的解决方案（即使它不是我提供的解决方案）与我给出的解决方案的偏差不应超过 0.5%。我相信简单地保持切割而不分支可能会节省更多时间。你知道我可以简单地进行切割而不在 gurobi 中分支的方法吗？这是代码性能：

将参数 LogFile 的值更改为 Prev：gurobi.log 默认值：将参数 MIPFocus 的值更改为 3 Prev：0 最小值：0 最大值：3 默认值：0 将参数 Cuts 的值更改为 3 Prev：-1 最小值：-1 最大值：3默认值：-1 优化具有 1794 行、673 列和 4180 个非零值的模型 找到启发式解决方案：目标 -22.8549 预求解删除 18 行和 17 列预求解时间：0.01 秒预求解：1776 行、656 列、4464 个非零值

加载的 MIP 从目标 -342.641 开始

变量类型：592 连续，64 整数（64 二进制） 预求解：1776 行，656 列，4464 非零

根松弛：目标 -6.775689e+02，682 次迭代，0.02 秒

……

我正在努力为整数线性规划模型设计一个目标函数。目标是确定两个基因的拷贝数以及是否发生了基因转换事件（其中一个拷贝被另一个覆盖，看起来一个被删除但净拷贝数没有改变）。

该问题涉及两个数据向量，P_A和P_B。这些向量包含大于零的连续值，这些值对应于在每个位置进行的拷贝数的测量。P_{A,i}不一定是整个基因的同一个点P_{B,i}，因为每个拷贝的位置都是唯一的（并且可以映射到基因组中的绝对位置）。

鉴于此，我的计划是尝试最小化我的决策变量和跨不同基因组窗口的测量数据之间的差异，为我提供对应于同一区域的两个数据向量的不同切片。

决策变量：

然后，目标是最小化以下等式左右两侧的差异：

受到一些限制，例如2 <- A_w + B_w <= 4

但我不确定如何将其公式化为最小化的函数。我有两个不是真正函数的方程，决策变量没有系数。

我也不确定如何处理C_w.

我也不确定如何将结果重新组合在一起；在我解决每个窗口中的 LP 之后，我仍然需要将其合并到一个全基因调用中（并且理想地确定哪些窗口具有非零值C_w.

是否有适用于 Python 的混合整数线性规划（MILP）求解器？

GLPK python可以解决MILP问题吗？我读到它可以解决混合整数问题。
我对线性规划问题很陌生。所以我很困惑，如果混合整数规划与混合整数线性规划（MILP）不同，我无法真正区分。

我已经使用 CPLEX 可调用库（在 VS2010 中）解决了一个 lp。lp如下：

代码如下。现在我想让它成为 MIP（对 x 的附加完整性约束）。我试图通过更改status = CPXlpopt (env, lp);为status = CPXmipopt (env, lp);. 这不起作用，我得到错误3003: not a mixed-integer problem。有人知道我在这里想念什么吗？

谢谢你的时间。

我有一个线性程序，不知道如何表达一种约束形式，即使它是可能的。也许这里有人知道解决方案。

一家公司组装并销售由 3 种成分 a、b 和 c 组成的混合物，其中 a = b = c。
每种成分可以来自 2 个工厂：f1 和 f2。
每种成分的成本整天都在波动，并且每个工厂之间的成本都不同。
每个工厂以一对夫妇的形式提供每种成分的成本：（成本，可用数量）。

我想表达的约束（不影响现有的目标函数）但我不知道如何表达：
避免选择高于我的销售价格的制造成本。

例如，在时间 t，成本可能是：

我想为两个输入常量获得最佳重新分区：maximumAllowedQuantity 和 maximumAllowedCost。
但目前我只处理 maximumAllowedQuantity 并且我也想处理 maximumAllowedCost （这是我的问题的目的）。

由每个成本的金额组成的最终解决方案将在输出变量中：

例如，使用提供的示例数据，对于输入 maximumAllowedQuantity = 15（没有 maximumAllowedCost 约束，因为我不知道如何制定它，这就是我要问的），基于当前的一些目标（例如：我更喜欢以相同的总成本在工厂之间公平分配金额，而不是偏袒一家工厂），
我可以得到：

我可以在成本方面总结为：

如果我们按成本分解得到的混合物，我们得到：

这里的最高成本是 65 美元。
但是如果我的售价是 60 美元，为了避免赔钱：
如何添加约束 maximumAllowedCost = 60 美元？

注意：我们不能简单地采用先前的结果（没有 maximumAllowedCost 约束）并删除成本 > 60 美元的金额，因为如果总数量较小，我的目标函数将为成本 <= 60 的数量提供另一个重新分配：这里 9.5（15 - 0.5 - 3.0 - 2.0) 而不是之前的 15。
...

谢谢

我正在解决关于 Trees 的问题。我正在尝试编写 ILP 公式。我有一棵树 T=(V,E) V 是顶点 E 是边。我的限制之一是关于连通性，我想制定我的陈述：如果 X[i,j] =1; 然后 X[parent_i,i] = 1。X 是二进制变量，表示我们在解决方案中选择该节点，如果它在解决方案 1 中，否则为 0。i，j 是 V 的元素我如何制定这个？

提前致谢。

我在 Python 2.7.8、Windows 32 位中运行 PuLP 编程库。我使用 GLPK 作为混合整数线性规划问题的求解器。求解器收敛到大约。1% 的最优解很快，但是计算精确最优解的时间很长。有没有办法使用 PuLP 指定 GLPK 求解器的百分比容差？我搜索了https://pythonhosted.org/PuLP/solvers.html但它没有为 GLPK 求解器提供任何答案。