标签: mixed-integer-programming

是否有可能找到最接近混合整数问题的解决方案？例如,我想要下面的简化问题:

f = [1;1;1];
intcon = 1:3;

Aeq = [0.99,0.97,0.15];
beq = 0.16;
lb = zeros(3,1);
ub = [1;1;1]; 

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub)

返回,x=[0;0;1]因为这是目标值的最接近的整数解0.16.相反,它现在返回

Intlinprog因为没有任何一点满足约束而停止了.

不一定要跑intlinprog.beq例如,如果低,理想情况下也需要工作0.14.

我有一个混合整数规划问题.我可以使用JuMP找到最佳解决方案.但我怎样才能找到第二个最佳解决方案？或者第三好等

这可能是另一个同样最优的解决方案,或者它可能是更糟糕的解决方案,或者可能是:Infeasible- 可能没有大多数解决方案.

我知道对于类似TSP的问题,我可以通过逐步删除最佳路径上的链接来找到其他解决方案(即将某些城市之间的距离设置为无限).对于调度类型问题,我可以类似地逐步设置禁止在最佳路径中使用的时隙的可用性.

但有没有一种通用的方法来做到这一点,而没有编写自己的问题特定的方法来禁止这个解决方案？

约束编程(CP)和线性规划(LP)或混合整数规划(MIP)之间有什么区别？我知道什么是LP和MIP,但不明白与CP的区别 - 或者CP与MIP和LP相同？我对此很困惑......

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

1. 免费/开源

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

   无功整数：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 的建模语言？

我想使用我自己的遗传算法 (GA) 来解决混合整数问题：

https://mintoc.de/index.php/Batch_reactor

我可以在 GEKKO 中加入我的求解方法吗？

就像是...

m = GEKKO()
.
.
.

m.options.SOLVER = 'my_GA'

我想知道是否有人能够建议一些软件包来解决非线性优化问题，该问题可以为最佳解决方案提供整数变量？问题是最小化具有等式约束的函数，该函数受一些下边界和上边界约束。

我在 R 中使用了 'nloptr' 包来解决非线性优化问题，该问题效果很好，但现在想扩展该方法以将某些变量作为整数。从我到目前为止对 nloptr 的使用和理解来看，它只能返回连续变量，而不是整数变量以获得最佳解决方案。

我相信这类问题需要使用混合整数非线性规划来解决。

nloptr 形式的问题的一个示例：

min f(x) (x-y)^2/y + (p-q)^2/q
so that (x-y)^2/y + (p-q)^2/q = 10.2

where 
x and p are positive integers not equal to 0 
and 
y and q may or may not be positive integers not equal to 0

R 中的 nloptr 代码如下所示

library('nloptr')

x1 <- c(50,25,20,15)

fn <- function(x) {
  (((x[1] - x[2])^2)/x[2]) + (((x[3] - x[4])^2)/x[4])
  }

heq <- function(x) {
  fn(x)-10.2
}

lower_limit <- c(0,0,0,0)
upper_limit <- …

我会尽量让我的问题简短明了。如果您需要任何进一步的信息，请告诉我。

我有一个 MIP，用 Python 包 PuLP 实现。（大约 100 个变量和约束）问题的数学表述来自一篇研究论文。本文还包括一项数值研究。然而，我的结果与作者的结果不同。

我的问题变量叫做prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

prob.solve() LpStatus我通过退货解决问题Optimal

当我添加一些最佳（论文）结果作为约束时，我得到了稍微更好的客观值。将目标函数限制为稍低的值也是如此。LpStatus 保持不变Optimal。

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

我的假设是 PuLP 的求解器近似解。计算速度很快，但显然不太准确。有没有办法可以提高 PuLP 所使用的求解器的精度？我正在寻找类似的内容：prob.solve(accuracy=100%).我查看了文档，但不知道该怎么做。有什么想法可能是什么问题吗？

任何帮助表示赞赏。谢谢。

我有一个混合整数编程问题（通过列生成削减库存），我已经在 AMPL 中解决了这个问题，并且我使用 cvxopt 移植到了 Python。CVXOPT“op”没有提供我需要的二进制变量选项，所以我用 GLPK 扩展它以使用“ILP”。我得到 ilp status =“LP 松弛是原始不可行的”，我知道这是不正确的，因为之前的 AMPL 解决方案。所以我知道我的配置不正确。我试图通过玩弄stackoverflow问题中的示例来理解整数“I”和二进制“B”键的使用CVXOPT中的整数线性规划（ILP）函数返回非整数。

我的问题是，I&B 键之间有什么区别，例如：

stat, sol1 = glpk.ilp(W, G.T, h, I=set([0, 1]))
stat, sol2 = glpk.ilp(W, G.T, h, I={0,1})
stat, sol3 = glpk.ilp(W, G.T, h)

有以下 3 种不同的解决方案：( print(soli.T)

1. [ 0.00e+00 0.00e+00 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

2. [ 0.00e+00 0.00e+00 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

3. [ 5.00e-01 5.00e-01 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

我看过help(ilp)，但它只是说 I&B 是整数和二进制变量的索引集，（我理解），但它没有描述如果您同时使用 (I&B) 或它们重叠会发生什么，或者一个或另一个是空集，或未定义。我会认为sol1= …

我正在一个项目中，我需要根据百分比值数组细分整数值。我的最终数组必须包含整数值，并且数组的总和必须等于初始整数。

下面是一个伪造的例子。我们列出了带有某些“潜力”的汽车，我们需要将此潜力分配给特定的邮政编码。邮政编码分配由一些售罄信息决定。

SELLOUTS_PER_P_CODE规定要分配给每个邮政编码的权重。例如，对于第一个轿厢（car 1），存在很多的重量为p_code_3和少p_code_2，甚至更少用于p_code_1这样的分配应该分别为轿厢1 p_code_1=1，p_code_2=2，p_code_3=4。

贝娄是问题的数学形式。

在这里，我正在使用pyomo来实现此公式，但是不会产生预期的结果。该模型未考虑来自SELLOUTS_PER_P_CODE

from pyomo.environ import *
from pprint import pprint


def distribute(total, weights):
    scale = float(sum(weights.values())) / total
    return {k: v / scale for k, v in weights.items()}


Cars = ["car 1", "car 2", "car 3"]
Locations = ["p_code_1", "p_code_2", "p_code_3"]
POTENTIALS = {"car 1": 7, "car 2": 2, "car 3": 14}
SELLOUTS = {"p_code_1": 0.2, "p_code_2": 0.3, "p_code_3": 0.5} …

我希望拥有所有可行（次优）向量，而不仅仅是 mip 的最佳解决方案向量。
\n我在这里发现了一些老问题，但我不确定它们是如何工作的。

首先，是否有任何新的库工具/方法可以自动执行此操作？
\n我尝试了这个，但是什么也没做：

if termination_status(m) == MOI.FEASIBLE_POINT\n    println(x)\nend\noptimize!(m);\n

如果没有，最简单的方法是什么？
\n我想到扫描最优解，直到找到第一个非零决策变量，然后将该变量约束为零并再次求解模型。

for i in 1:active_variables\n    if value.(z[i])==1\n        @constraint(m, x[i] == 0)\n        break\n    end\nend\n\noptimize!(m);\n

但我用这个方法看到了这个问题**：

\n
1. \xce\x99f 我将 x[i] 约束为零，在下一步中我可能希望再次删除此约束？这取决于是否可以存在两种（或更多）不同的解决方案，其中x[i]==1
\n