Originally posted by: VivekPeriaraj

Hello,

 

Would like an expert opinion on computing the dual objective from the duals from CPXgetpi(). Basic question, but keep getting confused because of the signs. :)

 

I have less than or equal to, greater than or equal to and equality constraints in my model. And I have a dual vector from CPXgetpi(). I have the following options to compute the dual objective:

 

1)

 

dualObj = 0.0

If (_sense[i] == 'G')  dualObj += pi[i] * (-b[i]).

else dualObj += p[i] * b[i].

 

2) 

 

dualObj = 0.0;

If (_sense[i] == 'E')  dualObj += pi[i] * b[i].

else dualObj += fabs(p[i]) * b[i].

dualObj = -dualObj

 

Or something else?

 

Regards,

Vivek

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Hello,

 

The following seems to give us correct objective. Pls correct me if I am wrong.

if (_sense[i] == 'E') {
if (_pi[i] < 0.0) _dualObj += (_pi[i] * _rhs[i]);
else _dualObj += (_pi[i] * -_rhs[i]);
}
else if (_sense[i] == 'L') {
_dualObj += (_pi[i] * _rhs[i]);
}
else {
_dualObj += (_pi[i] * -_rhs[i]);
}

Regards,

Vivek

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: TobiasAchterberg

It is much simpler than this: you just calculate the scalar product of pi with the rhs vector.

If you are minimizing, then pi[i] >= 0 for 'G' rows and pi[i] <= 0 for 'L' rows.

It gets more complicated if you are having ranged rows, though...

And additionally, you also need to consider the reduced costs (let's call them dj), if you have any variable with a non-zero finite bound. Then you need to add dj[j] * lb[j] if dj[j] > 0 and dj[j] * ub[j] if dj[j] < 0.

 

The point of the dual LP (if the primal is minimization) is that you want to find multipliers of the constraints (and bounds) such that you end up with an aggregated >= row. This rows yields a lower bound for the primal LP, and the strong duality theorem says that the best lower bound that you can get (i.e., the maximum of the dual LP) is equal to the optimal (minimal) value of the primal LP.

Since you need to get a valid >= row as aggregation, this means that the multipliers for >= rows (and lower bounds) in the primal need to be non-negative, while the multipliers for <= rows (and upper bounds) need to be non-positive.

 

Tobias

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Hi Tobias,

 

Thanks a lot!

 

Is it possible to use the duals I get from CPXgetpi() on a dual LP which I have formulated manually without the bounds on the primal variables? Other day, you mentioned that if all my primal variables are bounded, then the associated dual constraints are boxed and that any dual vector would be feasible. My problem now is I have a dual vector (derived from two problems) and I want to compute the objective of this vector. The problems that produced these dual vectors still have the bounds for the primal variables. If so, I gather I can't compute the objective without including the reduced costs on the bounds?

 

Regards,

Vivek

 

Regards,

Vivek.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

I don't know whether I got it correctly, but do you want to do the following:

1. decompose one big problem into two smaller ones
2. find dual solutions to these two problems
3. remove the bounds from the big problem
4. combine the two dual solutions from the two small problems to a dual solution for the big problem
5. calculate the dual objective

?

In this case, you cannot be sure that the combined dual vector is dual feasible, as there are no bounds implying that any dual solution is dual feasible. If it is dual feasible, you can calculate the dual objective using only the dual values. But you have to ensure dual feasibility somehow.

On the other hand, I do not understand why you are trying to do this.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Hello Thomas,

 

Thank you. You have got the steps correct. My problem is DW decomposable and I have a master and a pricing sub. And I could derive the duals for my original problem using the optimal duals from these two problems (as per Walker method). Like you have noted, the question is the dual feasibility. My tests indicate that dual feasibility is not easy in the beginning of the column generation but it's possible in later iterations. But I am not sure, if I am getting the signs correct for my dual vector.

 

Thanks,

Vivek.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: TobiasAchterberg

Let us review the theory of dualization for LPs that include bounds on variables. First, let's consider only >= constraints and minimization.

The primal LP can be defined as

min  cx
s.t. Ax >= b     (y)
      x >= l     (q)
     -x >= -u    (r)

Then the associated dual LP is

max  by + lq - ur
s.t. yA + q - r = c
     y >= 0
     q >= 0
     r >= 0

Suppose that all bounds l,u are finite. Then, for any dual vector y >= 0 you can just calculate the resulting reduced costs q-r = c - yA. If for variable j we have (c-yA)_j >= 0 then we define q_j := (c-yA)_j and r_j := 0. Otherwise we define q_j := 0 and r_j := -(c-yA)_j. Doing so ensures q >= 0 and r >= 0 and consequently we get a dual feasible solution (y,q,r).

If an upper bound u_j is infinite, then we must have r_j = 0. If a lower bound l_j is infinite, then we must have q_j = 0. Thus, in these cases it is no longer the case that any dual vector y >= 0 can be extended to a dual feasible solution (y,q,r).

If a primal constraint is a <= inequality, then we have y_i <= 0 for the corresponding dual variable. If a primal constraint is an equation, then the corresponding dual variable y_i is free.

So, as a summary, when you think about the dual solution you always need to think about both, the dual row multipliers y and the reduced costs (q,r). You cannot ignore the bounds in the primal, and similarly you cannot ignore the reduced costs in the dual.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Thanks Tobias for the explanation!

 

The problem was that, when I formulated the dual problem using CPXdualwrite(), the problem sense changed to minimize while my primal was minimize too. Now, if I reverse the sign of the dual vector and the reduced cost vector, then my derived duals were feasible as reported by CPXgetrowinfeas() right from the very first iteration :) Thanks a ton. I knew my problem was with the interpretation of the sign and it indeed was! Thanks Tobias and Thomas for your time and I hope someone would find this discussion useful later.

 

Regards,
Vivek

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

I also tried with bounds removed on my primal as many of the variables have implied bounds. The dual objective was computed correctly and duals were feasible. Thanks!

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Thanks Tobias. By including the reduced costs, I am now getting right dual objective.

#CPLEXOptimizers
#DecisionOptimization