2

我需要编写一个整数程序。它非常简单，但问题是几乎没有关于如何使用可调用库为 GLPK 编写整数程序的好信息，更不用说为 GLPK# 编写整数程序了。

我的整数程序看起来很像这样：

Maximise: X[0] + X[1] + ... + X[n];

s.t.      X[1] + X[5] <= 1;
          X[1] + X[7] <= 1;
          X[2] + X[4] <= 1;
          X[3] + X[9] <= 1;
          ...
          X[i] = {0,1}

我有一堆二进制 X，我想最大化总和。某些 X 排除了某些其他 X。

到目前为止，我所做的只是

LPProblem lp = new LPProblem()
{
  ModelClass = MODELCLASS.MIP,
  ObjectiveDirection = OptimisationDirection.MAXIMISE,
  ObjectiveName = "Z"
};

// Stuff goes here, I'm not sure how to represent the model

SOLVERSTATUS status = lp.SolveInteger();
4

3 回答 3

4

也许你可以使用 GLPK# 以外的东西。如果您是一名学者，您可以免费获得 CPLEX 或 Gurobi。否则，谷歌 OR 工具在过去一年中一直支持 C#。根据Google OR Tools page，它包含 GLPK 和 CBC 的包装器。仅仅因为您可以在两个求解器之间切换，我建议您使用 Google OR Tools。对于您的特定实例，您可能会发现一种求解器比另一种更好。

于 2013-02-22T06:30:12.027 回答
1

只是一些其他的评论来填补这一点。首先 GLPK 是可以的，但对于大型模型来说速度很慢 - 如果您面临一个大问题（即使这是未来的方式），您可能最好看看其他一些已经提到的求解器。此外，GLPK# 的开发似乎非常安静——我已经将近 2 年没有看到任何更新了。这可能是一件好事（它稳定且有效，所以为什么要更改它）或者它可能是停滞的。

如前所述，Gurobi 和 CPLEX 都是非常强大的快速求解器，并在 C# 中提供了良好的建模 API。如果您可以访问这些内容，那么它们确实值得。SCIP 求解器很好 - 可能是非商业求解器中最好的，但我不确定 C# 接口。

Google OR 工具的另一个潜在优势是强调约束编程——如果您有一组复杂的二元变量和约束，那么 CP 方法可能具有一些优势。

于 2013-02-28T11:06:14.423 回答
1

您描述的问题称为“最大集团问题”。创建一个无向图，其顶点标记为 1 到 n。如果您有 x[i] + x[j] <= 1 形式的约束，则在 i 和 j 之间绘制一条边。令 H 为互补图——即当且仅当G 中 i 和 j 之间没有边时，您在 i 和 j 之间有一条边。一个 clique 是顶点的子集，每个顶点由一个边缘到 S 的所有其他成员。你的问题是找到一个最大规模的集团。这是一个众所周知的 NP 完全问题。尽管如此，还是有一些非常好的启发式算法（甚至可能还有可用的软件）来解决这个问题。查看以下调查http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.5821

您给出的 IP 公式不是很严格，因此，除非 n 相当小，即使使用 CPLEX 和 GUROBI 等顶级求解器，您也可能无法使用该公式在合理的时间内解决您的问题。

于 2013-06-09T16:28:40.480 回答