1

我的问题可能与这个有关，但是我没有得到它的解决方案。所以我会尝试询问我的具体问题。

我想知道 2D 中的一组半平面是否有一个空的交叉点。因此，我有两个无界变量x和y. 在 C# 中我有

x = gModel.AddVar(-GRB.INFINITY, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "x");
y = gModel.AddVar(-GRB.INFINITY, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "y");

然后我添加约束，每个半平面一个：

gModel.AddConstr((-1.0 * x) + (0 * y) <= 100, "h10");
gModel.AddConstr((1.0 * x) + (0 * y) <= 100, "h09");
gModel.AddConstr((0 * x) + (-1.0 * y) <= 100, "h08");
gModel.AddConstr((0 * x) + (1.0 * y) <= 100, "h07");
gModel.AddConstr((1.0 * x) + (0 * y) <= -33.3333334, "h06");
gModel.AddConstr((-1.0 * x) + (0 * y) <= 77.7777778, "h05");
gModel.AddConstr((-1.0 * x) + (0 * y) <= 55.55555533333333, "h04");
gModel.AddConstr((-1.0 * x) + (0 * y) <= 48.148148155555553, "h03");
gModel.AddConstr((-1.0 * x) + (0 * y) <= 40.740740733333332, "h02");
gModel.AddConstr((-1.0 * x) + (0 * y) <= 70.370370377777789, "h01");
gModel.AddConstr((1.0 * x) + (0 * y) <= -62.962962955555561, "h00");

我使用 (0 * x + 0 * y, GRB.MINIMIZE) 进行优化以获得结果状态，该状态表明是否存在可行的解决方案（即不是空的交叉点）或没有（空的交叉点）。

问题是，在之前的设置中，我得到一个 UNBOUNDED 状态，而h00和h02显然是矛盾的！怎么样？

我正在使用 Gurobi 5.5。使用初始设置

 GurobiEnv.Set(GRB.IntParam.DualReductions, 0);

请问有什么建议吗？

补充： Rich 创建了一个要点来重现该问题。

4

1 回答 1

0

我想这又是一个数值问题，因为 Gurobi 试图从问题描述中消除系数为零的变量。完全为零的目标函数可能会导致不良后果。

实际上，我会说使用 Gurobi 来解决这个问题是矫枉过正的。确定这些半平面是否有共同点的一种简单方法是计算边界线的所有交点（n 条线约为 n²），然后检查它们中的每一个是否位于所有半平面中。如果是这样，这是您的可行点。否则，就没有这一点。

于 2015-09-19T09:56:05.970 回答