Gurobi unbounded result issue

Question

My question may be related to this one, however I did not get its solution. So I'll try to ask for my specific problem.

I want to find out whether a set of halfplanes in 2D has an empty intersection or not. Thus, I have two unbounded variables x and y. In C# i have

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

Then I add constraints, one for each halfplane:

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");

I optimize with (0 * x + 0 * y, GRB.MINIMIZE) to get the result state which says whether there is a feasible solution (i.e. not an empty intersection), or not (an empty intersection).

The problem is that with the previous setup, I get an UNBOUNDED state while it is clear that h00 and h02 contradict! How that?

I'm using Gurobi 5.5. With the initial setting

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

Any suggestions please?

SUPPLEMENTAL: Rich created a gist to reproduce the issue.

Answer 1

I guess that this is again a numerical problem because Gurobi tries to eliminate variables with zero coefficient from the problem description. An objective function which is completely zero might lead to unwanted consequences.

Actually, I would say that using Gurobi for this problem is overkill. A simple way to determine if these half-planes have a common point would be to calculate all intersection points of the boundary lines (about n² for n lines) and then check for each of them if it lies in all half-planes. If it does, it is your feasible point. Otherwise, there is no such point.