# How to get an extreme ray of an LP from Gurobi

I am working on a problem of form $$$$\begin{array}{l @{\quad} l} \mathrm{max}_{x, u} & p^{\top} u \\ \text{st.} & A u + a x \leq 0 \\ & x \in \{0, 1\}^n \\ & u \in \mathbb{R}^k \end{array}$$$$ Sometimes, this problem is unbounded from the above. I would like to obtain the extreme ray of both $$x$$ and $$u$$ in a C++ environment. I have tried different suggestions from the internet, however, it always fails. So I am wondering what exactly a sample code looks like to achieve my purpose?

The code that I have arrived currently is

// set up Gurobi model
GRBModel model = GRBModel (*prob->env);

GRBVar *x = model.addVars (n, GRB_BINARY);
GRBVar *u = model.addVars (size_of_u, GRB_CONTINUOUS);

GRBVar tau = model.addVar (-GRB_INFINITY , GRB_INFINITY, 1.0, GRB_CONTINUOUS);

// set up objective function
model.set (GRB_IntAttr_ModelSense, GRB_MAXIMIZE);

GRBLinExpr expr;

// epigraphical constraints: tau <= p'u
for (int k = 0; k < size_of_u; ++k)
expr += p[k] * u[k];

// Constraints A' u - a' x <= 0
for (int k = 0; k < constraint_vectors.size(); ++k){
for(auto & a : constraint_vectors[k]){
expr = 0;
for (int l = 0; l <size_of_u; ++l)
expr += A_T[k][l]*u[l];
for (int i = 1; i < n; ++i) //
expr -= a[i]*x[i] + a[n + i]*(1-x[i]);
model.addConstr (expr -  a[-1] <= 0 );
}
}

model.set(GRB_IntParam_InfUnbdInfo, 1);
model.optimize();
for (int i=0; i<iterations;i++){
cout << "This is the solution status in the master problem "
<< model.get(GRB_IntAttr_Status) << endl;
if (model.get(GRB_IntAttr_Status) == 5){
for (int l = 0; l< size_of_u; ++l) {
current_u[l] = u[l].get(GRB_DoubleAttr_UnbdRay);
cout << "current_u[" << l << "] = " << current_u[l] << endl;
}
}
}


When run this code, there is an error message saying:

libc++abi.dylib: terminating with uncaught exception of type GRBException


pointing to the first line inside the second for loop. I am also wondering why this error occurs?

• Is it possible that you need to deactivate presolve in order to get the extreme ray? – k88074 Nov 18 '20 at 8:02

In order to query the GRB_DoubleAttr_UnbdRay attribute, you need to optimize the problem with the InfUnbdInfo parameter set to 1.

• thanks for your answer. however, I already applied this in the code as: model.set(GRB_IntParam_InfUnbdInfo, 1); model.optimize(); – independentvariable Nov 17 '20 at 18:46
• You are solving a MIP though. In those cases the extreme ray is not directly returned by Gurobi. You should rather fix the model and then run the optimization again to convert it to a continuous problem. – Richard Nov 18 '20 at 8:44

I don't know whether this is the reason, but the documentation says that InfUnbdInfo is for LP only. So we might have to work with the LP. Two thoughts:

• x = 0, u = 0 is a feasible solution for the MIP.

• As x is bounded, x will not be part of the ray.

Thus, any ray for the LP should also be a ray for the MIP.

So if Gurobi decides your problem is unbounded, you might just switch to the LP and solve it through primal simplex to obtain your ray.