问题标签 [mixed-integer-programming]

我有一组向量（曲线），我想匹配一条曲线。问题不仅在于找到与单条曲线最接近的曲线集的线性组合（这可以通过最小二乘 Ax = B 来完成）。我需要能够添加约束，例如将拟合中使用的曲线数量限制为特定数量，或者曲线彼此相邻。这些约束可以在混合整数线性规划优化中找到。

我开始使用 lsqlin，它允许约束并且能够将变量限制为 > 0.0，但在添加更多约束方面我不知所措。有没有办法将整数约束添加到最小二乘，或者有没有办法用 MILP 解决这个问题？

非常感谢您在正确方向上的任何帮助！

编辑：根据 ErwinKalvelagen 的建议，我正在尝试使用 CPLEX 及其二次求解器，但是直到现在我还没有设法让它工作。我创建了一个最小的“不工作”示例，并在此处上传了数据并在下面上传了代码。问题是 matlabs LS 求解器lsqlin能够求解，但是 CPLEXcplexlsqnonneglin返回CPLEX 错误 5002：对于同一问题，%s 不是凸的。

我正在使用 Gurobi Python 界面gurobipy。我有一个包含很多变量的模型公式。我想将应该是二进制的不太重要的变量初始化为连续变量，并在需要时将它们更改为二进制。但是，这种情况不会经常发生。

我已经尝试了类似问题的答案的解决方案，但这需要重建模型。在回调例程中重建模型GRB.Callback.MIPSOL会导致崩溃。

这可能吗？还是我应该将所有变量都作为二进制引入，并在 中处理这些情况GRB.Callback.MIPNODE？

我正在使用 neos bonmin 求解器来找到高度约束的混合整数非线性问题的全局最小解。以下是相同模型的结果，除了成本目标函数中的系数对于找到最佳解决方案的结果较小。

有人可以举例说明为什么会发生这种情况吗？

是否有任何 Ipopt 或 Bonmin 选项可以让求解器通过具有较高成本系数的模型的第一个不可行的解决方案？

我已经在这里完成了两个求解器选项

邦民期权

https://projects.coin-or.org/Bonmin/browser/stable/1.8/Bonmin/doc/BONMIN_UsersManual.pdf?format=raw

Ipopt 选项

https://www.coin-or.org/Ipopt/documentation/node40.html

在这个例子中，客观成本系数更高，我得到了一个最终不可行的解决方案

在这个结果中，客观成本系数较低，我得到了一个最佳解决方案

这是我的模型中的成本目标函数和成本约束。我无法分享我的整个模型，因为它有几千行。

这里以“DRipSet”开头的变量是二元决策

我有这个优化问题，我试图根据列 X 的唯一值最大化列 z，但也在一个约束范围内，即 X 选择的每个唯一值加起来的 Y 列最多小于或等于（在这个例子）23。

例如，我有这个示例数据：

结果应如下所示：

这是使用 LpSolve 在 R 中设置线性规划优化的副本？有解决方案，但我在 python 中需要相同的解决方案。

我在 Matlab 中有一个我定义的命令，它应该返回整数值：

我不想对结果进行四舍五入。我希望这些价值观int从一开始就存在。

这是我尝试过的：

知道如何强制x成为int价值矩阵而不是double？

我有一个非线性最小化问题，它将连续变量和二进制变量的组合作为输入。把它想象成一个网络流量问题，阀门可以控制吞吐量，泵可以改变方向。

一个“自然的”简约的表述可能是：

目标函数是确定性的，但求解成本很高。如果我不考虑二元变量，Scipy 的差分进化算法结果证明是解决我的问题的有用方法（收敛速度比盆地跳跃更快）。

已经有一些关于在基于差分进化的最小化问题中包含整数变量的证据。建议的方法将 y2,y3 变成连续变量 x2,x3 \in [0,1]，然后修改目标函数如下：

第三种，可能是幼稚的方法是将二进制变量组合成单个连续变量 z \in [0,1]，从而减少优化变量的数量。

例如，

应该首选以上哪一项，为什么？我很想知道如何以智能的方式将二进制变量集成到连续差分进化算法（例如 Scipy 的）中。

PS。我知道有一些文献提出了专门的混合整数进化算法。现在，我想和 Scipy 呆在一起。

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

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

有以下 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=sol2上面，因为它只是定义集合 I 的两种不同方法。我假设sol3是所有整数并且没有二进制变量，因为B未定义，但我没有任何文档来确认这一点。

我正在使用 docplex 构建一个混合整数程序，然后通过 cplex 解决该程序。但是，在尝试解决 MIP 时，我收到以下错误：

查看 lp 文件，可以看出以下行是问题所在：

创建约束的行是：

其中 ilp 是 docplex.mp.model 对象，每个 select_var 是一个二元决策变量。我真的不确定为什么会发生这种情况，如果有任何帮助，我将不胜感激！

我对算法非常陌生，现在正在研究一些路线优化问题，并遇到了一些关于以下方法的论文：

• 元启发式方法 基于种群（遗传算法、蚁群优化等） 基于单一解决方案（迭代局部搜索）

• 基于图的方法 ，例如 A* 算法

• 混合整数线性规划方法

我对这些方法之间的关系有点困惑，我们是使用例如使用 GA 来解决 MILP 还是它们都只是单独的方法？

提前致谢！！

我在 GAMS 中有以下问题

我实现了一个位置路由问题。在检查 .log 文件时，我注意到如果我修复它可以大大加快计算时间。我先举个例子：

假设我们有一个由 s1*s140 个节点组成的所有节点的集合 S，而节点 i1*i10 代表潜在的仓库，而 i11*i140 代表要服务的客户。所以我们有

套

二进制变量

参数

目标函数最小化固定开放成本和路由成本。

虽然将仓库的容量设置得足够大，以便能够为所有客户提供服务，并为每个仓库设置高昂的开业成本，但我的假设是，最佳解决方案是开设一个为所有客户服务的仓库。

我的假设是正确的，但是我注意到 CPLEX 首先需要很长时间来检查解决方案空间以打开通往许多仓库的方式。

当打开的仓库更少时，最优性差距会“跳跃”到接近最优的解决方案（见附件截图）。所以基本上很多时间都花在扫描明显“坏”的解决方案上。实际上，我有意识地使用了明显最好的解决方案必须仅包含一个仓库的示例。

我对你的问题：

我如何“指导” CPLEX 结帐由首先打开的仓库组成的解决方案，而不给出模型中可能打开的仓库的​​最大数量（即 sum(WH, z(WH)) =l= 1 ; ）

我尝试使用 .prior 后缀和 mipordind = 1 选项来分支优先级。Cplex 仍然检查了由 10 个打开的仓库组成的解决方案，所以我认为它没有帮助。

我还试图将仓库开仓成本设置得高得离谱。然而，包括打开尽可能多的仓库在内的解决方案仍然受到检查并浪费时间。

对不起，我希望我已经把所有必要的信息都放在了:)

期待您的建议

亲切的问候亚当