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

Question

假设我们得到了某种图形，其中给出了优化问题的可行区域。例如：这是一张图片

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

Answer 1

伙计，我同意其他人的看法，你应该比那幅油彩图片更具体一些；）。特别是，您既没有指定任何目标/目标方向，也没有给出任何上下文，那么该图应与整数变量相关，除了存在分离可行集（可以通过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])如果i对应于一个多边形，a[i,1]*x[1]+a[i,2]-rhs[i]<=M*(1-y[2])如果i对应于另一个多边形，并且如果您的行从下面限制了事情：-M*(1-y[1])<=-a[i,1]*x[1]-a[i,2]+rhs[i]如果i对应于一个多边形，[i]如果i对应于另一个多边形。重要的是，M必须足够大，但不能太大而不会引起数值问题。

话虽这么说，我绝不是这些分离编程技术的专家，所以随时可以插话，进行更正或使事情变得更清楚。

而且，一个更复杂的问题通常会产生更复杂和令人满意的答案;）如果您努力组成一个真正的小示例问题，您可能会得到问题的完整表述，甚至是一段可执行的代码马上。