时间戳

首页 > 解决方案 > 我将如何构建与图对应的整数优化模型

modeling - 我将如何构建与图对应的整数优化模型

问题描述

假设我们得到了某种图，其中给出了优化问题的可行区域。例如：这是一张图片 在此处输入图像描述

我将如何继续在整数优化问题中构造这些约束？有人有任何提示吗？谢谢！

标签： modeling

解决方案

伙计，我同意其他人的观点，即你应该比那幅画得更具体一点；）。特别是，您既没有指定任何目标/目标方向，也没有给出任何上下文，那么这个图应该是与整数变量相关的，除了可以通过 MIP 技术建模的析取可行集的存在。看起来你的问题是你概念化的形式化。但是，如果您只是懒惰并且只对对析取区域建模感兴趣，您应该研究析取编程技术，例如“big-M”（注意：big-M 重新表述可能会出现问题）。如果你能得到一个（相当容易），你应该瞄准一些凸包重构。

回到您的图片，很明显您在两个实际维度（假设在 R^2 中）存在问题，其中限制可行集的约束是线性的（构成可行多边形的线）。

所以你知道你有两个维度并且需要两个真正的连续变量，比如说x[1]和x[2]，来制定你的每个线性约束（a[i,1]*x[1]+a[i,2]<=rhs[i]对于一些索引 i 对应于你的图表中的行数）。此外，您的变量似乎被限制在第一个字节上，因此x[1]>=0应该x[2]>=0保持不变。现在，要添加析取，您需要一些仅在某个条件为真时才成立的约束。因此，您可以添加两个二元决策变量，比如说y[1],y[2]和一个附加约束y[1]+y[2]=1，以表明只能同时激活一组约束。您应该能够在 big-M 的帮助下通过重新制定约束来实现这一点，如下所示：

如果你用你的线从上面绑定东西： a[i,1]*x[1]+a[i,2]-rhs[i]<=M*(1-y[1])如果我对应一个多边形， a[i,1]*x[1]+a[i,2]-rhs[i]<=M*(1-y[2])如果我对应另一个多边形，如果你的线从下面 绑定东西：如果我对应-M*(1-y[1])<=-a[i,1]*x[1]-a[i,2]+rhs[i]一个多边形， -M*(1-y[1])<=-a[i,1]*x[1]-a[i,2]+rhs[i]如果我对应另一个多边形. 重要的是 M 足够大，但不能太大而导致数值问题。

话虽如此，我绝不是这些析取编程技术的专家，所以请随意插话，添加更正或使事情更清楚。

此外，一个更复杂的问题通常会产生更详细和令人满意的答案；）如果您努力制作一个真正的小示例问题，您可能会得到一个完整的问题表述，甚至是一段可执行的代码。时间。

推荐阅读