CODEWITHSUNDEEP
optimizationmathematical-optimizationcplexinteger-programming
excalibur1491
excalibur1491

Reputation: 1221

CPLEX obtain reduced costs of a MIP?

I am solving a MIP problem using CPLEX. After solving it, I want to get the reduced costs. I am aware of the fact that reduced costs don't exist for the MIP, so I did the following:

     int type = CPXgetprobtype(env, lp);
     if(CPXchgprobtype(env, lp, CPXPROB_FIXEDMILP)) abort();
     if(CPXlpopt(env,lp)) abort();
     int blabla; double blublu;
     if(CPXsolution (env, lp, &blabla , &blublu , x, pi, slack, dj)) abort();
     for (int i = 0; i < CPXgetnumcols(env,lp); i++) {
        printf("v%d = %f, ", i,dj[i]);
        if ((i+1) % 10 == 0) printf("\n");
     }
     if(CPXchgprobtype(env, lp, type)) abort();

When I print the array dj, it's all 0's. I also tried using CPXgetdj instead of CPXsolution, with the same result.

After reading this I believe what I am doing is correct. Yet it does not seem to work. My problems have 20000 variables, and I have tried with a bunch of them and it always says 0...

I have a small time limit, so it does not prove optimality (but it does find an integer solution), I'm not sure if this matter.

Thanks

Upvotes: 2

Views: 945

Answers (1)

acco93
acco93

Reputation: 138

Consider a general linear problem P where all variables are fixed at the value of the integer optimal solution of a given integer problem I. Let P be

enter image description here

where the overlined bj is the value of xj in the optimal integer solution. The dual problem D of P is

enter image description here

The optimal solution of D of cost z(D) = z(P) = z(I) could be found setting

enter image description here

thus the reduced costs are

enter image description here

Upvotes: 2

Related Questions