Assume we have the problem
min c'x
st. A x = b (P0)
x >= l
where l is large in absolute value say l_j=-1000 for all js. (l is short for lower bounds). The dual problem is
max b'y + l's
st. A'y + s = c (D0)
s >= 0
It is very common to transform the problem to
min c'x + c'l
st. A x = b- A l (P1)
x >= 0
for efficiency reasons. Indeed all interior-point optimizers will do that.
The dual problem is
max b'y + c'l
st. A'y + s = c (D1)
s >= 0
Let us say we solve (P1) and (D1). Moreover,
A'y + s = c
holds only approximate which definitely be the case for interior-point methods. To be precise we have
A'y + s = c + e
holds exactly where 0 < |e|| << 1.
This implies if (y,s) from (D1) is reported as an optimal solution to (D0) then there can be a big error in the dual objective value. Note that is not the case if l=0. Now if instead we report (y,c-A'y) as the optimal dual solution to (D0) then objective value will be correct but then s>=0 might be violated.
The question is that which dual solution to report. I guess the answer is that it depends on your priorities.
I will leave it as an exercise to the interested reader to construct a small example demonstrating this. Since I just spend all day figuring out that happening on instance with 100K variables.
Interesting. I have had similar experiences, to some extent it's a bad formulation and will only happen with large bounds. In my opinion returning a dual solution which does not validate feasibility is preferred. If the primal and dual objectives differs significantly, then the user must deal with it him self. It's a no win situation for the optimizer vendor..
ReplyDelete