CPLEX 获得 MIP 的降低成本？

Question

我正在使用 CPLEX 解决 MIP 问题。解决后，我想得到降低的成本。我知道 MIP 不存在降低成本的事实，因此我执行了以下操作：

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

当我打印数组dj时，它全是0。我也尝试使用 CPXgetdj 而不是 CPXsolution，结果相同。

看完this我相信我所做的是正确的。但它似乎不起作用。我的问题有 20000 个变量，我尝试了其中的一些，但它总是显示 0...

我有一个小的时间限制，所以它不能证明最优性（但它确实找到了一个整数解），我不确定这是否重要。

谢谢

Answer 1

考虑一个一般的线性问题P，其中所有变量都固定为给定整数问题的整数最优解的值I .设 P 为

其中上划线的bj是最优整数解中xj的值。 P的对偶问题D是

成本z(D) = z(P的最优解D ) = z(I) 可以找到设置

因此降低的成本是

CPLEX 获得 MIP 的降低成本？

CPLEX obtain reduced costs of a MIP?

optimization

mathematical-optimization

cplex

integer-programming