问题标签 [mixed-integer-programming]

我正在尝试为以下问题找到一个整数规划公式：

根据 2 个标准对项目列表进行排序，由以下成本表示：

• '位置成本'：取决于项目在列表中的位置
• “邻居成本”：取决于列表中相邻的两个项目（即项目是直接邻居）

以下适用：

• 每个物品只能放置一次
• 列表有一个开始位置 P_1（-> 该位置的项目没有前面的列表项目）
• 列表有一个结束位置 P_X（-> 该位置的项目没有后续项目）

我使用 PuLP 进行如下所述的公式化，并尝试使用 GLPK_CMD 和 COIN_CMD 进行求解。它适用于 3 个项目，但对于 4 个或更多项目返回“未定义”。据我所知，诸如 DataFrame 'feasible_solution_example' 中描述的订单不会违反约束。谁能冒险猜测为什么求解器找不到解决方案？
非常感谢任何输入和评论。

更新： 感谢您的评论。删除约束后，现在可以使用。

我无法弄清楚如何设置 MIP 间隙阈值，以便当原始解决方案和对偶解决方案之间的相对差异在某个值内时，求解器将终止。我正在使用 PySCIPOpt 与 SCIP 进行交互。

我确信有一种简单的方法（例如，如果我使用 Gurobi 的 python 接口，它只是m.Params.MIPGap = x，m模型实例在哪里）。

任何帮助是极大的赞赏！

众所周知，精确的数学策略（如 MILP）对于灵活作业车间问题的大型实例效率不高。然而，现在仍然可以找到针对 FJS 问题的 MILP 公式的建议。这可能是因为使用 MILP 模型进行涉及非精确方法如元启发式（GA、FA、TS 等）的实验很有趣，因为它提供了下限。

我还读到，当找到可行的解决方案比最佳解决方案更重要时，应该选择 CP。这是一个真实的说法吗？

我正在使用 Julia 中的 CPLEX 求解 MIP 模型。我知道 CPLEX 有一个所谓的解池，其中存储了求解过程中的所有中间整数解。有没有办法使用 Julia (JuMP) 访问这些解决方案？

我有 Gurobi 许可证，并且我追求一种好的 MILP/LP 建模语言，应该是

1. 免费/开源

2. 直观的，即看起来像的东西（取自 MiniZinc）

   变量int：x；约束 x >= 0.5；解决最小化x；

3. 快速：构建模型并将其发送到 Gurobi 的时间应该与最佳模型（AMPL GAMS 等）的顺序相似

4. 灵活/强大（能够处理 3D+ 数组，轻松激活/停用约束，为求解器提供初始解决方案等）

当然，如果我错了，请纠正我，AMPL GAMS 在 1) 处失败，Python 和 R 在 2) 处失败（也许在 3 处）？）。

GLPK、Minizinc、ZIMPL 等怎么样？它们满足 1) 和 2) 但 3) 和 4) 呢？他们在这方面和 AMPL 一样好吗？如果没有，是否有满足 1-4 的建模语言？

我正在尝试将下面的第三个条件转换为线性约束。出于说明目的，我已经包含了完整的问题和我的进展。

一家制造商正在考虑生产三种产品 a、b、c。每种产品的材料、人工和利润如下。

产品：（投入材料数量、工时、利润）

一个：（3,6,200）

乙：（6,5,300）

c: (10,8,400)

目前，有 12,000 单位的输入材料和 12,000 小时的劳动力可用。指定了以下附加限制。

1. 如果公司决定生产“a”，那么它必须至少生产 100 个单位。

2. 如果公司决定生产“b”型汽车，那么它必须至少生产 80 辆。

3. 如果公司决定生产“c”，那么它最多可以生产总共 120 个单位的“a”和“b”（如果生产“c”，我将其解释为 a + b <= 120，并且 a + b受材料和劳动力限制，否则）。

我需要制定一个整数线性程序来最大化公司的利润，同时满足劳动力和材料的限制，以及上面列出的 3 个附加限制。

到目前为止，我已经完成了以下工作。

我指定 Xa、Xb 和 Xc 为生产的 a、b 和 c 的数量。我介绍二进制变量如下：

如果 Xa > 0，则 Ya = 1，否则为 0。

如果 Xb > 0，则 Yb = 1，否则为 0。

如果 Xc > 0，则 Yc = 1，否则为 0。

那么问题来了：

最大化 200Xa + 300Xb + 400Xc

英石

Xa >= 0, Xb >= 0, Xc >= 0

Ya 在 {0,1}，Yb 在 {0,1}，Yc 在 {0,1}

3Xa + 6Xb + 10Xc < = 12,000

6Xa + 5Xb + 8Xc < = 12,000

Xa >= 100Ya

Xb >= 80Yb

如何制定最后一个附加约束？

更新：

经过一番研究。Xa + Xb <= 120 + M(1-Yc)。其中 M 足够大，以至于 Xa + Xb 不会受到超出材料和劳动力限制的人为限制。留下这个，以防其他人可能会得到帮助。

我正在构建一个模型，该模型需要我考虑各种船只的容量，但我不确定如何在 ampl 中声明这一点。

目前，我有：

其中 I 是路线的集合，T 是船只的行程集合。x[a,i] 是指示变量，当船只 a 行驶路线 i 时，它 =1，people[a,t] 是船只 a 在行程 t 上的人数。

对于这个约束，ampl 总是抛出以下错误：

我怎样才能解决这个问题？

I have written the code for the operation of the appliances for a minimum up time in a MILP problem in MATLAB.

The code I have written is based on the lines of the "optimal operation of thermal plants" tutorial video for MILP problem.Following is the link to it -

https://in.mathworks.com/videos/mixed-integer-linear-programming-in-matlab-91541.html

Following is my code -

Although the code is generating a solution. But the solution is wrong as it is violating the appliances' duration constraint. For the first column of 'A' variable in the solution, the device is operating for 3 hours but its duration is only for 2 hours.

Any help would be very much appreciated. Thanks

我想使用 Pyomo 在 python 中开发的 MIP 问题访问对偶变量。据我了解，对偶不是为 MIP 问题创建的，但我认为应该有一个解决方法。

这应该可以用作一个最小的工作示例，我自己正在使用 Gurobi。

我可以看到两种可能的解决方案；1. 修复二进制/整数变量并解析为 LP 并重新创建对偶。2. 仅在必要的约束条件下获得对偶。

我一直无法想出尝试第二种方法的方法，首先我做了类似的事情：

如果有任何不清楚或需要更多信息，请告诉我，我们将不胜感激。

我正在尝试为用 Java 编写并由 CPLEX 解决的 MIP 找到足够好的解决方案。由于这需要太多时间，如果我能得到一个可行的解决方案，我会很高兴的。由于 CPLEX 提供启发式，是否可以输出由这些计算得出的可行解，然后停止求解器？