How to get an extreme ray of an LP from Gurobi

Question

I am working on a problem of form \begin{equation} \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} \end{equation} 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);
model.set (GRB_IntParam_Threads, 4);

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];
model.addConstr (tau <= expr);

// 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?

Answer 1

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

Answer 2

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.