3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Is it possible that you need to deactivate presolve in order to get the extreme ray? $\endgroup$ – k88074 Nov 18 '20 at 8:02
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for your answer. however, I already applied this in the code as: model.set(GRB_IntParam_InfUnbdInfo, 1); model.optimize(); $\endgroup$ – independentvariable Nov 17 '20 at 18:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Richard Nov 18 '20 at 8:44
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.